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


Скачати 136.41 Kb.
НазваОлімпіада школярів з програмування
Дата19.05.2013
Розмір136.41 Kb.
ТипДокументи
bibl.com.ua > Фізика > Документи

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

  1. Таймер

Ім'я вхідного файлу:

а.in

Ім'я вихідного файлу:

а.out

Максимальний час роботи на одному тесті:

2 секунди

Максимальний об'єм використовуваної пам'яті:

8 мегабайт

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

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

У першому рядку вхідного файлу записаний поточний час у форматі Чч:мм:сс (з провідними нулями). При цьому воно задовольняє обмеженням: ЧЧ - від 00 до 23, ММ і СС - від 00 до 60.

У другому рядку записаний інтервал часу, який повинен бути зміряний. Інтервал записується у форматі Ч:м:с (де Ч, М і З - від 0 до 109, без провідних нулів). Додатково якщо Ч=0 (або Ч=0 і М=0), то вони можуть бути опущені. Наприклад, 100:60 насправді означає 100 хвилин 60 секунд, що те ж саме, що 101:0 або 1:41:0. А 42 позначає 42 секунди. 100:100:100 - 100 годин, 100 хвилин, 100 секунд, що те ж саме, що 101:41:40.

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

У вихідний файл виведіть у форматі Чч:мм:сс час, в скільки прозвучить звуковий сигнал. При цьому якщо сигнал прозвучить не в поточну добу, то далі повинен слідувати запис +<кіл> days. Наприклад, якщо сигнал прозвучить наступного дня – то +1 days.

Приклади

а.in

а.out

01:01:01

48:0:0

01:01:01+2 days

01:01:01

58:119

02:01:00

23:59:59

1

00:00:00+1 days



  1. Додому на електричках

Ім'я вхідного файлу:

b.in

Ім'я вихідного файлу:

b.out

Максимальний час роботи на одному тесті:

3 секунди

Максимальний об'єм використовуваної пам'яті:

8 мегабайт

Одна з команд-учасниць олімпіади вирішила повернутися додому на електричках. При цьому хлоп'ята хочуть потрапити додому якомога раніше. На жаль, не всі електрички йдуть від міста, де проводиться олімпіада, до станції, на якій живуть хлоп'ята. І, що ще образливіше, не всі електрички, які йдуть повз їх станцію, зупиняються на ній (так само як і взагалі, електрички зупиняються далеко не на всіх станціях, повз які вони йдуть).

Всі станції на лінії пронумеровані числами від 1 до N. При цьому станція номер 1 знаходиться в місті, де проводиться олімпіада, і у момент часу 0 хлоп'ята приходять на станцію. Станція, на яку потрібно потрапити хлоп'ятам, має номер E.

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

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

У вхідному файлі записані спочатку числа N (2 N 100) і E (2 E N). Потім записано число M (0  M  100), що позначає число рейсів електричок. Далі йде опис M рейсів електричок. Опис кожного рейса електрички починається з числа Ki (2 Ki N) — кількості станцій, на яких вона зупиняється, а далі слідує Ki пар чисел, перше число кожної пари задає номер станції, друге — час, коли електричка зупиняється на цій станції (час виражається цілим числом з діапазону від 0 до 109). Станції усередині одного рейса впорядковані в порядку зростання часу. Протягом одного рейса електричка весь час рухається в одному напрямі — або від міста, або до міста.

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

У вихідний файл виведіть одне число — мінімальний час, коли хлоп'ята зможуть опинитися на своїй станції. Якщо існуючими рейсами електричок вони добратися не зможуть, виведіть –1.

Приклад

b.in

b.out

5 3

4

2 1 5 2 10

2 2 10 4 15

4 5 0 4 17 3 20 2 35

3 1 2 3 40 4 45

20




  1. Клад

Ім'я вхідного файлу:

з.in

Ім'я вихідного файлу:

з.out

Максимальний час роботи на одному тесті:

2 секунди

Максимальний об'єм використовуваної пам'яті:

32 мегабайти

Знайти закопаний піратами клад просто: все, що для цього потрібне – це карта. Як відомо, пірати зазвичай малюють карти від руки і описують алгоритм знаходження кладу так: «Встаньте біля самотньої пальми. Пройдіть тридцять кроків у бік лісу, потім сімнадцять кроків у бік озера ., нарешті десять кроків у бік великого булижника. Клад знаходиться під ним». Велика частина таких вказівок просто зводиться до проходження якоїсь кількості кроків в одному з восьми напрямів (1 – північ, 2 – північний схід, 3 – схід, 4 – південний схід, 5 – південь, 6 – південний захід, 7 – захід, 8 – північний захід) (див. рис). Довжина кроку в будь-якому напрямі рівна 1.

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



Вам необхідно написати програму, яка по вказівках піратів визначає крапку, де заритий клад.

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

Перший рядок вхідного файлу містить число N – число вказівок (1ХNХ40). Подальші N рядків містять самі вказівки – номер напряму (ціле число від 1 до 8) і кількість кроків (ціле число від 1 до 1000). Числа розділені пропусками.

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

