Rambler's Top100

Скачать программы    Все программы автора

РОБОТ

Робот движется по полю, которое состоит из N клеток, выстроенных в ряд. На каждой из клеток находится кубик определенного цвета.

До начала движения робот находится на первой клетке поля и не держит ни одного кубика. Находясь на клетке, робот может выполнить не более одного раза каждую из следующих операций: (1) положить кубик того же цвета, который лежит на текущей клетке; (2) поднять с клетки тот кубик, который находился там сначала. После этого робот перемещается на следующую клетку или останавливается, если текущая клетка последняя в поле.

Одновременно робот может держать не более K кубиков. На момент остановки робот не должен держать ни одного кубика.

Задание

Напишите программу ROBOT, которая по информации о цвете кубиков и ограничении на количество кубиков, которое может держать робот, определяет максимальное общее количество кубиков, которое робот может перенести с места на место, двигаясь по полю.

Входные данные

Первая строка входного файла ROBOT.DAT содержит символьную строку длинны N (1N≤1000). Строка состоит из маленьких букв латинского алфавита. Каждая буква соответствует клетке поля и определяет цвет кубика, который находится в этой клетке. Вторая строка содержит ограничение на количество кубиков, которое одновременно может держать робот K (1K≤25).

Выходные данные

Единственная строка выходного файла ROBOT.SOL должна содержать целое число — максимальное количество кубиков, месторасположение которых робот может изменить, двигаясь по полю.

Пример входных и выходных данных

ROBOT.DAT

ROBOT.SOL

rgbbggrmcm

2

4

 { fp } 

program Robot;

const

FILE_IN = 'ROBOT.DAT';

FILE_OUT = 'ROBOT.SOL';

MAX_SIZE = 1000;

MAX_K = 25;

var

N : Integer;

K : Integer;

Field : array[1..MAX_SIZE] of Char;

Prev : array[1..MAX_SIZE] of Integer;

Transfered : Integer; { The number of the transfered cubes }

Hands : array[1..MAX_K] of Integer;

procedure Init;

var

Fin : Text;

c : Char;

i : Integer;

Letter : array['a'..'z'] of Integer;

begin

Assign(Fin, FILE_IN);

Reset(Fin);

N := 0;

c := ' ';

while ( c <> Chr(10) ) do

begin

Read(Fin, c);

if (c in ['a'..'z']) then

begin

Inc(N);

Field[N] := c;

end;

end;

ReadLn(Fin, K);

Close(Fin);

{ Initialize Transfered }

Transfered := 0;

{ Initialize Hands }

for i:=1 to K do

Hands[i] := 0;

{ Initialize Prev }

for c:='a' to 'z' do

Letter[c] := 0;

for i:=1 to N do

begin

Prev[i] := Letter[Field[i]];

Letter[Field[i]] := i;

end;

end;

procedure Run;

var

i : Integer;

j : Integer;

MS : Integer; { The number of Maximal Suitable hand }

begin

for i:=1 to N do

begin

{ Check if we can put a cube in the i-th cell }

if (Prev[i] > 0) then

begin

{ Look for the most suitable hand to take the cube that lays on the cell Prev[i] }

MS := 0;

for j:=1 to K do

begin

if (Hands[j] <= Prev[i]) then

begin

if (MS = 0) then MS := j

else if (Hands[MS] < Hands[j]) then MS := j;

end;

end;

if (MS <> 0) then

begin

Inc(Transfered);

Hands[MS]:=i;

end;

end;

end;

end;

procedure Done;

var

Fout : Text;

begin

Assign(Fout, FILE_OUT);

Rewrite(Fout);

WriteLn(Fout, Transfered);

Close(Fout);

end;

begin

Init;

Run;

Done;

end.

Белорусский рейтинг MyMinsk.com Сайты беларуси Регистр "ЗУБР" Каталог на TIGA.BY, а также  новости, работа, объявления, фото и многое другое Рейтинг@Mail.ru Rambler's Top100 Белорусский каталог программ
Hosted by uCoz