Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Интересные и занимательные задачи по программированию > Конкатенация строк


Автор: km999 24.1.2011, 23:00
Имеется последовательность строк. Первая строка "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

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

Автор: dEvIllEssE 27.1.2011, 15:24
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.

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

Автор: Akina 27.1.2011, 16:16
Цитата(dEvIllEssE @  27.1.2011,  16:24 Найти цитируемый пост)
почему-то беда со шрифтами

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

Цитата(dEvIllEssE @  27.1.2011,  16:24 Найти цитируемый пост)
Делал в обычном турбопаскале

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

Цитата(km999 @  25.1.2011,  00:00 Найти цитируемый пост)
Может есть хоть какие-то идеи?  

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

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

Автор: dEvIllEssE 27.1.2011, 18:01
Цитата

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


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

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

Автор: Akina 27.1.2011, 18:12
Цитата(dEvIllEssE @  27.1.2011,  19:01 Найти цитируемый пост)
это же на час наверно будет.

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

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

Автор: Akina 28.1.2011, 10:53
Цитата(dEvIllEssE @  28.1.2011,  11:42 Найти цитируемый пост)
я просто сохранил в расширении txt

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

Цитата(dEvIllEssE @  28.1.2011,  11:42 Найти цитируемый пост)
 я и не спорю, что ваши методы круче

Вы сделали "в лоб". Но это же не алгоритмика... она для того и существует, чтобы 
Цитата(dEvIllEssE @  28.1.2011,  11:42 Найти цитируемый пост)
иногда подумать  

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

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

Автор: Akina 28.1.2011, 17:01
Да ладно smile не уметь не стыдно, стыдно не хотеть научиться.

Автор: km999 28.1.2011, 22:33
Спасибо всем за помощь. Разобрался с решением.

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

Цитата(dEvIllEssE @  27.1.2011,  16:24 Найти цитируемый пост)

Во-первых, просто построй хотя бы первые два десятка строк и посмотри на них попристальнее... сразу выяснится, что буквовка запросто определяется в зависимости от чётности номера строки и позиции символа в ней (длина периода 5 и 8 соответственно).

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

Автор: Akina 31.1.2011, 17:13
Цитата(km999 @  31.1.2011,  18:01 Найти цитируемый пост)
первые три буквы не меняются. Т.е. если строка четная, то - bca, если нечетная - abc. 

Я же сказал, что 
Цитата(Akina @  27.1.2011,  17:16 Найти цитируемый пост)
длина периода 5 и 8 соответственно

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

Автор: dEvIllEssE 3.2.2011, 14:07
Цитата(km999 @  31.1.2011,  17:01 Найти цитируемый пост)
Цитата(dEvIllEssE @  27.1.2011,  16:24 )
Во-первых, просто построй хотя бы первые два десятка строк и посмотри на них попристальнее... сразу выяснится, что буквовка запросто определяется в зависимости от чётности номера строки и позиции символа в ней (длина периода 5 и 8 соответственно).

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


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

Автор: Silent 4.2.2011, 10:06
Как указал тов. Akina, буква действительно неким "магическим" образом зависит от позиции в строке и номера строки  smile 

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. Вот такая реккурентная формула. Можно реализовать рекурсивно, можно циклом. Исходный код:
Код

#include <stdio.h>

int K,P;
const int f[44] = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733};

int main()
{
    scanf("%d %d",&K,&P);
    int i = 44;
    while (f[i-1] > P) i--;
    if ((K >= 45) || (i == 44)) 
        printf("No solution");
    else 
    {
        while (i > 2)
            if (P <= f[i-2]) 
                i -= 2;
            else 
            {
                P -= f[i-2];
                i--;
            }
        if (i == 1) printf("A");
        else    
            if  (P == 1) printf("B");
            else printf("C");
    }
    return 0;
}


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

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

Автор: Akina 4.2.2011, 10:42
Цитата(Silent @  4.2.2011,  11:06 Найти цитируемый пост)
Как указал тов. Akina, буква действительно неким "магическим" образом зависит от позиции в строке и номера строки  

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

Автор: km999 5.2.2011, 00:52
Добавлено @ 00:56
Цитата(Silent @ 4.2.2011,  10:06)
P.S. Где-то я эту задачу уже видел, на тимусе, что ли?

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


Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)