Турніри Школи Олімпійського Резерву "Step by Step"

Рекомендуємо ознайомитися з правилами участі у турнірах Школи Олімпійського Резерву "Step by Step"
Рейтинг учасників турнірів

ZOI-2009 Тур-3
класифікація: "medium"
дата старту: 2009-11-12
дата завершення: 2009-11-22
турнір проводить: Зубик В.В.
к-ть учасників:  136 
результати турніру

опис турніру:

Задачі третього туру Хмельницької заочної олімпіади з програмування.

Завдання на турнір >>
задача 1. "T3Z1"
кількість балів: 33

Game
Ліміт часу: 300мс
Ліміт пам'яті: 32 Мбт

Вовочка любить на уроках математики грати різні інтелектуальні ігри – не байдикувати ж зовсім. Недавно він захопився такою простою грою. Спочатку для гри вибирає деяке натуральне число N і малює на папері кружечок. Потім малює ще один і з’єднує його з першим лінією. Після цього малює наступний кружечок і з’єднує його з одним із попередніх. Так він робить до тих пір, поки на листку не буде рівно N кружечків. Свої кружечки Вовочка нумерує в довільному порядку числами від 1 до N. Складіть програму, що визначить скільки різних малюнків може зробити Вовочка для вибраного N. Малюнки вважаються різними, якщо існують такі кружечки з номерами i та j, що на одному малюнку вони з’єднанні, а на іншому – ні.

Формат вхідних даних. У першому рядку вхідного файлу game.in міститься K (0<K<=10) – кількість тестів. Наступні K рядків містять натуральне число N (0<N<=100) для кожного тесту.

Формат вихідних даних. Для кожного тесту у вихідний файл game.out вивести залишок від ділення кількості різних малюнків на число 2000000011.

Приклад вхідних та вихідних даних.
game.in
3
1
2
3

game.out
1
1
3

 

задача 2. "T3Z2"
кількість балів: 34

Cubes
Ліміт часу: 200мс
Ліміт пам'яті: 32 Мбт

У дитячому садку Вовочка любив складати із кубиків вежі. Кубики у нього були такі, що кожна грань мала свій оригінальний колір. Вовочка клав кубик на кубик так, щоб кожна бічна грань його побудованої вежі була одного кольору. Зрозуміло, що кожного разу він міг скласти вежу різної висоти в залежності від того, які кольори для граней він вибирав. Цікаво, - подумав Вовочка, - а яку ж найбільшу вежу можна скласти з цих кубиків? Задачка виявилася не дуже простою. Попробуйте скласти програму, що визначить максимальну висоту вежі, побудованої за описаними правилами, якщо ребро кубика рівне 1.

Формат вхідних даних. Перший рядок вхідного файлу cubes.in містить натуральне число N (1<N<=1000) – кількість кубиків у наборі Вовочки. Дальше у наступних N рядках описані кольори граней кожного кубика за допомогою шести великих літер латинського алфавіту, що позначають відповідний колір (A - Azure Blue, B - Blue, C - Cyan, G - Green, O - Orange, R - Red, S - Sun Yellow, V - Violet, W - White, Y - Yellow). Грані кубика ідуть у наступному порядку: передня, права, ліва, задня, верхня, нижня.

Формат вихідних даних. У вихідний файл cubes.out вивести найбільшу висоту вежі, що може бути побудована за описаними правилами з кубиків Вовочки.

Приклад вхідних та вихідних даних.
cubes.in
4
GYVABW
AOCGYV
CABVGO
OVYWGA

cubes.out
3

 

задача 3. "T3Z3"
кількість балів: 33

Decoder
Ліміт часу: 300мс
Ліміт пам'яті: 32 Мбт

Вовочка з Васильком жили в різних будинках і під час осінніх канікул, що дорослі їх назвали Карантином, придумували собі різні забави. Пропоную вашій увазі одну з них. Вовочка відправляє Васильку SMS із словом, що складається з N символів. Василько здійснює над словом X (0<=X<N) циклічних зсувів (циклічний зсув – це коли останній символ переходить на місце першого) і відправляє слово назад до Вовочки. Вовочка повинен визначити скільки циклічних зсувів зробив Василько або чи зробив він помилку при виконанні зсувів. При невеликих словах ця гра була досить простою, але із збільшенням кількості символів її складність зросла.

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

Формат вхідних даних. У першому рядку вхідного файлу decoder.in міститься натуральне число N (1 <= N <= 250000) – кількість символів у слові. Другий рядок містить перше слово. Третій рядок містить слово, що було отримане в результаті циклічних зсувів. Слова складаються із символів таблиці ASCII з кодами від 33 до 255.

Формат вихідних даних. У вихідний файл decoder.out вивести найменшу кількість циклічних зсувів, що їх треба зробити для того, щоб із першого слова отримати друге або «-1» без лапок у випадку, коли це зробити неможливо.

Приклад вхідних та вихідних даних.
decoder.in
8
karantyn
tynkaran

decoder.out
3

 


назад у розділ "Турніри"