У вихідний файл виведіть координати X і Y крапки (два дійсні числа, розділені пропуском), де заритий клад, вважаючи, що вісь Ox направлена на схід, а вісь Oy – на північ. На початку шукач скарбів повинен стояти на початку координат. Координати необхідно вивести з погрішністю не більше 10-3.

Приклади

з.in

з.out

6

1 3

3 1

1 1

3 3

5 2

7 1

3.000 2.000

1

8 10

-7.071 7.071




  1. Забавна гра

Ім'я вхідного файлу:

d.in

Ім'я вихідного файлу:

d.out

Максимальний час роботи на одному тесті:

3 секунди

Максимальний об'єм використовуваної пам'яті:

8 мегабайт

Легендарний вчитель математики Юрій Петрович придумав забавну гру з числами. А саме, узявши довільне ціле число, він переводить його в двійкову систему числення, отримуючи деяку послідовність з нулів і одиниць, що починається з одиниці. (Наприклад, десяткове число 1910 = 124+023+022+121+120 в двійковій системі запишеться як 100112.) Потім вчитель починає зрушувати цифри отриманого двійкового числа по циклу (так, що остання цифра стає першою, а всі останні зрушуються на одну позицію управо), виписуючи послідовності, що утворюються при цьому, з нулів і одиниць в стовпчик — він помітив, що незалежно від вибору початкового числа послідовності, що виходять, починають з деякого моменту повторюватися. І, нарешті, Юрій Петрович відшукує максимальне з виписаних чисел і переводить його назад в десяткову систему числення, вважаючи це число результатом виконаних маніпуляцій. Так, для числа 19 список послідовностей буде таким:

10011

11001

11100

01110

00111

10011

.

і результатом гри, отже, опиниться число 124+123+122+021+020 = 28.
Оскільки придумана гра з числами все більше займає уяву вчителя, відволікаючи тим самим його від роботи з ну дуже обдарованими школярами, Вас просять написати програму, яка б допомогла Юрієві Петровичеві отримувати результат гри без утомливих ручних обчислень.

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

Вхідний файл містить одне ціле число N (0N32767).

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

Ваша програма повинна вивести у вихідний файл одне ціле число, рівне результату гри.

Приклад

d.in

d.out

19

28




  1. Цілі крапки

Ім'я вхідного файлу:

e.in

Ім'я вихідного файлу:

e.out

Максимальний час роботи на одному тесті:

2 секунди

Максимальний об'єм використовуваної пам'яті:

32 мегабайти

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

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

У першому рядку міститься N (3-N-1000) – число вершин багатокутника. У подальших N рядках йдуть координати (XiYi) вершин багатокутника в порядку обходу за годинниковою стрілкою. Xi і Yi - цілі числа, по модулю що не перевершують 1000000.

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

У вихідний файл вивести одне число – шукане число крапок.

Приклади

e.in

e.out

4

-1 -1

-1 1

1 1

1 -1

1

3

0 0

0 2

2 0

0

  1. Степінь

Ім'я вхідного файлу:

f.in

Ім'я вихідного файлу:

f.out

Максимальний час роботи на одному тесті:

2 секунди

Максимальний об'єм використовуваної пам'яті:

32 мегабайти

Для того, щоб перевірити, як її учні уміють вважати, Марія Іванівна щороку задає їм додому одне і те ж завдання – для заданого натурального A знайти мінімальне натуральне N таке, що N в степені N (N, помножене на себе N разів) ділиться на A. Від року до року і від учня до учня міняється тільки число A.

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

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

У вхідному файлі міститься однина A (1-A-1000000000 – про всяк випадок; раптом Марія Іванівна задасть велике число, щоб «завалити» кого-небудь.).

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

У вихідний файл вивести однину N.

Приклади

f.in

f.out

8

4

13

13



  1. Гра з фішками

Ім'я вхідного файлу:

g.in

Ім'я вихідного файлу:

g.out

Максимальний час роботи на одному тесті:

2 секунди

Максимальний об'єм використовуваної пам'яті:

32 мегабайти

Ви є одним з розробників нової комп'ютерної гри. Гра відбувається на прямокутній дошці, що складається з W*H кліток. Кожна клітка може або містити, або не містити фішку (див. малюнок).

Важливою частиною гри є перевірка того, чи сполучено дві фішки шляхом, задовольняючим наступним властивостям:

  1. Шлях повинен складатися з відрізань вертикальних і горизонтальних прямих.

  2. Шлях не повинен перетинати інших фішок.

При цьому частина шляху може опинитися поза дошкою. Наприклад:



Фішки з координатами (1,3) і (4,4) можуть бути сполучені. Фішки з координатами (2,3) і (5,3) теж можуть бути сполучені. А ось фішки з координатами (2,3) і (3,4) з'єднати не можна – будь-який шлях, що сполучає їх, перетинає інші фішки.

Вам необхідно написати програму, перевіряючу, чи можна з'єднати дві фішки шляхом, що володіє вищезгаданими властивостями, і, у разі позитивної відповіді, що визначає мінімальну довжину такого шляху (вважається, що шлях має злами, почало і кінець тільки в центрах кліток (або «уявних кліток», розташованих поза дошкою), а відрізок, що сполучає центри двох сусідніх кліток, має довжину 1).

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

