Скачать программы Все программы автора
РОБОТ
Робот движется по полю, которое состоит из N клеток, выстроенных в ряд. На каждой из клеток находится кубик определенного цвета.
До начала движения робот находится на первой клетке поля и не держит ни одного кубика. Находясь на клетке, робот может выполнить не более одного раза каждую из следующих операций: (1) положить кубик того же цвета, который лежит на текущей клетке; (2) поднять с клетки тот кубик, который находился там сначала. После этого робот перемещается на следующую клетку или останавливается, если текущая клетка последняя в поле.
Одновременно робот может держать не более K кубиков. На момент остановки робот не должен держать ни одного кубика.
Задание
Напишите программу ROBOT, которая по информации о цвете кубиков и ограничении на количество кубиков, которое может держать робот, определяет максимальное общее количество кубиков, которое робот может перенести с места на место, двигаясь по полю.
Входные данные
Первая строка входного файла ROBOT.DAT содержит символьную строку длинны N (1≤N≤1000). Строка состоит из маленьких букв латинского алфавита. Каждая буква соответствует клетке поля и определяет цвет кубика, который находится в этой клетке. Вторая строка содержит ограничение на количество кубиков, которое одновременно может держать робот K (1≤K≤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.