Завдання ІІ етапу Всеукраїнської учнівської олімпіади з інформатики 2019 р.
Завдання 1. (20 балів)
Задано
два числа N і K. Знайдіть кількість
чисел з діапазону від 1 до N включно, таких, що сума їх цифр ділиться на K.
Вхідні дані
У
першому рядку вхідного файлу записані числа N (1≤N≤1018) і K
(1≤K≤200).
Вихідні дані
У
вихідній файл вивести кількість таких чисел.
Завдання 2. (30 балів).
В
інтернет-магазині до дня «Святого
Миколая» проводиться акція - «Купуючи два будь-яких товари, третій отримуєш
безкоштовно *», а внизу дрібним шрифтом приписано «* - з трьох обраних вами
товарів оплачуються два найбільш дорогих».
Петрик,
переглянувши повний список товарів, який пропонується в інтернет-магазині і їх
вартість, визначився, які товари він
хоче купити. Відповідно, йому потрібно визначити, яку мінімальну суму грошей
він може витратити для такої покупки.
Формат вхідних даних
У
вхідному файлі задано спочатку число N (1≤N≤1000), а потім N чисел - вартості
обраних Петриком товарів. Всі вартості - натуральні числа, що не перевищують
10000.
Формат вихідних даних
У
вихідний файл виведіть одне число – мінімальну суму грошей, яка необхідна, щоб
Петрик зміг придбати вибрані товари.
Завдання 3. Гра (50 балів).
Учні,
на подвір'ї школи грають в одну із своїх
улюблених ігор.
На
одній лінії на однаковій відстані один від одного намальовано квадрати, а в
середині кожного із яких написано ціле
додатне або від'ємне число (кількість балів). Учень робить хід, «стрибає» з
одного круга в інший. Намальовані квадрати мають порядкові номери від 1 до N.
Стартує кожен учень в квадраті з номером 1 і фінішує в квадраті з номером N.
Він може робити «стрибки» вперед на відстань від 1 до K квадратів, рахуючи від
поточного. Виграє той з учнів, який набере більшу суму балів потрапивши на квадрат
з номером N (ця сума рівна сумі чисел,
які написані в тих квадратах де побував учень).
Зрозуміло,
що потрапивши на певний квадрат
учень збільшу або зменшує свою
суму набраних балів . Визначте, як потрібно «стрибати» учневі, щоб набрати
найбільшу суму балів. Враховуйте, що учень не може «стрибати» назад.
Вхідні дані
У першому рядку задано два натуральних числа: N та K (2 ≤ N, K ≤ 10000),
розділені пропусками.
У другому рядку записані через пропуск N - 2 цілих числа ( кожне з яких по модулю не перевищують 10000).
Вихідні дані
У першому рядку
програма повинна вивести найбільшу кількість балів, яку може набрати учень. У
другому рядку виводиться кількість
зроблених учнем «стрибків», а в третьому рядку номери всіх квадратів, на
яких побував учень (через пробіл в порядку зростання).
Якщо правильних відповідей декілька, виведіть будь-яку з
них.
Приклад.
Вхідні дані
5 3
2 -3 5
Вихідні дані
7
3
1 2 4 5
Немає коментарів:
Дописати коментар