Завдання № 7 відбірково-тренувальних зборів команди міста Києва

Завдання № 7
відбірково-тренувальних зборів
команди міста Києва

1. Многоґранник

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

Поверхню многогранника можна неперервно i взаємно однозначно вiдобразити на сферу.

Завдання
Створiть програму, яка визначить, скільки граней з певною кількістю сторін має многогранник.

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

Вiдомо, що:

вершин не бiльше, нiж 2000;
ребер не бiльше, нiж 4000;
лише в однiй гранi кiлькiсть ребер перевищує 8.

Вихідні дані
Кожний рядок вихiдного файлу має містити перелік номерів вершин однієї грані многогранника.
Усі можливі різні такі рядки потрібно розташувати у порядку неспадання кількості вершин грані: спочатку розташовують інформацію щодо усіх 3-кутних граней, потім — 4-кутних граней, потім — 5-кутних і т.і.
Для сталої кількості вершин грані переліки номерів вершин i₁, i₂, i₃, … потрібно розташувати у порядку неспадання i₁, при сталому i₁ — у порядку неспадання i₂, при сталих i₁ та i₂ — у порядку зростання i₃.

Приклад (тетраедр)

solid.in	solid.out
`4 2 3 4 1 3 4 1 2 4 1 2 3`	`1 2 3 1 2 4 1 3 4 2 3 4`

2. Приватні інтереси

Максимальна оцінка: 20 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 4 MБ
Вхідний файл: privat.in
Вихідний файл: privat.out
Програма: privat.*

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

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

Завдання
Створіть програму privat.*, яка передбачить результат гри та рух пішака.

Вхідні дані
Перший рядок файлу privat.dat містить у вказаному порядку натуральні числа m та n.

Для j в межах від 1 до m включно (j + 1)-ий рядок цього ж файлу містить невід'ємні цілі числа — сукупні вартості монет у клітинках j-го рядка таблиці в тому порядку, як вони (клітинки цього рядка) розташовані в таблиці зліва направо. Кількість всіх чисел файлу не перевищує 12346, максимальний виграш не перевищує 65432 (золотих).

Вихідні дані
Перший рядок вихідного файлу privat.res має містити два невід'ємних цілих числа — виграші (кількості зібраних монет) першого та другого гравців відповідно.

Другий рядок цього самого файлу має містити послідовність символів, що описують напрям ходів пішака (від першого до останнього) для досягнення цього результату: u — вгору (від анґлійського up), r — праворуч (від анґлійського right).

Приклад

privat.in	privat.out
`4 4 1 1 2 0 3 7 8 9 3 0 7 1 0 3 3 1`	`19 11 uurrr`