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

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

ZOI-2009 Тур-5
класифікація: "medium"
дата старту: 2009-12-10
дата завершення: 2009-12-20
турнір проводить: Мельник В.І.
к-ть учасників:  132 
результати турніру

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

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

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

Цікаві числа

Ім’я вхідного файлу: interest.in
Ім’я вихідного файлу: interest.out
Максимальний час роботи на одному тесті: 300 ms
Максимальний об’єм використаної пам’яті: 64 мегабайта
Максимальна оцінка за задачу: 20 балів

Існують натуральні числа, що закінчуються цифрою N, такі, що перенесення цифри N на початок числа приводить до збільшення числа в N разів.
Наприклад, число 102564, N=4, 410256=102564*4.

Формат вхідних даних: у єдиному рядку вхідного файлу задано натуральне число N (2<=N<=9).

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

Приклад вхідних та вихідних даних:

interest.in interest.out
4 102564

 

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

Дивні числа

Ім’я вхідного файлу: strange.in
Ім’я вихідного файлу: strange.out
Максимальний час роботи на одному тесті: 600 ms
Максимальна оцінка за задачу: 30 балів

Вася називає число дивним, якщо кількість його дільників непарна, наприклад число 4 – дивне, воно має 3 дільники: 1,2,4. Задано список чисел, Вася хоче знайти кількість дивних чисел у ньому. Так як Вася не вміє програмувати, то це завдання було доручене Вам.

Формат вхідних даних: у першому рядку вхідного файлу заданий розмір списку – натуральне число N (1<=N<=100). У наступних N рядках записані натуральні числа без ведучих нулів, які не перевищують 10^20.

Формат вихідних даних: єдиний рядок вихідного файлу повинен містити одне число - кількість дивних чисел у заданому списку.

Приклад вхідних та вихідних даних:

strange.in strange.out
5
1
4
13
160
170
2
задача 3. "T5Z3"
кількість балів: 50

Прогулянка по місту

Ім’я вхідного файлу: travel.in
Ім’я вихідного файлу: travel.out
Максимальний час роботи на одному тесті: 800 ms
Максимальна оцінка за задачу: 50 балів

У Кракові, недалеко від берега Вісли стоїть Дракон: кам’яний, з пухирчастим тілом, величезними лапами, до неба піднятою головою. Місто Краків – улюблене місто туристів, які з’їжджаються сюди звідусіль. Петрик – один із них. Карта Кракова являє собою таблицю, розміром NxM, клітинками якої є квартали, деякі з яких доступні для руху, а деякі ні. Також на карті відмічені цікаві місця, причому це також квартали, по яких можливий рух. Вася вибрав маршрут для ознайомлення з містом. Він почне з клітинки (1;1), прийде в клітинку (N;M), а потім знову повернеться туди звідки прийшов (в клітинку (1;1)). Звичайно, Петрик хоче переглянути якнайбільше різних цікавих місць. Так як Петрик знає Краків дуже погано, та й взагалі заблукати тут дуже небажано, він вирішив, що на шляху до клітинки (N;M) буде завжди іти вправо, або вниз (відносно карти), а на зворотнім – вліво, або вверх. Допоможіть Петрикові знайти максимальну кількість різних цікавих місць, в яких він може побувати.


Формат вхідних даних: у першому рядку вхідного файлу міститься два числа – N та M (1<=N,M<=100). В наступних N рядках міститься опис карти – рядок з M літер, причому “#” означає квартал недоступний для руху, “*” – місце для перегляду, а “.” (точка) – квартал доступний для руху, який слугує Васі лише клітинкою для руху. Гарантується, що клітинки (1;1) й (N;M) не будуть позначені символом “#”.


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


Приклад файлів вхідних і вихідних даних:

string.in string.out
4 5
**.*.
..##.
*#*..
*.*.*
7

 


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