1. Код Грея (автор — Олександр Рудик)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: code.in
Вихідний файл: code.out
Програма: code.*

Кодом Грея називають непозиційну систему запису цілих натуральних чисел за допомогою двох символів 0 та 1 таким чином. Нуль кодують послідовністю нулів. При зростанні цілого числа:

• наймолодший 1-й розряд у послідовності символів змінюють у такій послідовності: 0, 1, після чого у наступний 2-й розряд записують 1, а наймолодший розряд змінюють уже у протилежному порядку;

• два наймолодші розряди змінюють у такому порядку: 00, 01, 11, 10, після чого у 3-й розряд записують 1, а два наймолодші розряди змінюють уже у протилежному порядку: 10, 11, 01, 00 …;

• k наймолодших розрядів змінюють у порядку, визначеному попередніми кроками, після чого у наступний (k + 1)-й розряд записують 1, а молодші розряди змінюють уже у протилежному порядку.

Коди Грея довжини 4 чисел від 0 до 15 включно такі (записано у порядку зростання числа): 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.

Коди Грея двох послідовних натуральних чисел відрізняються лише в одному розряді. Це використовують для збільшення надійності роботи системи оптичних фотодіодів при встановленні кута повороту дисків — носіїв інформації.

Завдання
Визначте код Грея натурального числа.

Вхідні дані
Вхідний файл містить лише десятковий запис натурального числа n при n < 10¹⁸.

Вихідні дані
Вихідний файл має містити код Грея числа n мінімальної довжини. Інакше кажучи, цей код має починатися з одиниці й містити j символів, де 2 ^j – 1 ≤ n < 2 ^j.

Приклади

2. Тетрис (автор — Андрій Гриненко)

Максимальна оцінка: 100 балів
Обмеження на час: 5 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: tetris.in
Вихідний файл: tetris.out
Програма: tetris.*

Розглянемо гру тетрис з такими правилами. На кожному кроці одна із зображених на рис 1. фігура падає в яму прямокутної форми ширини 10, якщо дивитися збоку. Довжини сторін усіх квадратів, з яких складаються фігури 1–7, дорівнюють 1.

Рис. 1. Фігури для гри тетрис.

Перед початком падіння і лише перед ним фігурку можна повернути на кут 0°, 90°, 180° або 270° за рухом годинникової стрілки..

Рис 2. Зліва направо подано результат обертання фігури 1
на 0°, 90°, 180° або 270° за рухом годинникової стрілки.

Після обертання (у тому числі на 0°) кожну фігуру можна рухати ліворуч, праворуч або вниз на одну клітинку. Таке переміщення дозволено лише, якщо при цьому ця фігура не перетне жодну з фігур, що вже лежать у ямі, і не перетне бокові або нижню стінки ями. Фігура може зупинитись лише тоді, коли хоча б одна з її клітинок своєю нижньою стороною торкається дна ями або фігури, яка вже лежить у ямі.

Завдання
Ваша програма має вказати, як потрібно остаточно розташувати фігури, що падають у яму, щоб зменшити різницю найбільшої висоти, на якій розташовані клітинки фігур у ямі, і кількості повністю заповнених рядків у ямі.

Вхідні дані
Перший рядок вхідного файлу містить одне натуральне число n — кількість фігур, що падатимуть у яму.

Другий рядок містить n чисел: f₁, f₂, …, f_n. Тут f_j — тип фігури (див. рис. 1), що впаде у яму на кроці j.

На відміну від решти задач і вперше на ІІІ етапі у м. Києві, зі вмістом усіх вхідних файлів до даної задачі можна ознайомитися під час виконання завдання:

1. Скопіюйте файл D:\Olimp\Doc\tetris.exe у теку D:\Olimp\Work.
2. Запустіть на виконання tetris.exe у теці D:\Olimp\Work.
3. Введіть пароль «tet2ris» і завершіть розгортання rar-архіву.

Вихідні дані
Вихідний файл має містити n трійок невід’ємних цілих чисел, α_j, x_j і y_j, де:
α_j — градусна міра кута, на який потрібно повернути j-ту у порядку падіння фігуру (0°, 90°, 180° або 270° за рухом годинникової стрілки);
x_j — відстань до фігури від лівого краю ями після усіх переміщень;
y_j — відстань до фігури від дна ями після усіх переміщень.

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

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

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