Перший рядок вхідного файлу містить два натуральні числа: W – ширина дошки, H – висота дошки (1-W,H-75). Наступні H рядків містять опис дошки: кожен рядок складається рівно з W символів: символ «X» (заголовна англійська буква «экс») позначає фішку, символ «.» (крапка) позначає порожнє місце. Решту всіх рядків містять описи запитів: кожен запит складається з чотирьох натуральних чисел, розділених пропусками, – X1, Y1, X2, Y2, причому 1-X1,X2-W, 1-Y1,Y2-H. Тут (X1, Y1) і (X2, Y2) – координати фішок, які потрібно з'єднати (ліва верхня клітка має координати (1,1)). Гарантується, що ці координати не співпадатимуть (окрім останнього запиту; див. далі). Останній рядок містить запит, що складається з чотирьох чисел 0; цей запит обробляти не треба. Кількість запитів не перевершує 20.

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

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

Приклади

g.in

g.out

5 4

XXXXX

X...X

XXX.X

.XXX.

2 3 5 3

1 3 4 4

2 3 3 4

0 0 0 0

5

6

0

4 4

XXXX

.X..

..X.

X...

1 1 3 1

0 0 0 0

4

  1. Розкопки

Ім'я вхідного файлу:

h.in

Ім'я вихідного файлу:

h.out

Максимальний час роботи на одному тесті:

2 секунди

Максимальний об'єм використовуваної пам'яті:

32 мегабайти

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

Учені змогли зрозуміти, що в цьому випадку означають знайдені символи, і переклали цю рівність звичайною мовою – мовою цифр, дужок, знаків арифметичних дій і рівності. Крім того, з інших джерел було отримано вагомий доказ того, що марсіани знали тільки три операції – складання, множення і віднімання (марсіани ніколи не використали «унарний мінус»: замість «-5» вони писали «0-5»). Також учені довели, що марсіани не наділяли операції різним пріоритетом, а просто обчислювали вирази (якщо в них не було дужок) зліва направо: наприклад, 3+3*5 у них дорівнювало 30, а не 18.

На жаль, символи арифметичних дій марсіани чомусь наносили спеціальним чорнилом, яке, як виявилось, були не дуже стійкими, і тому в знайдених листках між числами замість знаків дій були пропуски. Якщо вся вищевикладена теорія вірна, то замість цих пропусків можна поставити знаки складання, віднімання і множення так, щоб рівність стала вірною. Наприклад, якщо був знайдений лист паперу з написом «18=7 (5 3) 2», то можлива така розстановка знаків: «18=7+(5-3)*2» (пам'ятаєте про те, в якому порядку марсіани обчислюють вирази!). В той же час, якщо попався лист з написом «5=3 3», то марсіани явно не мали на увазі числової рівності, коли писали це.

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

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

Перший рядок вхідного файлу складається з натурального (цілого позитивного) числа, що не перевершує 230, знаку рівності, і послідовності натуральних чисел (не більше десяти), твір яких також не перевершує 230. Деякі групи чисел (одне або більш) можуть бути оточені дужками. Довжина вхідного рядка не перевершуватиме 80 символів, і інших обмежень на кількість і вкладеність дужок немає. Між двома сусідніми числами, не розділеними дужками, завжди буде хоч би один пропуск, в решті всіх місць може бути будь-яке (у тому числі і 0) число пропусків (природно, усередині числа пропусків немає).

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

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

Приклади

h.in

h.out

18=7 (5 3) 2

18=7+(5-3)*2

5= 3 3

-1




  1. Села

Ім'я вхідного файлу:

i.in

Ім'я вихідного файлу:

i.out

Максимальний час роботи на одному тесті:

2 секунди

Максимальний об'єм використовуваної пам'яті:

32 мегабайти

У тридесятій державі є N сіл. Деякі пари сіл сполучені дорогами. В цілях економії, «зайвих» доріг немає, тобто з будь-якого села в будь-яку можна добратися по дорогах єдиним чином.

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

Ви повинні написати програму, що допомагає йому в цьому.

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

Перший рядок вхідного файлу містить два числа: N і P (1-P-N-150). Решту всіх рядків містять описи дорогий, поодинці на рядку: опис дороги складається з двох номерів сіл (від 1 до N), які ця дорога сполучає. Всі числа у вхідному файлі розділені пропусками і/або перекладами рядка.

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

У вихідний файл виведіть однину – шукана кількість дорогий.

Приклади

i.in

i.out

3 2

1 2

3 2

1

11 6

1 2

1 3

1 4

1 5

2 6

2 7

2 8

4 9

4 10

4 11

2

Коментар. У другому прикладі група сіл (1,2,3,6,7,8) виявиться ізольованою від останніх, якщо зруйнувати дороги 1-4 і 1-5.


Сторінка из

Схожі:

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


При копіюванні матеріалу обов'язкове зазначення активного посилання © 2013
звернутися до адміністрації
bibl.com.ua
Головна сторінка