|
Термін виконання - до 0 годин 28 грудня 2010 р. Працює перевірка задач на авторських тестах в режимі on-line.
Реєстрація учасників триває. Он-лайн відеоконсультації (відео-чат) за адресою //disted.edu.vn.ua/index/webinar
8 грудня 2010 року в 18-30
15 грудня 2010 року в 18-30
Для участі слід використовувати IE
e-mail: olymp@olymp.vinnica.ua
Задача 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
Завдання підготували В.Боднар, Г.Непомнящий, І.Порубльв, Ю.Пасіхов
|