Рис. 3. Остаточне розташування фігур для поданого прикладу вхідних та вихідних даних. Досягнення учасника становитиме 2 = 3 – 1, бо h_max = 3, r = 1.

3. Військові навчання (автор — Ярослав Твердохліб)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 64 MБ
Вхідний файл: відсутній
Вихідний файл: відсутній
Програма: military.*

Маленький Петрик в дитинстві дуже любив грати у солдатів. Тепер він виріс і став генералом. Нещодавно йому доручили керувати військовими навчаннями. Під час навчань він із допомогою рації дає солдатам команди, які ті виконують і одразу ж доповідають йому про результат.

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

1. Висадити солдата у точку з координатами (x, y) та надати йому номер s;

2. Відкликати солдата з номером s, якщо такий є на полігоні;

3. Визначити кількість солдатів, які перебувають на відстані від точки (x, y), що не перевищує d.

При цьому відстанню між точками (x₁, y₁) та (x₂, y₂) називають таку суму:

Завдання
Напишіть програму military.*, яка б реалізувала таке:

1. Процедуру addSoldier, яку мовами Pascal або C++ потрібно оголосити так:

   procedure addSoldier(x,y,s:longint);
   void addSoldier(int x,y,s);

   При кожному виклику цієї процедури ваша програма має додавати солдата у точку з координатами (x,  y) та надавати йому номер s. Гарантовано, що у цей час солдата з таким номером не буде на полігоні.

2. Функцію removeSoldier, яку мовами Pascal або C++ потрібно оголосити так:

   function removeSoldier(s:longint):longint;
   int removeSoldier(int s);

   При кожному виклику цієї функції ваша програма має видалити солдата з номером s з полігона та повернути 1, якщо солдат з таким номером був на полігоні до виклику функції, або повернути 0 без виконання жодних дій, якщо такого солдата не було.

3. Функцію query, яку мовами Pascal або С++ потрібно оголосити так:

   function query(x,y,d:longint):longint;
   int query(int x,y,d);

   При кожному виклику цієї функції ваша програма має порахувати кількість солдат, що перебувають на відстані від точки (x, y), що не перевищує d, і повернути цю кількість.

Нижче подано приклади реалізації програм мовами C++ і Pascal.

/* GCC */
#include <algorithm>
#include <iostream>
using namespace std;

bool was[50001];
void addSoldier(int x,int y,int s)
{
	was[s]=true;
}
int removeSoldier(int s)
{
	int ret=0;
	if (was[s]) ret=1;
	was[s]=0;
	return ret;
}
int query(int x,int y,int d)
{
	return 1;
}

{ Free Pascal }
unit military;

interface

	procedure addSoldier(x,y,s:longint);
	function removeSoldier(s:longint):longint;
	function query(x,y,d:longint):longint;

implementation
	var
	was:array[1..50000] of boolean;
	procedure addSoldier(x,y,s:longint);
	begin
		was[s]:=true;
	end;
	
	function removeSoldier(s:longint):longint;
	var ret:longint;
	begin
		if (was[s]=true) then ret:=1 else
		ret:=0;
		was[s]:=false;
		removeSoldier:=ret;
	end;

	function query(x,y,d:longint):longint;
	begin
		query:=1;
	end;
end.

У поданих кодах масив was створено для того, щоб нагадати учасникам, яким чином і в якому місці коду потрібно запроваджувати змінні, які потім можна використовувати. Створення саме такого масиву не є обов’язковим, тоді як функції і процедуру потрібно назвати саме так, як це вказано в умові.

Обмеження на параметри. Загальна кількість викликів усіх процедур не перевищує 50 000. В усіх викликах процедур аргументи та d не перевищують за модулем 300, 0 ≤ d, аргумент s не перевищуватиме 50 000, 0 < s.

