Задания 1 тура Всеукраинской олимпиады школьников по информатике NetOI-2019
(решения принимаются до 0 часов 16.11.19)
Задача Coins2019. Как вам известно, в Украине изъято из обращения монеты 1, 2 и 5 копеек. Эти монеты принимаются к обмену. Вам необходимо определить количество способов подать на обмен сумму в N копеек этими монетами.
Технические условия. Программа Coins2019 читает с устройства стандартного ввода натуральное число N, не более 105 и выводит на устройство стандартного вывода искомое количество способов.
Пример
Ввод 5
Вывод 4
Задача Jogging. Один из участников NetOI занимается спортивным ориентированием и периодически участвует в соревнованиях. На этот раз правила соревнования немного необычные. Существует N контрольных пунктов, все находятся на прямой. Пункты имеют свои координаты. Спортсмен начинает маршрут в точке с координатой Q и должен посетить K пунктов. Какое минимальную расстояние он должен преодолеть?
Технические условия Программа Jogging читает с устройства стандартного ввода два натуральных числа - N и K (оба не больше 105). Далее программа читает ровно N целых чисел, каждое из которых по модулю не превышает 105 - координаты контрольных пунктов, далее одно целое число, по модулю не большее 105 - координата, с которой начинает спортсмен. Программа должна вывести единственное число - минимальное расстояние, которое нужно преодолеть, чтобы достичь цели и посетить K контрольных пунктов.
Примеры
|
Ввод |
Вывод |
|
3 2 1 7 12 10 |
7 |
|
Ввод |
Вывод |
|
2 1 11 -10 0 |
10 |
Задача Minandmax. Тарас, младший брат Миши, очень хочет поиграть одним из его массивов. Миша, чтобы не терять возможность научить малыша чему-то новому, поставил ему такое условие: "Вот тебе массив целых чисел. Найди в нем «слабейший» фрагмент из элементов, идущих подряд, длиной не менее 2, тогда можешь поиграть с этим массивом ". При этом он добавил, что «силой» фрагмента массива является разноссть максимального и минимального значений в данном фрагменте. Помогите Тарасу.
Технические условия. Программа Minandmax читает со стандартного устройства ввода две строки. Первая строка содержит число N (2 ≤ N ≤ 10000) - длину массива. Вторая строка содержит элементы массива (целые числа, по абсолютной величине не превышают 109). Программа выводит на устройство стандартного вывода единственное число - силу «слабейшего» фрагмента.
|
Ввод |
Вывод |
|
2 1 3 |
2 |
|
3 1 1 1 |
0 |
|
5 1 2 1 2 1 |
1 |
Задача Toys2019. В классе НУШ установили автомат, продающий игрушки (реформа образования!). Ученики, конечно же, выстроились в очередь, но выяснилось, что:
• Стоимость игрушки - 1 гривна;
• Каждый ученик может приобрести только одну игрушку;
• Автомат принимает только купюры 1, 2 и 5 гривен и выдает по необходимости сдачу;
• У каждого ученика есть только одна купюра;
• Если автомат не имеет чем выдать сдачу, он останавливается;
• В начале работы в автомате нет ни одной купюры;
• Ученики категорически не хотят меняться местами в очереди и пропускать других учеников.
Сколько учеников смогут приобрести игрушки?
Технические условия. Программа Toys2019 читает с устройства стандартного ввода в первой строке количество учеников N - натуральное число, не более 105, во втором - N разделенных пробелом чисел 1, 2 или 5 - номиналы купюр учеников в очереди, начиная от автомата. Программа выводит на устройство стандартного вывода единственное число - максимальное количество учеников, которые приобретут игрушки.
Пример
Ввод
7
1 2 1 2 5 5 1
Вывод
5
Задача Buffet. В буфете физико-математической школы (не удивляйтесь, они пока существуют!) все цены - несократимые обыкновенные дроби с положительными числителями и знаменателями. Вчера в буфет привезли A булочек и B пирожков общей стоимостью S1, а сегодня - C булочек и D пирожков общей стоимостью S2. Помогите буфетчице определить стоимость одной булочки и одного пирожка.
Технические условия. Программа Buffet читает с устройства стандартного ввода в единственной строке сначала три натуральных числа A, B, S1, и далее 3 числа C, D, S2. Все числа разделены пробелами и не превышают 105. Программа выводит на устройство стандартного вывода вначале стоимость одной булочки – числитель и знаменатель через пробел, а далее стоимость одного пирожка – так же разделенные пробелом числитель и знаменатель. Если однозначно определить стоимости булочки и пирожка невозможно, надо вывести 0 0 для каждлго изделия.
Примеры
Ввод Вывод
1 3 5 2 6 10 0 0 0 0
Ввод Вывод
4 3 5 2 3 4 1 2 1 1
--------------------------------------------------------------------------------------
Задание подготовили Г.Непомнящий, М.Стречень, Ю.Пасихов