П`ятниця, 29.03.2024, 18:52
Головна Реєстрація RSS
Вітаю Вас, Гість
Наше опитування
Оцініть мій сайт
Всього відповідей: 68
Головна » 2017 » Листопад » 20 » IІ ТУР ВСЕУКРАЇНСЬКОЇ УЧНІВСЬКОЇ ОЛІМПІАДИ З ПРОГРАМУВАННЯ 2017/18 Н.Р.
19:46
IІ ТУР ВСЕУКРАЇНСЬКОЇ УЧНІВСЬКОЇ ОЛІМПІАДИ З ПРОГРАМУВАННЯ 2017/18 Н.Р.

19 листопада 2017 року в Хоцьківській ЗОШ І-ІІІ ступенів відбувся ІІ тур Всеукраїнської учнівської олімпіади з програмування серед учнів 8-11 класів.

З А В Д А Н Н Я
ІІ етапу олімпіади з інформатики
2017-2018 н.р.

Задача 1. COUNTERS. (60 балів) За круглим столом зібралось n гравців (n ≤ 255). Кожен зробив ставку в k монет (1 ≤ k ≤ 5). Домовились, що при рахунку за годинниковою стрілкою кожен m-й гравець (m > n) вибуває з гри. Останньому гравцеві дістається вся ставка. Написати програму, яка для даних значень n, m і відомої ставки кожного гравця визначає номер гравця, що виграв та суму виграшу (без урахування своєї ставки).
Вхідні дані: Перший рядок файла Count.dat містить числа n та m, другий рядок через пропуск n чисел k i (1 ≤ i ≤ n) – ставки гравців у порядку номерів.
Результати: У файлі Count.res через пропуск записати номер гравця, що виграв та суму його виграшу.
 
Приклад
Count.dat Count.res
7 9
4 3 2 5 1 3 2
7 18
 
Тести:
1 2 3 4 5 6 7 8 9 10
Тест 2 2 2 3 3 3 7 8 15 15
 
Ідея рішення: Ставки гравців заносимо в лінійний масив. Кожен m-ий елемент масиву замінюємо на нуль, поки не залишиться один ненульовий елемент, це і буде номер гравця, що виграв. Сума його виграшу буде: сума всіх елементів заданого масиву мінус ставка гравця, який залишився.

Кращий розв'язок:

10 тестів (60 балів)

 
Задача 2. NUMBERS. (60 балів) Дано дві довгі однакові стрічки, що складаються із n клітинок в кожній. Кожна стрічка містить однакові набори чисел, але в різному порядку. Написати програму, що визначає, на яку найменшу кількість частин доведеться розрізати першу стрічку, щоб шляхом переставляння частин з неї можна було утворити другу, причому різати можна тільки по межах клітинок, а перегортати стрічку чи її частини не можна.
Вхідні дані: Перший рядок вхідного файла Numb.dat містить натуральне число n (2 ≤ n ≤ 100), що задає кількість клітинок у стрічках. Два наступні рядки містять числа від 1 до n у різному порядку.
Результати: У вихідний файл Numb.res записати єдине число – найменшу кількість частин, на які доведеться розрізати першу стрічку так, щоб, після перестановки частин місцями, отримати другу стрічку.
 
Приклад
Numb.dat Numb.res
5
4 3 2 5 1
1 2 5 3 4
4
 
Тести:
1 2 3 4 5 6 7 8 9 10
Тест 2 2 2 3 3 3 7 8 15 15
 
Ідея рішення: Задані два набори чисел заносимо відповідно у два лінійні масиви. Починаючи з першого елемента другого масиву, шукаємо фрагмент у першому масиві, де всі відповідні числа однакові. Змінюємо їх на нулі і рахуємо розрізану частину. Повторюємо попередні дії, поки в першому масиві всі числа стануть нулями.

Кращий розв'язок:

9 тестів з 10 (57 балів)

 
Задача 3. FRAGMAX. (80 балів) Написати програму, яка визначає в числовій послідовності з n елементів кількість суцільних фрагментів, що містять єдиний найбільший елемент, рівний числу m.
Вхідні дані: У першому рядку вхідного файла Fragmax.dat записано два натуральних числа: n (2 ≤ n ≤ 100) – довжину послідовності чисел – та m (1 ≤ m ≤ 100). У другому рядку міститься послідовність з n натуральних чисел, кожне з яких не перевищує 100.
Результати: Вихідний файл Fragmax.res повинен містити єдине число – кількість фрагментів послідовності, найбільше число яких дорівнює m.
 
Приклади
Fragmax.dat Fragmax.res
4 5
1 5 1 2
6
2 2
3 4
0
 
Тести:
1 2 3 4 5 6 7 8 9 10
Тест 2 2 2 3 3 3 7 8 20 30
 
Ідея рішення: Перебираємо всі можливі варіанти суцільних фрагментів за дoпомогою трьох вкладених циклів з параметром:
for i:=1 to n do
    for j:=i to n do
        for u:=i to j do

і рахуємо кількість суцільних фрагментів, що містять найбільший елемент, рівний числу m.

Кращий розв'язок:

9 тестів з 10 (50 балів)

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

Кращий розв'язок:

10 тестів (80 балів)

 
Задача 4. TRIMIN. (80 балів) Дано два різних типи фігурок, зображених на рисунку, а також такі, які можна з них одержати поворотами. Прямокутне поле розмірами m рядків та n стовпчиків вважається заповненим такими фігурками, коли кожна фігурка знаходиться у межах поля і накриває рівно три клітинки, причому фігурки не перекриваються, а порожніх клітинок не більше двох. Заповнене поле можна подати у вигляді прямокутної таблиці, де нулем позначені пусті клітинки, а однакові натуральні числа позначають клітинки, що належать одній фігурці. Написати програму, яка, проаналізувавши вміст кількох числових двовимірних таблиць, визначить для кожної з них, чи задає вона правильно заповнене фігурками прямокутне поле.
Вхідні дані: Перший рядок вхідного файлу Trim.dat містить єдине ціле число t (2 ≤ t ≤ 10) – кількість прямокутних таблиць. Далі йдуть t блоків такої структури. Перший рядок блоку містить два цілих числа m та n (1 ≤ m ≤ 50, 1 ≤ n ≤ 50) – кількість рядків та кількість стовпчиків відповідної таблиці. Далі йдуть m рядків по n цілих чисел у кожному. Значення цих чисел від 0 до [m × n ⁄ 3] включно.
Результати: Вихідний файл Trim.res повинен містити t рядків, у кожному – слово YES або NO – відповідь про те, чи задає відповідна таблиця правильно заповнене фігурками поле.

Приклади
Trim.dat Trim.res
2
4 8
1 2 2 2 6 7 7 9
1 4 4 3 6 7 8 9
1 0 4 3 6 8 8 9
10 10 10 3 0 5 5 5
2 6
1 1 2 2 1 1
0 1 0 2 0 1
YES
NO
 
Тести:
1 2 3 4 5 6 7 8 9 10
Тест 2 2 2 3 3 3 7 8 20 30
 
Ідея рішення: Легко переконатися, що масив відповідає правильному покриттю фігурками триоміно тоді й тільки тоді, коли виконуються такі дві вимоги:
  1. Значень «0» є рівно (N * M) mod 3 штук, а кожного зі значень від «1» до (N*M) div 3 – рівно по три штуки.
  2. Для кожного зі значень від «1» до (N*M) div 3, зайняті ним клітинки утворюють фігурку триоміно.

Кращий розв'язок:

10 тестів (80 балів)

Результати ІІ етапу олімпіади з інформатики 2017-2018 н.р.
Переяслав-Хмельницький район
Команда ХоцьківськоїЗОШ І-ІІІ ступенів

Наверх

Переглядів: 513 | Додав: ivv
Всього коментарів: 0
avatar