Інтерактивність. Результат компіляції вашого коду буде підключено як модуль до програми перевірки, що буде здійснювати взаємодію з системою тестування й викликати згадану процедуру addSoldier та функції removeSoldier та query. Будь-які дані можуть бути введені або виведені лише через програму grader.*. Цю програму Вам здавати не потрібно. Її для перевірки надасть журі. Код учасника не має містити звертання до будь-яких файлів.

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

Компіляція. Під час перевірки буде використано лише такі компілятори: Free Pascal 2.2.2, Turbo Delphi Explorer 2006, Dev C++ 4.9.9.2 разом з Mingw/GCC 3.4.2 і Visual C++ 2008 Express Edition:

• для того, щоб скомпілювати розв’язання за допомогою Visual Studio, GNU C++ або Turbo Delphi, потрібно створити проект, у який додати файли grader.*, military.* (у випадку C++ треба ще military.h), виділити grader.* і провести компіляцію;

• для того, щоб скомпілювати розв’язання за допомогою Free Pascal, потрібно скомпілювати grader.pas, причому military.pas має лежати у тій самій теці.

При тестуванні компілятори Turbo C і Turbo Pascal не буде використано, бо вони не забезпечують доступ до відповідного обсягу пам’яті. Їх можна використовувати під час виконання завдання. Потім потрібно змінити замовлення компілятора на { Free Pascal } або /* GCC */ і переконатися, що у відповідних середовищах програмування програму можна скомпілювати й запустити на виконання.

Приклади реалізації можна отримати таким чином:

1. Скопіюйте файл D:\Olimp\Doc\military.exe у теку D:\Olimp\Work.
2. Запустіть на виконання military.exe у теці D:\Olimp\Work.
3. Введіть пароль «mili2011tary» і завершіть розгортання rar-архіву.

Для перевірки на тесті, відмінному від запропонованого в архіві, потрібно змінити вміст military.in, скомпілювати та запустити grader.*, що міститься у згаданому архіві military.exe. Результат виконання програми буде записано у файл military.out.

Формат наданого в архіві файлу military.in такий. Перший рядок містить число N — кількість запитів. Кожний з наступних N рядків починається з числа 1, 2 або 3 — типу запиту:

• якщо перше число 1, то слідом йдуть три цілих числа x, y, s — параметри addSoldier;

• якщо перше число 2, то слідом йде одне ціле число s — параметр removeSoldier;

• якщо перше число 3, то слідом йде три цілих числа x, y, d — параметри query.

Формат наданого в архіві або створеного grader.* файлу military.out такий:

• файл містить N рядків;

• j-ий рядок відповідає запиту j вхідного файлу. Усі рядки, що відповідають запитам першого типу, порожні, а інші містять результати виконання процедур (описано вище).

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

4. Парність (автор — Олександр Рудик)

Максимальна оцінка: 100 балів
Обмеження на час: 6 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: oddeven.in
Вихідний файл: oddeven.out
Програма: oddeven.*

Нехай n — довільне натуральне число, а послідовність i₁, i₂, …, i_n містить усі натуральні числа від 1 до n включно. Порушенням порядку у такій послідовності називають систему таких двох нерівностей, що справджуються: j < k та i_j > i_k. Якщо послідовність зростає, то кількість порушень порядку дорівнює 0. Якщо послідовність спадає, то така кількість дорівнює n(n – 1)/2. В усіх інших випадках ця кількість розташована між вказаними величинами.

Завдання
Встановіть парність кількості порушень порядку послідовності.

Вхідні дані
У першому рядку вхідного файлу вказано кількість послідовностей m. Кожний з наступних m рядків містить натуральне число n і послідовність різних натуральних чисел від 1 до n включно: i₁, i₂, …, i_n при 2 ≤ m ≤ 16, 2 ≤ n ≤ 1 048 576. У 50% тестів n ≤ 4096.

Вихідні дані
Єдиний рядок вихідного файлу має містити m символів — нулів або одиниць — без пропусків: k-й символ рядка — це залишок від ділення на 2 кількості порушень порядку k-ї послідовності, заданої (k + 1)-м рядком вхідного файлу.

Приклад

5. Фарбована сума (автор — Данило Мисак)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 MБ
Вхідний файл: sum.in
Вихідний файл: sum.out
Програма: sum.*

