Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Tri2015

Задача Tri2015. Мешканці далекої  планети Трианглії вирішили побудувати новий вівтар у Храмі Священної Трійки. Вівтар повинен мати форму рівностороннього трикутника з довжиною сторони n см, і складеним з камінців у формі рівносторонніх трикутників з  стороною 1 см. При цьому n має бути степенем числа три: n = 3k (рис. 1).

 

Рис. 1. Приклад  вівтаря з довжиною сторони n=3см

 

Кожен з маленьких трикутників-камінців має бути пофарбованим в один з трьох кольорів: червоний, зелений чи синій. Для того, аби визначити колір кожного каменю майбутнього вівтаря, спочатку створюють допоміжний шар (фундамент) з n+1 каменів, по одному на кожного мешканця. Далі вівтар будується  пошарово - спочатку шар над фундаментом, потім другий шар, і так до самої вершини, дотримуючись двох правил:

   якщо кольори двох сусідніх трикутників внизу якогось трикутника різні, то цей трикутник має бути третього кольору;

   якщо колір двох сусідніх трикутників внизу співпадає, то цей же колір повинен мати і поточний трикутник.

Герой Трианглії Тривася Трипупкін спізнився на момент закладки фундаменту. Решта n  його друзів вже поклали свої камінці у фундамент, так що там залишилось місце лише для крайнього правого трикутника (синій камінець в фундаменті на рис. 1). Тривася хоче дізнатися, камінець якого кольору він має покласти у фундамент, аби вершина вівтаря була пофарбована в  зелений колір.

 

Технічні умови. Програма Tri2015 читає з пристрою стандартного введення ціле число  1 <= M <= 10 – кількість фундаментів. Далі програма читає з того ж  рядка через  пропуски М послідовностей символів  з множини {r,g,b}, що відображають  кольори камінців у майже готовому  фундаменті зліва   направо (у кожній послідовності символи записані без пропусків, кількість символів у кожній послідовності n = 3k, де k 10 , тобто n 59049).  Програма виводить на пристрій стандартного виведення  М підмножин множини {r,g,b}. Кожна підмножина  записана в вигляді одного або послідовності символів без пропусків. Послідовності розділено одним пропуском. Якщо Тривася не може отримати зелену вершину жодним  з способів, вивести єдиний символ n.

Приклад 

Введення 2 rgg ggrggrggr

Виведення: b g


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"