2liga_final_2013

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

.

Задача K. Загадка стародавнього племені

Подорожуючи Бразилією та дивлячись на те, як країна готується до чемпіонату світу з футболу 2014 року, наші герої цікавилися і історією цієї дивовижної країни. У одному місті вони відвідали музей стародавніх племен, де їх увагу привернув наскельний напис. За словами екскурсовода, у стародавніх племен існувало повір'я, яке свідчило: "Чим більше разів напишеш підряд у рядку ім'я бога, тим більше проживеш". На жаль до наших часів дійшов тільки фрагмент такого напису. Пана Коцького зацікавило питання – яке мінімальне за довжиною ім'я написане і повторювалось на цьому наскельному написі? Допоможіть знайти відповідь на це питання.

Формат вхідних даних

У першій і єдиному рядку вхідного файлу наведено рядок (фрагмент напису, що дійшов до нашого часу), який містить тільки латинські літери, довжина рядка не перевищує 50 000 символів.

Формат вихідних даних

У вихідний файл виведіть одне число – мінімально можливу довжину початкового імені, яке повторювалось на наскельному написі.

Приклад:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача L. Свято Фарби

Подорожуючи Південною Америкою, наші герої заїхали у державу Кольоровію, де саме святкували свято Фарби. На честь свята мешканці завжди проводили змагання на біговій доріжці стадіону, яку перед цим фарбували різними кольорами. У процесі фарбування приймали участь N малярів і кожний з них фарбував своїм кольором, відмінним від іншого. Крім того кожний маляр знав який відрізок бігової доріжки він повинен пофарбувати. Але, оскільки процес фарбування проходив послідовно, то деякі ділянки бігової доріжки перефарбовувалися. Трохи поміркувавши Котигорошко знайшов таку послідовність роботи малярів, за якої, після закінчення усього процесу фарбування, кількість різних кольорів на доріжці буде максимальним.

Cпробуйте і Ви це зробити.

Формат вхідних даних

Перший рядок містить ціле число N (1 ≤ N ≤ 300). Наступні N рядків містять по два

цілих числа через пробіл. У -ому з цих рядків знаходяться числа Lі та Rі (–109 ≤ Lі < Rі ≤ 109),

де Lі – початкова координата фарбування -ої ділянки;

Rі – кінцева координата фарбування -ої ділянки.

Формат вихідних даних

Упершому рядку треба вивести максимальну кількість кольорів, що буде видно на доріжці при оптимальному порядку фарбування.

Удругому рядку повинно бути написано N чисел – -е число позначає, який відрізок

треба намалювати -им для досягнення оптимального результату.

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

Примітка. За наявності декількох рішень вивести будь -яке з них.

Приклад:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача M. Щасливий білет

Пересуваючись громадським транспортом у Кольоровії, наші герої помітили одну особливість – усі білети мали номери, що складалися тільки з нулів та одиниць, а щасливим вважався білет, що не мав у номері трьох підряд розташованих нулів. Пана Коцького зацікавило питання – якщо номер білета має N цифр, то яким буде номер К-го щасливого білета?

Формат вхідних даних

У першому рядку вхідного файлу записана кількість тестів T (1 ≤ T ≤ 10 000). Наступні T рядків містять самі тести. Кожен тест складається з двох цілих чисел — N

(1 ≤ N ≤ 50) та K.

Формат вихідних даних

Для кожного тесту вивести K-ту у лексикографічному порядку щасливу послідовність довжини N. Гарантується, що кількість щасливих послідовностей не менше K.

Приклади:

Всеукраїнська студентська олімпіада з програмування

ФІНАЛ. Харків

24-27 жовтня 2013

Задача N. Транспортна стрічка

Закінчивши свою подорож, наші герої приїхали у міжнародний аеропорт столиці Кольоровії, де чекали свого рейсу до України. Оскільки часу у них було вдосталь, вони піднялися на оглядовий майданчик аеровокзалу, де з цікавістю спостерігали за процесом розвантаження літака, що саме приземлився. Цікавість у них викликала та обставина, що від дверей літака до дверей приймального відділення вантажів, відстань між якими дорівнювала L метрів, співробітники аеропорту спорудили автоматичну транспорту стрічку довжини L, яка формувалася з двох типів блоків різної довжини – X та Y метрів.

Котигорошка зацікавило питання – "Скільки блоків кожного виду треба використати для формування автоматичної транспортної стрічки, щоб їх загальна кількість була найменшою?". Допоможіть Котигорошку у вирішенні цього питання.

Формат вхідних даних

У першому рядку вхідного файлу записані два числа X та Y – довжина блоків, задана з двома десятковими знаками (0,01 ≤ X, Y ≤ 25.00).

Другий рядок містить одне число L (0,01 ≤ L ≤ 109) – відстань від дверей літака до дверей приймального відділення вантажів з двома десятковими знаками.

Формат вихідних даних

В єдиному рядку вивести через пробіл два числа: кількість блоків першого типу, кількість блоків другого типу. Якщо транспорту стрічку, що точно вписується у означену відстань, зробити неможливо – вивести одне число 0.

Приклади: