Задача: Игра со строкой
Имя входного файла: abc.in
Имя выходного файла: abc.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта
Маленькая Элизабет любит играть со строками. У нее есть строка длины n, полностью состоящая из букв «а». Она делает со строкой следующие действия:
§Если первая буква «а», то она дописывает в конец строки «bc», после чего удаляет из строки первые 2 буквы.
§Если первая буква «b», то она дописывает в конец строки «a», после чего удаляет из строки первые 2 буквы.
§Если первая буква «c», то она дописывает в конец строки «aaa», после чего удаляет из строки первые 2 буквы.
Элизабет останавливается после того, как у нее получится строка, состоящая из одной буквы «а». Например при n=4 потребуется 6 шагов
aaaa→aabc → bcbc→ bca→ aa→bc →a
Сколько потребуется шагов для любого n (2≤n≤100)?
Решение
Данная задача — моделирование гипотезы Коллатца
n= 27 ответ 40656
n= 63 ответ 42160
Program B;
Var
i,l:byte;
step:integer;
s:string;
input,output:text;
Begin
Assign(input, 'abc.in');
Reset(input);
Assign(output, 'abc.out');
Rewrite(output);
readln(input,l);
s:='';
for i:=1 to l do S:=s+'a';
step:=0;
while s<> 'a' do
begin
if s[1]='a' then
s:=s+'bc'
else
if s[1]='b' then
s:=s+'a'
else
s:=s+'aaa';
Delete(s,1,2);
step:=step+1;
end;
writeln(output,step);
Close(input);
Close(output);
End.