Олімпіада школярів з програмування

Скачати 171.16 Kb.

Назва	Олімпіада школярів з програмування
Дата	02.06.2013
Розмір	171.16 Kb.
Тип	Документи

bibl.com.ua > Астрономія > Документи

Годинник з боєм

Ім'я вхідного файлу:	а.in
Ім'я вихідного файлу:	а.out
Максимальний час роботи на одному тесті:	3 секунди
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

Старовинний годинник б'є щопівгодини. Причому на початку кожної години вони б'ють стільки раз, скільки зараз годинника (по 1 разу – під час ночі і під час дня, по 2 рази – в дві години ночі в дві години дня і так далі, опівночі і опівдні вони б'ють, відповідно, по 12 разів). І ще 1 раз вони б'ють в середині кожної години.

Даний проміжок часу (відомо, що пройшло строго менше 24 годин). Напишіть програму, що визначає, скільки ударів зробив годинник за цей час.

Формат вхідних даних

У першому рядку записаний початковий момент часу, в другому рядку — кінцевий. Моменти часу задаються двома цілими числами, що розділяються пропуском. Перше число задає годинник (від 0 до 23), друге — хвилини (від 1 до 59, при цьому воно не рівне 30).

Формат вихідних даних

У вихідний файл виведіть одне число — скільки ударів зробив годинник за цей відрізок часу.

Приклади

а.in	а.out
5 20 10 25	45
10 25 5 20	135
5 2 5 21	0

Вибори жерців

Ім'я вхідного файлу:	b.in
Ім'я вихідного файлу:	b.out
Максимальний час роботи на одному тесті:	3 секунди
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

У країні Олімпіадії знову вибори.

Країна складається з маленьких графств. Графства об'єднуються в конфедерації. Кожна конфедерація разів на рік вибирає собі покровителя – одного з 200 жерців. Цей ритуал називається Великими Перевиборами Жерців і виглядає так: конфедерації одночасно подають заяви (одне від конфедерації) в Раду Жерців про той, кого вони хотіли б бачити своїм покровителем (якщо заява не подана, то вважають, що конфедерація хоче залишити собі того ж покровителя). Після цього всі заявки задовольняються. Якщо декілька конфедерацій вибирають одного і того ж Жерця, то вони назавжди об'єднуються в одну. Таким чином, кожен Жрець завжди є покровителем не більше ніж одній конфедерації. Потрібно написати програму, що дозволяє Раді Жерців з'ясувати номер Жерця-покровителя кожного графства після Великих Перевиборів. У Раді всі графства занумеровані (починаючи з 1). Всі Жерці занумеровані числами від 1 до 200 (деякі з них зараз можуть не бути нічиїми покровителями).

Формат вхідних даних

У вхідному файлі записано число N – кількість графств в країні (1N5000) – і далі для кожного графства записаний номер Жерця-покровителя конфедерації, в яку воно входить (графства вважаються по порядку їх номерів). Потім вказані заяви від конфедерацій. Спочатку записано число M – кількість поданих заяв, а потім M пар чисел: перше число – номер поточного Жерця-покровителя, друге – номер бажаного Жерця-покровителя.

Всі числа у вхідному файлі розділяються пропусками і (або) символами перекладу рядка.

Формат вихідних даних

У вихідний файл вивести для кожного графства одне число – номер його Жерця-покровителя після Великих Перевиборів. Спочатку – для першого графства, потім – для другого і так далі

Приклад

b.in	b.out
7 1 1 5 3 1 5 1 2 5 1 1 3	3 3 1 3 3 1 3

Представлення чисел

Ім'я вхідного файлу:	з.in
Ім'я вихідного файлу:	з.out
Максимальний час роботи на одному тесті:	3 секунди
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

Дано натуральне число N. Потрібно представити його у вигляді суми двох натуральних чисел A і B таких, що НОД (найбільший загальний дільник) чисел A і B — максимальний.

Формат вхідних даних

У вхідному файлі записано натуральне число N (2N109⁾

Формат вихідних даних

У вихідний файл виведіть два шуканих числа A і B. Якщо рішень декілька, виведіть будь-яке з них.

Приклади

з.in	з.out
15	5 10
16	8 8

Гексагон

Ім'я вхідного файлу:	d.in
Ім'я вихідного файлу:	d.out
Максимальний час роботи на одному тесті:	3 секунди
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

оле для игры в новую игру "Гексагон" разбито на шестиугольники (см. рисунок). Игрок, стартуя из некоторого начального шестиугольника, сделал несколько ходов. Каждый ход заключается в перемещении фишки в соседний шестиугольник (имеющий с тем, где находилась фишка до начала хода, общую сторону) — тем самым, ход делается вдоль одного из направлений X, Y или Z (см. рисунок). Игрок записал все свои ходы, причем если фишка двигалась вдоль какого-либо направления несколько раз подряд, то в записи это обозначается указанием направления и количества ходов, которые были сделаны.

Напишіть програму, яка знайде найкоротший (по кількості здійснюваних ходів) шлях в початкову клітку з тієї, де фішка опинилася після ходів гравця.

Формат вхідних даних

У першому рядку вхідного файлу записано число N — кількість рядків в записі переміщень фішки (1N100). Далі йде N рядків із записом ходів: у кожному рядку записана спочатку велика буква X, Y або Z, задаюча напрям, потім пропуск, і число, задаюче кількість ходів в даному напрямі (число може бути і негативним, якщо гравець переміщав фішку паралельно осі, але в напрямі, протилежному напряму осі). Всі числа по модулю не перевищують 200.

Формат вихідних даних

У вихідний файл виведіть опис найкоротшого шляху назад в початкову клітку в тому ж форматі, в якому опис заданий у вхідному файлі (за винятком обмежень). Всі числа, що визначають кількість ходів в якому-небудь напрямі, повинні бути ненульовими.

Приклад

d.in	d.out
4 Z -2 Y 3 Z 3 X -1	2 Y -2 Z –2

Магія Копперфільда

Ім'я вхідного файлу:	e.in
Ім'я вихідного файлу:	e.out
Максимальний час роботи на одному тесті:	3 секунди
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

Всесвітньо відомий маг Девід Копперфільд любить показувати наступний трюк. Квадрат з N стовпців і N рядків, в кожній клітці якого знаходиться яка-небудь картинка, з'являється на екрані телевізора. Хай всі картинки пронумеровані таким чином:

1	2	.	N
N+1	N+2	.	*2N**
:	:	.	:
*N(N–1)+1**	*N(N–1)+2**	.	*NN**

Девід просить кожного глядача поставити палець на ліву верхню картинку (тобто в клітку номер 1), і Магія починається: маг просить глядачів зрушити свій палець K1 разів в довільному напрямі (зрушувати палець дозволяється тільки на сусідню картинку по горизонталі або по вертикалі, залишати палець на місці заборонено, при цьому якщо, допустимий, Девід попросив зрушити палець 3 рази, то можна, наприклад, зрушити палець на одну клітку управо, потім — на одну клітку вниз, потім — на одну вгору). Потім із словами "Ваш палець не тут" Девід прибирає деякі картинки, і — що дивно, пальці телеглядачів дійсно не указують на ті картинки, які прибирає Девід. Потім він просить зробити K2 ходів, і так далі (якщо Девід вже прибрав якусь картинку, то ходити через цю клітку не можна). В кінці, Девід прибирає всі картинки, окрім однієї, і, посміхаючись, говорить: "Ви тут" (аплодисменти).

Девіду доводиться досить часто повторювати цей трюк, і, щоб не помилитися, він попросив написати програму, яка йому повідомлятиме, скільки ходів повинні робити телеглядачі, і які картинки потрібно прибирати. Напишіть таку програму.

Формат вхідних даних

У вхідному файлі записано одне число N — розмір квадрата (2N100).

Формат вихідних даних

У вихідний файл ваша програма повинна друкувати наступні рядки чисел:

K1 X1,1 X1,2 . X1,m1

K2 X2,1 X2,2 . X2,m2

.

Ke Xe,1 Xe,2 . Xe,me

де Ki — це число ходів, які повинні зробити телеглядачі, а Xi,1 . Xi,mi — номери картинок, які Девід повинен прибрати з екрану після цього. При цьому всі Ki повинні задовольняти умові 2NKi10000 і всі Ki повинні бути різні. Кожна картинка (окрім тієї, яка залишиться) повинна забиратися рівно один раз. Після кожного прохання глядачів зробити Ki ходів, Девід повинен прибирати хоч би одну картинку. Кожне Ki повинне друкуватися на початку нового рядка. Ситуацій, коли телеглядач залишився на клітці, у якої немає сусідніх, а його просять абикуди ходити, виникати не повинно.

Приклад

e.in	e.out
3	8 4 6 13 9 10 7 1 7 8 11 3 5

Кубічне рівняння

Ім'я вхідного файлу:	f.in
Ім'я вихідного файлу:	f.out
Максимальний час роботи на одному тесті:	3 секунди
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

Напишіть програму, яка шукатиме всі цілі X, такі, що задовольняють рівнянню

AX3 + BX2 + CX + D = 0

де A, B, C, D — дані цілі числа.

Формат вхідних даних

У вхідному файлі записано чотири цілі числа: A, B, C, D. Всі числа по модулю не перевищують 2109.

Формат вихідних даних

У вихідний файл виведіть спочатку кількість вирішень цього рівняння в цілих числах, а потім саме коріння в зростаючому порядку. Якщо рівняння має нескінченно багато коріння, виведіть у вихідний файл одне число –1 (мінус один).

Приклади

f.in	f.out
1 0 0 –27	1 3
0 1 2 3	0

Швидка допомога

Ім'я вхідного файлу:	g.in
Ім'я вихідного файлу:	g.out
Максимальний час роботи на одному тесті:	3 секунди
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

Бригада швидкої допомоги виїхала по виклику в один з відокремлених районів. На жаль, коли диспетчер отримав виклик, він встиг записати тільки адресу будинку і номер квартири K1, а потім зв'язок урвався. Проте він пригадав, що за цією ж адресою будинку якийсь час назад швидка допомога виїжджала в квартиру K2, яка розташована в під'їзду P2 на поверсі N2. Відомо, що в будинку M поверхів і кількість квартир на кожному сходовому майданчику однаково. Напишіть програму, яка вычилсяет номер під'їзду P1 і номер поверху N1 квартири K1.

Формат вхідних даних

У вхідному файлі записано п'ять позитивних цілих чисел K1_, M, K2_, P2_, N2_. Всі числа не перевершують 1000.

Формат вихідних даних

Виведіть два чиса P1 і N1. Якщо вхідні дані не дозволяють однозначно визначити P1 або N1, замість відповідного числа надрукуйте 0. Якщо вхідні дані суперечливі, надрукуйте два числа –1 (мінус один).

Приклади

g.in	g.out
89 20 41 1 11	2 3
11 1 1 1 1	0 1
3 2 2 2 1	-1 –1

A-функция від строчки

Ім'я вхідного файлу:	h.in
Ім'я вихідного файлу:	h.out
Максимальний час роботи на одному тесті:	1 секунда
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

Даний рядок S, що складається з N символів. Визначимо функцію A(i) від перших i символів цій терміни таким чином:

A(i)= максимально можливому до, що рівні наступні рядки:

S[1]+S[2]+S[3]+.+S[k]

S[i]+S[i–1]+S[i–2]+.+S[i–k+1]

де S[i] – i-ый символ рядка S, а знак + означає, що символи записуються в строчку безпосередньо один за одним.

Напишіть програму, яка обчислить значення функції A для заданої строчки для всіх можливих значень i від 1 до N.

Формат вхідних даних

У першому рядку вхідного файлу записано одне число N. 1N200000. У другому рядку записаний рядок довжиною N символів, що складається тільки з великих і/або маленьких латинських букв.

Формат вихідних даних

У вихідний файл виведіть N чисел — значення функції A(1), A(2) . A(N).

Приклад

h.in	h.out
5 aabaa	1 2 0 1 5

Олімпіада по алхімії

Ім'я вхідного файлу:	i.in
Ім'я вихідного файлу:	i.out
Максимальний час роботи на одному тесті:	3 секунди
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

У державі алхіміків є N населених пунктів, пронумерованих числами від 1 до N, і M дороги. Населені пункти бувають двох типів: села і міста. Крім того, в державі є одна столиця (вона може розташовуватися як в місті, так і в селі). Кожна дорога сполучає два населені пункти, і для проїзду по ній потрібний Ti хвилин. У столиці було вирішено провести 1-у державну командну олімпіаду по алхімії. Для цього у всі міста із столиці були відправлені гінці (по одному гінцеві на місто) з інформацією про олімпіаду.

Напишіть програму, яка порахує, в якому порядку і через який час кожен з гінців дістанеться до свого міста. Вважається, що гонець під час шляху не спить і ніде не затримується.

Формат вхідних даних

У вхідному файлі спочатку записано 3 числа N, M, K — кількість населених пунктів, кількість дорог і кількість міст (2N1000, 1M10000, 1KN). Далі записаний номер столиці C (1CN). Наступні K чисел задають номери міст. Далі слідують M трійок чисел Si_, Ei_, Ti_, що описують дорогі: Si і Ei — номери населених пунктів, які сполучає дана дорога, а Ti — час для проїзду по ній (1Ti100).

Гарантується, що до кожного міста із столиці можна добратися по дорогах (можливо, через інші населені пункти).

Формат вихідних даних

Виведіть у вихідний файл K пар чисел: для кожного міста долен бути виведений його номер і мінімальний час, коли гонець може в нім опинитися (час вимірюється в хвилинах з тієї миті, як гінці виїхали із столиці). Пари у вихідному файлі повинні бути впорядковані за часом прибуття гінця.

Приклади

i.in	i.out
5 4 5 1 1 2 3 4 5 1 2 1 2 3 10 3 4 100 4 5 100	1 0 2 1 3 11 4 111 5 211
5 5 3 1 2 4 5 2 1 1 2 3 10 3 4 100 4 5 100 1 5 1	5 1 2 1 4 101

Лотерея

Ім'я вхідного файлу:	j.in
Ім'я вихідного файлу:	j.out
Максимальний час роботи на одному тесті:	4 секунди
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

На одному з телеканалів кожного тижня проводиться наступна лотерея. Протягом тижня учасники роблять свої ставки. Кожна ставка полягає в назві якого-небудь M-значного числа в системі числення з підставою K (тобто, по суті, кожен учасник називає M цифр, кожна з яких лежить в діапазоні від 0 до K–1). Провідні нулі в числах допускаються.

У деякий момент прийом ставок на поточний розиграш завершується, і після цього ведучий в телеэфире називає число, що виграло (це також M-значное число в K-ичной системі числення). Після цього ті телеглядачі, у кого перша цифра їх числа співпала з першою цифрою числа, названого ведучим, отримують виграш у розмірі A1 рублів. Ті, у кого співпали перші дві цифри числа — отримують A2 рублів (при цьому якщо у гравця співпала друга цифра, але не співпала перша, він не отримує нічого). Що аналогічно вгадали перші три цифри отримують A3 рублів. І так далі. Що вгадали все число повністю отримують AM рублів. При цьому якщо гравець вгадав t перших цифр, то він отримує At рублів, але не отримує призи за вгадування t–1, t–2 і так далі цифр. Якщо гравець не вгадав першу цифру, він не отримує нічого.

Напишіть програму, яка по відомих ставках, зроблених телеглядачами, знаходить число, яке повинна назвати телеведущая, щоб фірма-організатор розиграшу виплатила як виграші мінімальну суму. Для вашої зручності ставки, зроблені гравцями, вже впорядковані по неубуванню.

Формат вхідних даних

У першому рядку задаються числа N (кількість телеглядачів, що зробили свої ставки, 1N100000), M (довжина чисел 1M10) і K (підстава системи числення 2K10). У наступному рядку записані M чисел A1, A2 ., AM, задаючих виграші у разі збігу тільки першою, перших два..., всіх цифр (1A1A2.A_M 100000). У кожному з наступних рядків N записано поодинці M-значному K-ичному числу. Числа йдуть в порядку неубування.

Формат вихідних даних

У першому рядку виведіть шукане число (якщо рішень декілька — виведіть будь-яке з них), а в другому рядку — суму, яку при назві телеведущей першого числа доведеться виплатити як виграш.

Приклади

j.in	j.out
10 3 2 1 3 100 000 000 001 010 100 100 100 100 110 111	011 6
1 1 10 100 0	7 0

Комерційний калькулятор

Ім'я вхідного файлу:	до.in
Ім'я вихідного файлу:	до.out
Максимальний час роботи на одному тесті:	3 секунди
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

Фірма OISAC випустила нову версію калькулятора. Цей калькулятор бере з користувача гроші за здійснювані арифметичні операції. Вартість кожної операції в доларах рівна 5% від числа, яке є результатом операції.

На цьому калькуляторі потрібно обчислити суму N натуральних чисел (числа відомі). Неважко відмітити, що від того, в якому порядку ми складатимемо ці числа, іноді залежить, в яку суму грошей нам обійдеться обчислення суми чисел (тим самим, виявляється порушений класичний принцип «від перестановки місць доданків сума не міняється»  ).

Наприклад, хай нам потрібно скласти числа 10, 11, 12 і 13. Тоді якщо ми спочатку складемо 10 і 11 (це обійдеться нам в $1.05), потім результат — з 12 ($1.65), і потім — з 13 ($2.3), то всього ми заплатимо $5, якщо ж спочатку окремо скласти 10 і 11 ($1.05), потім — 12 і 13 ($1.25) і, нарешті, скласти між собою два отримані числа ($2.3), то у результаті ми заплатимо лише $4.6.

Напишіть програму, яка визначатиме, за яку мінімальну суму грошей можна знайти суму даних N чисел.

Формат вхідних даних

У вхідному файлі записано число N (2N100000). Далі йде N натуральних чисел, які потрібно скласти, кожне з них не перевищує 10000.

Формат вихідних даних

У вихідний файл виведіть, скільки грошей нам буде потрібно на знаходження суми цих N чисел. Результат повинен бути виведений з двома знаками після десяткової крапки.

Приклади

до.in	до.out
4 10 11 12 13	4.60
2 1 1	0.10

Перетин кубів

Ім'я вхідного файлу:	l.in
Ім'я вихідного файлу:	l.out
Максимальний час роботи на одному тесті:	3 секунди
Максимальний об'єм використовуваної пам'яті:	64 мегабайти

У просторі з прямокутною системою координат знаходяться два куби. Про них відоме наступне:

сторона кожного куба рівна 2
центр (тобто центр симетрії) кожного куба співпадає з початком даної системи координат
координати вершин першого куба A1A2A3A4A5A6A7A8 наступні: A1(1, 1, 1), A2(1 –1, 1), A3(–1, –1, 1), A4(–1, 1, 1), A5(1, 1 –1), A6(1 –1, –1), A7(–1, –1, –1), A8(–1, 1 –1)
вершини другого куба B1B2B3B4B5B6B7B8 пронумеровані так, що шляхом повороту куби можна сумістити, і при цьому поєднаються відповідні їх вершини (A1 і B1, A2 і B2 ., A8 і B8)
координати вершин другого куба дані у вхідному файлі.

Потрібно знайти об'єм перетину (тобто загальній частині) цих кубів.

Формат вхідних даних

У вхідному файлі записано 8 трійок дійсних чисел – координати вершин другого куба B1B2B3B4B5B6B7B8.

Формат вихідних даних

У вихідний файл виведіть одне число – шуканий об'єм перетину кубів. Відповідь не повинна відрізнятися від вірного більш ніж на 0.00001.

Приклади

l.in	l.out
1.0000000000 -1.0000000000 1.0000000000 1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 -1.0000000000 1.0000000000 1.0000000000 1.0000000000 1.0000000000 1.0000000000 1.0000000000 -1.0000000000 -1.0000000000 1.0000000000 -1.0000000000 -1.0000000000 1.0000000000 1.0000000000	8.00000
1.4142135623730950488016887242097 0 1 0 -1.4142135623730950488016887242097 1 -1.4142135623730950488016887242097 0 1 0 1.4142135623730950488016887242097 1 1.4142135623730950488016887242097 0 -1 0 -1.4142135623730950488016887242097 -1 -1.4142135623730950488016887242097 0 -1 0 1.4142135623730950488016887242097 -1	6.62742

Сторінка из

Схожі:

Олімпіада школярів з програмування Дане N цілих чисел. Потрібно вибрати з них три таких числа, добуток яких максимально	Олімпіада школярів з програмування Таймер це годинник, який уміє подавати звуковий сигнал після деякого періоду часу. Напишіть програму, яка визначає, коли повинен...
Олімпіада школярів з програмування Автобус може проїхати під мостом тоді і тільки тоді, коли висота моста перевершує висоту автобуса. Допоможіть організаторам дізнатися,...	Олімпіада школярів з програмування За наслідками роботи програми на кожному тесті учасникові або нараховуються бали за цей тест (коли програма видала правильну відповідь),...
Програма курсу програмування на мов і С++ Курс націлений на отримання знань і практичних навиків програмування на мовах C і C + + в рамках процедурно-орієнтованого програмування....	Основні методології (стилі, парадигми) програмування. Поняття програми.... Дів розробки програм Граді Буча “О’єктно-орієнтоване програмування (ООП) – це методологія програмування, яка заснована на представленні...
29. Опис та використання підпрограм Реалізація базових алгоритмічних структур процедурною мовою програмування. Опис процедур та функцій процедурною мовою програмування....	2. Дробово-лінійне програмування Постановка задачі дробово-лінійного... Дослідження операцій”, “Економетрія”, “Моделювання економіки”, “Економічна кібернетика” а також дисциплін циклу загальноекономічної...
Курс програмування на С # Зусилля, які ви витратите на вивчення С #, будуть винагороджені, так як Сі Шарп був розроблений в якості основної мови програмування,...	ЗАТВЕРДЖУЮ Всеукраїнська студентська олімпіада (далі – Олімпіада) – система масових очних змагань у творчому застосуванні здобутих знань, умінь...

Додайте кнопку на своєму сайті:
Портал навчання