Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Задания второго тура NetOI-2008
 Задание следует выполнить до 0 часов 22 декабря 2008 г.


Задача Summa

Задано 2 натуральных  числа N1 и N2. Необходимо подсчитать сумму цифр всех чисел от  N1 до N2. 
Технические условия: Программа Summa читает с клавиатуры через пробел два натуральных числа N1, N2 (N1, N2<= 2000000000, N1<=N2). Программа выводит на экран единственное число – найденную суму.

 


Пример
Ввод 21 24
Вывод 18 


Задача
Market

Покупатель имеет купюры номиналом A(1)…,A(N), а продавец  B(1)…,B(M). Необходимо найти максимальную стоимость товара Р, которую покупатель не сможет купить, потому что не имеет возможности точно рассчитаться за этот товар с продавцом, хотя денег для покупки товара достаточно.Технические условия: Программа Market  читает с клавиатуры количество купюр у покупателя N, затем N  натуральных чисел – номиналы купюр покупателя, затем количество купюр у продавца M, а затем  М натуральных чисел – номиналы купюр у продавца. Все числа разделены пробелом. Количество купюр в начальный момент у каждого не превосходит 10000, а номинал каждой купюры не превышает 50000. Программа выводит на экран единственное число P.
 
Пример
Ввод 3 10 5 20 3 1 5 2
Вывод 31



Задача  Winner

Некоторое количество игроков N (всегда большее одного человека), одновременно начинают играть в виртуальном казино, заранее внеся в "банк" игры денежную сумму в размере Z денежных единиц каждый. Игра состоит в следующем:
1. В начале каждого раунда виртуальное казино снимает в свою пользу с каждого из участников текущего раунда денежную сумму в размере T денежных единиц. Величина T до завершения игры не изменяется. В результате этого "банк" игры в начале каждого раунда уменьшается на определенную сумму денежных средств.
2. Во время каждого из проводимых раундов виртуальное казино каким-то образом однозначно определяет среди игроков одного проигравшего  в текущем раунде.
3. Проигравший выходит из игры. Текущий раунд на этом заканчивается.
4. Каждый последующий раунд игры виртуальное казино проводит по тому же принципу, последовательно выполняя все три вышеуказанных правила, но только уже с игроками, оставшимися в игре.
 
Игра продолжается до тех пор, пока в ней не останется один игрок - победитель. Выигрышем победителя является вся денежная сумма, оставшаяся в "банке" игры на момент ее окончания. При каком начальном количестве участников выигрыш победителя будет максимальным и чему равен этот максимальный выигрыш?
 Технические условия:  Программа Winner читает с клавиатуры через пробел два числа Z и T (100<=Z<=50000, 1<=T<=50). Программа выводит на экран два искомых числа, разделенных пробелом. При наличии более одного правильного варианта ответа следует выводить  наибольший выигрыш при наименьшем количестве игроков.
Пример
Ввод 110  20
Вывод
5 270  



Задача Device

Для проведения эксперимента надо выбрать из N имеющихся приборов только три. Для этого выполняют следующую операцию - если в группе приборов больше трех, то их нумеруют и выбирают одну из групп: с четными или нечетными номерами. Операцию повторяют до тех пор, пока в группе не останется три или менее приборов. Если их остается ровно три, то они выбираются для эксперимента. Напишите программу, которая подсчитает количество способов такого выбора приборов.
 Технические условия:  Программа Device читает с клавиатуры число N (1<=N<=2147483647) и выводит на экран найденное количество способов.
 Пример
Ввод 6
Вывод 2 




Задача  Cavalery   
                                                      

На шахматной доске размером  NxM находится Q коней в различных клетках. Шахматист пытается собрать всех коней в одну, известную ему клетку. Найти минимальное количество ходов, которое необходимо для этого сделать шахматисту. Если задача не имеет решенияэто бывает тогда, когда хотя бы 1 конь не может дойти до заданной клетки), сообщить об этом. Очевидно, вам уже понятно, что в одной клетке может находиться одновременно сколько угодно коней.
Технические условия:
Программа Cavalery читает с клавиатуры размеры шахматной доски N, M  (2 ≤ NM ≤ 100), координаты клетки, где кони должны собраться, S, T (номер строки и столбца), количество коней Q (0 ≤ Q ≤ 10000), затем Q  пар чисел – координаты каждого коня. Программа выводит на экран  одно число – минимальное количество ходов, либо, если задача не имеет решения,  количество коней, которые не могут дойти до заданной клетки.

Пример :

Ввод 4 4 1 1 3 2 3 3 2 3 3
Вывод 6
Ввод 5 5 3 4 0
Вывод 0


Задание подготовили Г.Непомнящий, О.Плакидюк, Ю.Пасихов

© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"