Фарбованою сумою n натуральних чисел («фарбованих доданків») a₁, a₂, …, a_n назвемо натуральне число s, яке задовольняє такі умови:

1. Цифри числа s можна розфарбувати в n різних кольорів так, що коли в ньому залишити цифри лише i-го кольору, ми отримаємо десятковий запис числа a_i, 1 ≤ i ≤ n.

2. s — найбільше з усіх натуральних чисел, що задовольняють умову 1.

Зрозуміло, що для довільного набору фарбованих доданків a₁, a₂, …, a_n існують числа, які задовольняють першу умову. Наприклад, таким буде число, що утворене шляхом приписування всіх доданків один до одного. Чисел, що задовольняють першу умову, скінченна кількість, тому серед них існує найбільше. Отже, фарбована сума завжди існує та визначена однозначно. Як видно з означення, вона не залежить від порядку доданків.

Завдання
Знайдіть фарбовану суму n заданих натуральних чисел.

Вхідні дані
У першому рядку вхідного файла вказано кількість фарбованих доданків n, 2 ≤ n ≤ 10⁵.

У другому рядку задано n фарбованих доданків, розділених символами пропуску. Кожен доданок — натуральне число, менше за 10⁹.

У 50% тестів до цієї задачі n ≤ 1000, а у 25% усіх тестів n ≤ 3.

Вихідні дані
Вихідний файл повинен містити єдине натуральне число — фарбовану суму вказаних у вхідному файлі доданків.

Приклади

6. Розклад уроків (автор — Олександр Рибак)

Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам’ять: 32 Mб
Вхідний файл: schedule.in
Вихідний файл: schedule.out
Програма: schedule.*

Уявіть, що Вам потрібно скласти розклад уроків на тиждень. Для кожного класу відомо, які предмети мають викладати у цьому класі та скільки уроків припадає на кожен предмет. Кожний предмет викладає лише один учитель, тому уроки з одного предмета не можуть бути у двох класах одночасно. Уроки мають суцільну нумерацію: наприклад, якщо у школі щодня буває не більше за 7 уроків, то перший урок вівторка має номер 8, другий урок вівторка — номер 9 і т. д. Уроки з одним і тим самим номером проходять для всіх класів у один і той самий час. У розкладі допускають «вікна» — випадки, коли один або декілька уроків пропускають, а перед цим і після цього уроки проводять.

Завдання
Подайте приклад потрібного розкладу або вкажіть, що розв’язку немає.

Вхідні дані
Перший рядок вхідного файлу містить у вказаному порядку цілі числа N (1 ≤ N ≤ 50) та T (1 ≤ T ≤ 50), де N — кількість класів, а T — максимально можлива кількість уроків протягом тижня. Кожний з наступних N рядків задає перелік предметів, уроки з яких потрібно проводити у відповідному класі (по рядку на клас). У кожному такому рядку записано T невід’ємних цілих чисел:

• кожен предмет позначено деяким натуральним числом від 1 до 50 (ця нумерація спільна для всіх рядків);

• номер кожного предмета зустрічається у рядку стільки разів, скільки уроків протягом тижня припадає на цей предмет у відповідному класі;

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

Позначимо через Q(i, j) кількість чисел, які дорівнюють j й розташовані у рядку, що задає перелік предметів для i-го класу (1 ≤ i ≤ N). При 1 ≤ j ≤ 50 справджується така нерівність:

Інакше кажучи, розклад потрібно скласти за умови, що кожному вчителю призначено провести протягом тижня не більше ніж T уроків.

Вихідні дані
Вихідний файл має містити N рядків по Т чисел. Для k = 1, 2, …, N у k-му рядку вихідного файлу має бути заданий розклад для класу, описаного (k + 1)-м рядком вхідного файлу. Кожне число у k-му рядку вихідного файлу має траплятися стільки разів, скільки воно трапилося у (k + 1)-му рядку вхідного файлу. При кожному j (1 ≤ j ≤ T) на j-х місцях різних рядків не може бути однакових додатних чисел — нулів це не стосується. Якщо шуканих розкладів багато, подайте будь-який з них. Якщо потрібного розкладу немає, виведіть число –1.

Приклади