Имеется последовательность строк. Первая строка "a", вторая "bc". Тре-
тья строка является конкатенацией предыдущих двух (к первой строке
приписывается вторая) – "abc". Четвертая строка – конкатенация второй и
третьей ("bcabc"). Все дальнейшие строки строятся аналогично, склеива-
нием предыдущих двух. Требуется определить, какой символ находится на
указанной позиции в строке с заданным номером.

Ввод:
Два целых числа, разделенные пробелом – K и P (0 < K <= 10^9), (0 < P <=
10^9), где K – номер строки Фибоначчи, а P – номер позиции в строке.

Вывод:
Искомый символ для соответствующего теста: "a", "b" или "c" (символы
латинского алфавита). Если Р превышает размер К-й строки (K <= 10^9), то
необходимо вывести «No solution» (без кавычек).

Пример
Ввод:
18 58
Вывод:
A

Может есть хоть какие-то идеи? 

Uses CRT;
Var
k,p,i:LongInt;
x,y,z:string;
Begin
ClrScr;
WriteLn('  „ ­л ¤ўҐ бва®ЄЁ: ЇҐаў п - a, ўв®а п - bc.');
WriteLn('Џа®Ја ¬¬  Їа®Ё§ў®¤Ёв Є®­Є вҐ­ жЁо бва®Є ¬Ґв®¤®¬ ”ЁЎ®­ ззЁ,');
WriteLn('Ё ўлў®¤Ёв бЁ¬ў®« ў гЄ § ­­®© Ї®§ЁжЁЁ "p" гЄ § ­­®© бва®ЄЁ "k".');
WriteLn;
Write('‚ўҐ¤ЁвҐ ­®¬Ґа бва®ЄЁ, k='); ReadLn(k);
Write('‚ўҐ¤ЁвҐ ­®¬Ґа Ї®§ЁжЁЁ, p='); ReadLn(p);
x:='a';
y:='bc';
If k=1 then y:='a';
If k=2 then y:='bc';
For i:=3 to k do
 Begin
 z:=y;
 y:=Concat(x,y);
 x:=z;
 End;
If (P>Length(y)) or (P=0) then WriteLn('No solution.')
               else
 Begin
 y:=copy(y,p,1);
 WriteLn(y);
 End;
ReadLn;
End.

Как вариант. Делал в обычном турбопаскале, почему-то беда со шрифтами. Думаю, можно сделать и проще, но не до этого щас. 
P.S. Первые три writeln - просто пояснение пользователю, что делает программа. Вторые два - соответственно, ввод k и p. Дальше все очевидно.
P.P.S. В следующий раз указывайте, что это задача ФРТК.

Это сообщение отредактировал(а) dEvIllEssE - 27.1.2011, 15:53

А перед Ctrl-C надо клавир в русскую раскладку переключать...


А запускать-то пробовал? при К порядка сотен миллионов? 


Во-первых, просто построй хотя бы первые два десятка строк и посмотри на них попристальнее... сразу выяснится, что буквовка запросто определяется в зависимости от чётности номера строки и позиции символа в ней (длина периода 5 и 8 соответственно).
Во-вторых, найди способ нахождения наибольшего числа Фибоначчи, не превосходящего заданное (это для определения, не надо ли вывести No solution). Или просто составь и забей в программу статическую таблицу первых 43 чисел (или напиши вычисление нужного числа).

Когда всё это проделаешь - пполучишь полный алгоритм.

Это сообщение отредактировал(а) Akina - 27.1.2011, 16:22

Пробовал, пробовал. Только при порядке сотен тысяч. Ответ выдавал, но проверить его нет возможности. Насчет сотен миллионов, попробую завтра, а то это же на час наверно будет.

P.S. Я решал еще другую задачку от ФРТК, где надо посчитать количество чисел содержащих в себе "1", от 1 до N. Там задал N=999999999 - через 20 минут получил ответ, опять же не проверял 

Описанный мной подход даёт ответ практически мгновенно.

Да я и не спорю, что ваши методы круче. Я сделал тупо то, что спрашивается, особо не вдумываясь. О чем собственно и предупредил в своем посте с решением. На счет Ctrl+C, я так не делал, я просто сохранил в расширении txt. А ваще я в программировании нуб, в школе что-то учил когда-то. Просто интересно иногда подумать 

Но оттуда-то сюда как вставлял?


Вы сделали "в лоб". Но это же не алгоритмика... она для того и существует, чтобы 

и найти "чёрный ход".

У меня уже в txt вставилось со сломанными шрифтами. Оттуда через Ctrl+C. А насчет "иногда подумать" - хватит уже подкалывать... Я и не претендую на то, чтобы быть мего программистом. Алгоритмика это хорошо и правильно, но требует образования и опыта. Для тебя эта задачка примитивна и легка; а я тоже понимаю, что она примитивна для настоящего программиста, но даже "в лоб" пришлось подумать.

Да ладно  не уметь не стыдно, стыдно не хотеть научиться.

Спасибо всем за помощь. Разобрался с решением.

Единственное, что заметил это то, что в зависимости от четности строки первые три буквы не меняются. Т.е. если строка четная, то - bca, если нечетная - abc. 


Можно по подробнее?

Это сообщение отредактировал(а) km999 - 31.1.2011, 17:02

Я же сказал, что 

так что посмотреть первые ТРИ символа - МАЛО.

Извините, но я такого не писал, это вы процитировали Акину, ошибочно указав на меня. Так что все стрелки на него :Р

Как указал тов. Akina, буква действительно неким "магическим" образом зависит от позиции в строке и номера строки   

i-ая строка есть конкатенация строк i-1 и i-2. Следовательно, буква на позиции X в i-ой строке - либо буква на позиции X в строке i-2 (если X меньше или равно длины строки i-2), либо на позиции X-len(i-2) (len(i-2) - длина i-2-ой строки); и еще мы знаем ответы для i=1 и i=2. Вот такая реккурентная формула. Можно реализовать рекурсивно, можно циклом. Исходный код:


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

P.S. Где-то я эту задачу уже видел, на тимусе, что ли?

См. аттач... это для уж совсем ленивых...

Присоединённый файл ( Кол-во скачиваний: 16 )
 1.PNG 7,21 Kb

Добавлено @ 00:56

Это задача из заочной олимпиады МФТИ



Это сообщение отредактировал(а) km999 - 5.2.2011, 00:58