| Срок выполнения - до 0 часов 28 декабря 2010 г. Работает проверка на авторских тестах в режиме on-line.Регистрация участников продолжается. Видеоконсультации по адресу //disted.edu.vn.ua/index/webinar 8 декабря 2010 г. в 18-3015 декабря 2010 г.в 18-30
Задача Crossing
На плоскости находится робот, в памяти которого записана программа. Эта программа представляет собой последовательность чисел, каждое число - отдельная команда. Неотрицательное число означает сделать такое количество шагов вперед, число -1 - повернуть налево на 90 градусов, стоя на месте, а число -2 означает повернуть вправо на 90 градусов. После окончания движения робота оказалось, что он ни разу не изменял направление своего движения дважды в одной и той же точке и ни один отрезок своего пути не проходил два или более раз. Начальная и конечная позиции робота не могут совпадать, робот эти точки больше никогда не проходил. Сколько раз робот пересекал свой путь?
Технічні умови.
Програма Crossing читает с клавиатуры натуральное число n (n<=1000) , далее n целых чисел a[i] (-2<=a[i]<=1000) - команд, выполняемых роботом. Программа выводит на экран искомое количество пересечений.
Пример
Ввод
12 3 -1 4 -2 1-2 2 -2 3 -1 3 2
Вывод
2
Задача Krizis
Есть N (1£N£100) граждан – субъектов предпринимательской деятельности. Каждый из них имеет на счету сумму денег, возможно и отрицательную (долги!). Каждый из них имеет возможность провести одну сделку, в результате которой сумму на счету можно изменить не более чем на целую величину L (1£L£3200) как в сторону увеличения, так и в сторону уменьшения или оставить без изменения. Если после такой операции некоторые из сумм на счету оказываются равными, то их владельцы объединяются в одно предприятие со счетом, какой был у каждого до слияния. Им удалось провести эту операцию таким образом, что осталось минимально возможное количество субъектов предпринимательской деятельности. Требуется написать программу для определения этого количества.
Технические условия: Программа читает с клавиатуры значения L и N, а далее N целых чисел (в диапазоне от -32000 до 32000), записанных через пробел. Программа выводит на экран одно число – искомую величину
Пример
Ввод
10 3 11 21 27
Вывод:
1
Задача Wie
Байтазар - руководитель бригады, которая ищет нефть. Известно, что месторождение нефти представляет собой отрезок с одним концом в точке А и другим внутри отрезка AB. Команда выяснила, что в точке A нефть есть, а в точке В - нет. Теперь Байтазару нужно узнать вторую границу месторождения (где именно внутри отрезка AB граница месторождения).
Поскольку в разных точках грунт состоит из разных пород, время бурения одной скважины зависит от места. Бригада Байтазара небольшая, поэтому они не могут бурить в разных местах одновременно. Босс Байтазара желает знать, когда бригада будет в состоянии определить границы месторождения. Байтазар попросил вас о помощи. Он разделил отрезок, соединяющий точки А и В, на отрезки равной длины. Точка A имеет координату 0, точка B координату N+1, а между ними есть N точек с координатами 1, 2,. . . , N. Байтазар сообщил вам количество времени, необходимое для бурения скважин в этих точках - оно равно t1, t2. . ., tN соответственно. Вы должны создать такой план бурения, что время, необходимое для определения дальней от точки A границы нефтяного месторождения, минимально (предполагая наихудший сценарий).
Технические условия. Программа читает с клавиатуры сначала натуральное число N (1 <= N <= 200), затем N натуральных чисел t1, t2. . ., tN, разделенных пробелами (1<= ti<=106). Ваша программа выводит на экран одно целое число - минимальное количество времени, которое придётся потратить Байтазару (предполагая наихудший сценарий), чтобы определить границы месторождения.
Пример
Ввод:
4 8 24 12 6
Вывод:
42
Объяснение примера. Предположим, что Байтазар бурит первую скважину в точке 1, что требует времени 8. Если окажется, что нефть там есть, ему может понадобиться пробурить скважины и в точке 2, и в точке 3. Если он пробурит только в точке 3, может оказаться, что там нефти нет и надо проверить, есть ли она в точке 2. Если он пробурит только в точке 2, может оказаться, что там нефть есть, и надо проверить точку 3. Таким образом, бурение скважин может занять 8+24+12=44 единиц времени. Оказывается, лучше начать бурения с точки 2. Если окажется, что нефти там нет, надо проверить точку 1, получим затраты времени 24+8=32. Если окажется, что нефть там есть, будет гарантированно достаточно пробурить в точках 3 и 4, получив суммарные затраты времени 24+12+6=42.
Задача Derivative
Назовем число P1 производным числа P, если P1 равно сумме кубов цифр, стоящих на непарных позициях и сумме квадратов цифр, стоящих на парных позициях числа P. Назовем число Pk производным k-го порядка числа P если для всех 1<i≤k число Pi является производным числа Pi-1. Дано натуральное число P найдите его производное k-го порядка.
Технические условия: Программа читает числа P и k, записанные через пробел (1≤ P, k ≤109). Програма выводит на екран единственное число – Pk.
Пример:
Ввод:
16 3
Вывод:
379
Примечание: Термин производное число», используемый в данной задаче, не имеет ничего общего с подобными терминами высшей математики.
Задача Moneybox
В копилке героя олимпиад Васи Пупкина есть только монеты его любимых номиналов. Количество любимых номиналов N (1 ≤ N ≤ 7) (имеются в виду украинские монеты номиналом 1, 2, 5, 10, 25, 50 коп. и 1 грн. Монету номиналом 1 грн. считать монетой номиналом 100 коп.) Однажды Васе очень были нужны деньги, и он решил достать из копилки с помощью пинцета часть монет. Естественно, Вася не видит монет в копилке, и поэтому каждый раз может вынуть монету любого номинала.
Сколько различных значений может иметь сумма полученных Петей денег, если он достанет из копилки M (1 ≤ M ≤ 1000) монет (считать, что количество монет каждого из имеющихся в копилке номиналов не меньше M)? Например, любимые монеты Пети 10 коп. и 25 коп. (N = 2). Петя вынимает 3 монеты (M = 3). При этом возможны варианты:
10 коп. + 10 коп. + 10 коп. = 30 коп;
10 коп. + 10 коп. + 25 коп. = 45 коп;
10 коп. + 25 коп. + 25 коп. = 60 коп;
25 коп. + 25 коп. + 25 коп. = 75 коп.
То есть, возможны четыре различных значения суммы.
Технические условия:
Программа читает число N, далее N чисел Z1, Z2, ... Zn - номиналы монет в копейках, далее число M. Все числа записаны в одну строку через пробел.
Программа выводит на экран единственное число - искомую величину.
Примеры:
Ввод:
2 10 25 3
Вывод:
4
Ввод:
4 1 2 5 10 3
Вывод: 19
Задания подготовили В.Боднарь, Г.Непомнящий, И.Порубльов, Ю.Пасихов
|
