Програмування

XXV Всеукраїнська олімпіада з інформатики ІІ етап (програмування)

Задачі з програмування

1. Розмін

Для ілюстрації метода математичної індукції у підручниках часів СРСР завжди наводилася наступна задача: «Довести, що будь-яку цілу суму грошей, починаючі з 8 крб., можна без здачі розміняти купюрами по 3 та 5 крб.». Вам не потрібно нічого доводити, а необхідно просто написати програму, яка б для двох типів купюр по Х та Y грошових одиниць визначала б, яку найбільшу суму грошей неможливо розміняти цими купюрами, якщо Х та Y – взаємно прості натуральні числа.

Технічні умови
Ім’я програми CHANGE.*
Введення З клавіатури вводяться номінали купюр – два взаємно простих натуральних числа (від 1 до 46342).
Виведення На екран або форму виводиться найбільша сума, яку не можна розміняти цими купюрами. Якщо можна розміняти будь-яку суму, то виводимо 0.

 

Приклад Введення Виведення
3 5 7

2. Як провести відпустку?

У туристичній фірмі клієнтові запропонували дві путівки. Їх вартості С1 і С2, а тривалість турів D1 і D2 відповідно. Як йому поступити, якщо він хоче подорожувати, як можна довше, але його відпустка складає D днів, а заплатити за путівки він може не більше С. Скласти програму для прорахунку варіантів. Програма виводить одне з п’яти повідомлень(без пропусків):

Повідомлення Роз’яснення
1AND2 Купувати обидві путівки
1 Купувати 1-у путівку
2 Купувати 2-у путівку
1OR2 Купувати 1-у або 2-у путівку (тривалість турів однакова, а ціни доступні клієнтові)
NONE Купівля не відбудеться

 

Технічні умови
Ім’я програми TOUR.*
Введення З клавіатури вводяться в наступному порядку 6 чисел (їх значення від 1 до 1000): C  D  С1  D1  С2  D2.
Виведення На екран або форму виводиться одне з п’яти вище згаданих повідомлень.

 

Приклади Введення Виведення
1 700 25 800 18 600 26 NONE
2 700 25 700 18 550 18 1OR2

3. Пісня

Дуже часто пісня складається з кількох куплетів та приспіву, які виконуються наступним чином: перший куплет, приспів, другий куплет, приспів, …, останній куплет, приспів. Але у пісеннику запис пісні наводиться наступним чином: перший куплет, приспів, а далі тексти наступних куплетів. Напишіть програму, яка б визначала виконання пісні за текстом із пісенника.

Технічні умови
Ім’я програми SONG.*
Введення З клавіатури вводиться рядок, в якому записана кількість куплетів – натуральне число К (від 1 до 10), а далі К+1 початкова літера: першого куплету, приспіву і наступних куплетів (великі латинські літери). Число та кожна літера розділені між собою пропусками.
Виведення На екран або форму виводяться у один рядок початкові літери частин пісні, розділені пропусками, у їх порядку при виконанні.

 

Приклад Введення Виведення
3 A P B C A P B P C P

4. Шоу

Незнайко бере участь в популярній телевізійній грі “Fool-Show”, яка проходить за наступними правилами: ведучий послідовно називає преміальні бали (цілі невід’ємні числа). Гравець може розпочати гру з будь-якого моменту. Йому приплюсовуються названі бали, і після кожного ходу він приймає рішення – вийти з гри з набраною сумою або продовжувати її далі. Якщо гравець чекає появи наступного числа, а ведучий називає число “нуль”, то всі очки, набрані гравцем, пропадають і він вибуває з гри. Після третього нуля, названого ведучим, гра закінчується. Незнайкові вдалося дізнатися про послідовність чисел, які називатимуться сьогодні. Яке максимальне число балів він зможе набрати?

Технічні умови
Ім’я програми SHOW.*
Введення Програма послідовно вводить з текстового файлу SHOW.DAT преміальні бали (числа від 0 до 1000), поки утретє не зустрінеться 0.
Виведення У вихідний файл SHOW.SOL виводиться максимально можлива сума балів.

Приклад SHOW.DAT SHOW.SOL
7 8 0 1 2 13 0 14 0 16

5. Слон

