1. Нова пошта, 10 балів
Містечко Друатвіль (французькою droite — пряма, ville — місто) розташоване у гірській ущелині вздовж шляху, навколо якого майже непрохідні гори. Мешканці містечка задумали побудувати нове приміщення пошти таким чином, щоб якнайменше стоптувати черевики. Створіть програму droite.* , яка визначить місце розташування нового приміщення пошти, для якого сума добутків відстаней від пошти до осель вздовж шляху на кількість мешканців цих осель найменша.

Вхідний файл droite.dat у першому рядку містить натуральне число n — кількість осель у місті.

Для k в межах від 1 до n включно (k+1)-ий рядок цього файлу містить (у вказаному порядку) два натуральних числа:
x_k — відстань від пам'ятного знаку на в'їзді у місто до k-ої оселі;
m_k — кількість її мешканців.

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

3
10 3
20 2
30 3

Вихідний файл droite.res має містити відповідь українською мовою (чи мовою навчання, граматичні помилки та літературний стиль на кількість балів не впливають). Наприклад,

Шукане місце - за 20 кроків від знаку.

2. Сновида, 10 балів
У президента Першого національного банку майора Томаса Б. Кінґмена (героя оповідання О'Генрі «Товариші із Сан-Розаріо») з'явилася звичка вночі перекладати вміст сейфів, у яких клієнти зберігають свої коштовності. Створіть програму sleep.*, яка допоможе вирахувати, через скільки діб всі коштовності вперше повернуться на свої місця, якщо щоночі майор Кінґмен перекладатиме вміст сейфів однаковим чином, а десятковий запис шуканого числа містить не більше 80-ти цифр.

Перший рядок вхідного файлу sleep.dat містить одне натуральне число n — кількість сейфів банку, що неперевищує 600. Другий рядок цього самого файлу містить послідовність n різних натуральних чисел в межах від 1 до n включно. k-ий член цієї послідовності — номер сейфу, куди майор перекладає вміст k-го сейфу першої ночі. Наприклад,

5
2 3 1 5 4

Єдиний рядок вихідного файлу sleep.res має містити запис у десятковій системі числення шуканого числа діб (починаючи з першої позиції). Наприклад,

6

3. Гроші на шахівниці, 10 балів
На кожній клітинці шахівниці розміру m на n клітин випадковим чином розкладено монети, загальна вартість яких не перевищує $3333. Пішак рухається або праворуч, або вгору (на одне поле за один хід) від нижнього лівого поля до верхнього правого. З усіх клітин, на яких побував пішак, знімають монети. Створіть програму money.*, яка допоможе таким чином зібрати найбільшу кількість монет.

Перший рядок вхідного файлу money.dat містить у вказаному порядку натуральні числа m і n, менші за 22. Для j у межах від 1 до m включно (j + 1)-ий рядок цього самого файлу містить сукупні вартості монет у клітинках j-го рядка шахівниці, якщо рахувати рядки згори донизу, у тому ж порядку, як вони (клітинки цього рядка) розташовані на шахівниці. Наприклад,

2 3
1 2 3
6 8 2

Перший рядок вихідного файлу money.res має містити найбільшу кількість монет, яку можна зібрати таким чином. Наступний рядок цього самого файлу містить (n + m – 2) символи, що описують напрям ходів пішака (від першого до останнього):
u — вгору (від анґлійського up),
r — праворуч (від анґлійського right), які дають можливість зібрати найбільше грошей, і в якій хід праворуч здійснюється якомога пізніше на кожній ділянці шляху. Наприклад,

19
rur

1. Мотель, 60 балів.
Рівнину перетинають швидкісні автостради. Створіть програму motel.*, яка вибере найвигідніше місце для мотелю, від якого сума відстаней до всіх автострад найменша.

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

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

2
0 0 4 3
1 1 0 1

Кількість прямих n лежить в межах від 2 до 10, а всі інші числа вхідного файлу motel.dat не перевищують 123.

Перший рядок вихідного файлу motel.res має містити найменшу можливу суму відстаней від автострад до мотелю. Наступні рядки цього самого файлу мають містити відповідь українською мовою чи мовою навчання (орфографічні помилки та літературний стиль на кількість балів не впливають) на питання про множину точок оптимального розташування мотелю. Шукану множину треба подати об'єднанням якомога меншої кількості лінійно зв'язних фіґур (фіґуру називають лінійно зв'язною, якщо будь-які дві її точки можна з'єднати неперервною прямою, кожна точка якої належить цій фіґурі). Наприклад,

0
Шукана множина містить єдину точку (4/3;1).

Будь-яке число у відповіді треба подати нескоротним дробом з цілим чисельником і натуральним знаменником, розділеними знаком ділення /. Якщо знаменник дорівнює 1, то знак ділення і знаменник не записувати.

2. Латиниця, 30 балів.
Латиниця (латинська абетка) має 26 літер: a b c d e f g h i j k l m n o p q r s t u v w x y z (вказано в алфавітному порядку).

Перший рядок вхідного файлу latin.dat містить у вказаному порядку два натуральних числа k та l, де k < 26, l < 255.

Другий рядок цього самого файлу містить послідовність k літер латиниці (використано лише малі літери) без прогалин між літерами. Наприклад,

4 3
bcdx

Створіть програму latin.*, яка у вихідний файл latin.res записує в алфавітному порядку l «слів» по k літер у кожному — послідовностей по k літер латиниці, в яких:

• не зустрічається літера a;
• жодна літера не повторюється;
• всі літери зустрічаються у тому порядку (при зчитуванні зліва направо), як і в абетці.

Кожен рядок файлу latin.res має містити лише одне таке «слово». При цьому неможливо вставити ніяке інше слово з переліченими властивостями:

• між послідовними «словами» файлу latin.res;
• між єдиним «словом» файлу latin.dat і першим «словом» файлу latin.res,

не порушивши алфавітного порядку. Для поданого раніше файлу latin.dat файл latin.res має такий вигляд:

bcdy
bcdz
bcef

Якщо таких «слів» менше, ніж l, то записуються всі можливі такі «слова».

Якщо таких «слів» немає взагалі, то в єдиний рядок файлу latin.res потрібно записати повідомлення

Таких слів немає!

Наприклад, це потрібно зробити, коли latin.dat має вигляд

4 5
xbcd

3. Тест, 60 балів.
У дитячому садку проводиться тестування. Дітям показують білі аркуші паперу прямокутної форми, які поділено на рівні квадрати горизонтальними та вертикальними лініями. Частину квадратів зафарбовано чорною фарбою, а частину — ні. Фіґурою на такому малюнку називають сукупність чорних квадратів, для довільної пари яких центри квадратів можна з'єднати ламаною, що повністю міститься у чорних квадратах і не містить жодної вершини квадрата. Різними фіґурами називаються фіґури, які неможливо сумістити послідовним застосуванням паралельних переносів, поворотів на 90° і симетрії відносно вертикальної чи горизонтальної прямої. Дітям пропонують встановити, скільки всього фіґур зображено на малюнку, і скільки різних фіґур зображено на цьому самому малюнку.

Створіть програму test.*, яка дає правильну відповідь на поставлене питання.

Перший рядок вхідного файлу test.dat містить (у вказаному порядку) два натуральних числа m і n, які не перевищують 60 — кількості квадратів, які розташовані на малюнку по вертикалі та горизонталі відповідно. Наступні m рядків по n символів цього ж файлу містять подання малюнку, в якому символ « » (пропуск) означає білий квадрат, а «Ш» — чорний. Наприклад,

5 9
ШШ  ШШ ШШ
Ш Ш  Ш  Ш
  ШШ     
Ш     Ш Ш
Ш Ш Ш Ш Ш

Єдиний рядок вихідного файлу test.res має містити у вказаному порядку два натуральних числа: кількість всіх фіґур та кількість різних фіґур. Відомо, що обидва шуканих числа не перевищують 127. Для поданого раніше файлу test.dat файл test.res має такий вигляд:

9 3