Всеукраїнська олімпіада з інформатики

Хмельницька область

Другий етап

7 грудня 2003 року

Задача 1. Оптова покупка.

Один компакт-диск коштує 10 грн., а блок з 10 дисків – 90 грн. Потрібно купити диски на суму m (m>100) грн. Як виконати покупку оптимально?

1.1. Введіть m, виведіть кількість блоків і окремих дисків.

1.2. Вхідні дані введіть з текстового файлу opt.dat, а результат виведіть у текстовий файл opt.sol.

Структура файлу opt.dat така: в єдиному рядку записане натуральне число m (100<m<200000).

Структура файлу opt.sol така: в першому рядку записане натуральне число – кількість блоків; у другому рядку – кількість окремих дисків.

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

opt.dat	opt.sol
102	1 1

Задача 2. Вантаж.

Дослідіть, чи вантаж з габаритними розмірами a, b, c см можна перемістити через прямокутний отвір, що має розміри e та f см.

У першому рядку текстового файлу gruz.dat записані через пропуск три числа – габаритні розміри вантажу, в другому рядку – два числа – розміри прямокутного отвору.

Потрібно скласти програму, яка прочитає вхідні дані із файла gruz.dat, проведе необхідні розрахунки і у файл gruz.sol виведе true, якщо вантаж можна перемістити через отвір і false, якщо вантаж через отвір перемістити не можна.

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

gruz.dat	gruz.sol
5 2 7 3 8	true

Задача 3. Чарівні вектори.

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

Наприклад, існує 3 чарівних 5-векторів:

1 1 1 2 5

1 1 1 3 3

1 1 2 2 2

Технічні вимоги. Число N записане у файлі vector.dat. Ваша програма повинна вивести у перший рядок файла vector.sol число K – кількість чарівних N-векторів, а в наступні K рядків самі вектори.

Задача 4. SMS

Сучасні щільникові телефони підтримують так званий набір SMS, тобто коротких текстових повідомлень. На жаль, клавіатура щільникового телефону має лише 10 клавіш, а в латинській абетці 26 літер, в українській абетці 33 літери. Тому на одній клавіші телефону зображають зразу декілька літер, наприклад на цифрі 1 - АБВ, на 2 - ГДЕЄ, і т. д. Тоді, щоб набрати літеру, яка написана на клавіші першою, потрібно натиснути на цю клавішу 1 раз, щоб набрати другу літеру - 2 рази і т. д., щоб набрати літеру, яка написана на клавіші K-ою по рахунку, треба натиснути на клавішу K разів.

Вчені підрахували, що людина в середньому набирає за час життя щільникового телефону букву А - ZА разів, Б - ZБ разів, і т. д., Я - ZЯ разів. Щоб людина не путалась, букви повинні бути розміщені на клавішах в алфавітному порядку. Однак з метою зменшення середньої загальної кількості натискувань на клавіші, потрібно так розмістити букви на клавішах, щоб сума S = ZАCА + ZБCБ+ ... +ZЯCЯ була мінімальна, де, наприклад, через СУ позначений номер букви У на клавіші, на якій вона знаходиться. Наприклад, якщо у нашого телефону було б 2 клавіші, а в нашому алфавіті було б тільки 3 літери - А Б і В, то можливо було б 2 способи розмістити букви на клавіатурі:

1 АБ S=ZА+2ZБ+ZВ

2 В

і 1 А S=ZА+ZБ+2ZВ

2 БВ

В залежності від величин ZА, ZБ и ZВ один із цих двох варіантів кращий.

Вам дані числа ZА, ZБ, ... ZЯ. Знайдіть таке розміщення букв українського алфавіту на клавіатурі с 10 клавішами, щоб мінімізувати S.

Примітка. Вхідні дані вводяться із вхідного стандартного потоку а вихідні дані виводяться у вихідний стандартний потік.