|
Цветочки
(Время: 1 сек. Память: 16 Мб Сложность: 12%)
Одним из вариантов решения данной задачи является моделирование процесса обмена цветков. Если в некоторую строку s мы сначала запишем первоначальное расположение цветоков в виде ‘GCV’, то в дальнейшем для очередной дневной перестановки нам следует сначала поменять символы s[2] и s[3] (цветок справа и центральный цветок – операция под кодовым названием «Маша»), а затем поменять символы s[1] и s[2] (цветок слева и центральный цветок – операция под кодовым названием «Таня»). Если мы такую процедуру выполним K раз, то в итоге в строке s получим искомый ответ. Такое решение достаточно простое и понятное, но не самое быстрое и короткое.
Другой подход основывается на поиске закономерности. Если выписать первые расстановки цветков для нескольких дней, то мы получим последовательность «VGC», «CVG», «GCV», «VGC», «CVG», «GCV», «VGC», «CVG» … Откуда видно, что период данной последовательности равен трем и ответ можно формировать по значению K mod 3. Таким образом, алгоритм решения возможно представить следующим образом:
read(k)
if(k mod 3=0) write('GCV')
if(k mod 3=1) write('VGC')
if(k mod 3=2) write('CVG')
| |