Шахова фігура – слон пересовується по діагоналям, тобто за один хід зміщується на однакову кількість клітинок по вертикалі та горизонталі. Нехай шахове поле має М рядків та N стовпців. Слон знаходиться у першому стовпчику на полі (1;А) і йому потрібно попасти на поле (N;В) останнього стовпчика. Скільки їснує різних шляхів руху слона, якщо він рухається зліва направо і на кожному ході змінює напрям руху? Початкове та кінцеве поля не співпадають.

Технічні умови
Ім’я програми BISHOP.*
Введення З клавіатури вводяться чотири цілих числа (від 1 до 100): M, N, A, B, розділених пропусками.
Виведення На екран або форму виводиться кількість шляхів. Якщо при додержанні умов руху з початкового поля на останнє  попасти неможливо, то виводиться 0.

 

Приклад Введення Виведення Шляхи у прикладі:
5 4 2 3 3 (1;2) – (3;4) – (4;3) 

(1;2) – (2;1) – (4;3)

(1;2) – (2;3) – (3;2) – (4;3)

Умови змагання:

1. Кількість і склад задач, час роботи визначає журі олімпіади на місцях.

2. Для роботи створіть директорію, назва якої співпадає з Вашим прізвищем, а розширення з номером школи, в якій Ви навчаєтесь, (напр., Shevchenko.12). В середині цієї директорії створіть папки за назвами тих задач, які Ви будете розв’язувати (CHANGE, TOUR, SONG, SHOW, BISHOP), а також файл readme.txt, в якому обов’язково вкажіть: Ваші прізвище, ім’я, по-батькові, район, школу, клас, в якому Ви вчитесь, дату народження, телефон, П.І.Б вчителя інформатики. Якщо в підготовці до олімпіади брали участь і інші особи, вкажіть і їх.

3. Кожну задачу розв’язуйте в своїй директорії. Програму-розв’язок треба помістити в  текстовий ASCII-файл, який обов’язково має назву, що вказана в умові, а розширення (.PAS, .CPP, .FRM, .С, .BAS, .DPR тощо) в залежності від мови та середовища, яке Ви використовуєте. Програму потрібно відкомпілювати і в цій директорії зберегти також і ЕХЕ-файл з такою ж назвою. Перевірятися буде   ЕХЕ-файл на наборі тестів. Журі зберігає право перекомпілювати Вашу програму.

4. При розв’язанні задачі SHOW використання файлів введення та виведення обов’язкове. Програма повинна обробляти файли, які знаходяться в поточному директорії. При порушенні цієї умови задача перевірятися не буде!

 

Рекомендовані тести до задач міської (районної олімпіад) з програмування 2011-12 навчального року

Тести до задачі “CHANGE”

№ тесту Вхідні дані Результат Оцінка
1 3 5 7 2 бали
2 1 73 0 7 балів
3 24 17 367 7 балів
4 999 1001 994999 7 балів
5 46342 46341 2147441939 7 балів
Разом 30 балів

 

Тести до задачі “TOUR”

№ тесту Вхідні дані Результат Оцінка
1 9 9 10 5 5 10 NONE 6 балів
2 9 9 9 9 6 5 1 6 балів
3 9 9 6 10 9 1 2 6 балів
4 9 9 9 8 8 8 1OR2 6 балів
5 9 9 4 5 5 4 1AND2 6 балів
Разом 30 балів

Якщо формат виведення не відповідає умовам, за тест нараховується 2 бали.

 

Тести до задачі “SONG”

№ тесту Вхідні дані Результат Оцінка
1 3 A P B C A P B P C P 3 бали
2 1 A Z A Z 9 балів
3 2 A A A A A A A 9 балів
4 8 X A W V U T S R Q X A W A V A U A T A S A R A Q A 9 балів
Разом 30 балів

Тести до задачі “SHOW”

№ тесту Файл show.dat Файл show.sol Оцінка
1 7 8 0 1 2 13 0 14 0 16 2 бали
2 0 0 0 0 4  бали
3 23 0 7 0 9 0 23 8 балів
4 14 2 0 8 9 0 15 0 17 8 балів
5 5 6 7 0 1 0 1 1 17 0 19 8 балів
Разом 30 балів

Тести до задачі “BISHOP”

№ тесту Вхідні дані Результат Оцінка
1 5 4 2 3 3 1 бал
2 40 17 4 21 0 2 бали
3 40 17 4 20 1 9 балів
4 33 33 3 3 253706790 9 балів
5 100 100 49 50 50445672272782096667406248627 9 балів
Разом 30 балів

Сайт відділу освіти Томаківської райдержадміністрації