XVIIІ обласна олімпіада з інформатики (Хмельницька обл.)
7 лютого 2004 року
1 тур (теоретичний)

Задача 1.  Вираз (20 балів)

Задані дійсні числа c, d. Обчислити значення виразу з чотирма десятковими знаками

 

де x1 – більший, а x2  – менший корені рівняння   Вхідні дані вводяться із вхідного стандартного потоку (клавіатура), а вихідні дані виводяться у стандартний вихідний потік (екран). Зайвих коментарів виводити не потрібно.

 

Задача 2. Шифровка (25 балів)

Відомо, що учасники обласної олімпіади Дунець Павло, Печений Олександр та Райчук Антон на зимові канікули запрошувалися на збори за результатами успішного виступу на минулорічній Всеукраїнській олімпіаді, що відбулася в Донецьку. Для них і всіх інших учасників обласної олімпіади журі склало шифровку, яка записана у файлі text.dat. Спосіб шифрування не відомий, але відомо, що літери та інші символи не змінювалися. Змінено лише місце їх розташування. Вам слід отримати розшифрований текст і записати його у файл uxxxn2.txt, де xxx – Ваш реєстраційний номер (при потребі реєстраційний номер уточніть у чергового члена журі).

 

Задача 3. ZOI_2003 (40 балів)

У відкритій заочній Інтернет-олімпіаді з інформатики сезону 2003-2004 взяли участь 171 учасник з N населених пунктів. Окремі з цих населених пунктів з’єднані дорогами відомої довжини. Вся система доріг задана квадратною таблицею розмірності N, елемент aij якої дорівнює деякому від’ємному числу, якщо населений пункт і не з’єднаний напряму дорогою з населеним пунктом j і дорівнює довжині дороги в протилежному випадку ( і, j = 1, 2, …, N).

a)       Для 1-го населеного пункту знайти найкоротші маршрути в інші населені пункти.

b)       Для k-го населеного пункту знайти найкоротші маршрути в інші населені пункти.

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

В першому рядку записане число N.

В наступних N рядках записана квадратна таблиця, елементи якої розділені  пропуском. В N+2 рядку записане число k (або число 1 для випадку a)).

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

В N-1 рядку записані маршрути. Рядок починається числом – номером населеного пункту, з якого починається маршрут, а закінчується числом – номером пункту призначення. Між ними через пропуск записані номери населених пунктів, через які треба добиратися.

 

Задача 4. Різні результати (15 балів)

Обчислити    вираз чотирма способами:

a)       послідовно зліва направо;

b)       послідовно зліва направо обчислюється  і , потім друге значення віднімають від першого;

c)       послідовно справа наліво;

d)       послідовно справа наліво обчислюють суми, що описані в b), потім проводять віднімання.

У файл uxxxn4.txt, де xxx-реєстраційний номер учасника, виведіть в окремих рядках результати отриманих обчислень. Починаючи з п’ятого рядка напишіть пояснення отриманих результатів. (Пояснення можна писати в редакторі Блокнот).

 

Примітка. Задачі називати за правилом:  uxxxn1.pas (або bas чи cpp) для першої задачі, :  uxxxn3a.pas (або bas чи cpp) для третьої задачі пункт a), :  uxxxn3b.pas (або bas чи cpp) для третьої задачі пункт b), де xxx – реєстраційний номер учасника. Для другої та четвертої задач здавати текстові файли, а програми здавати  не треба.

XVIIІ обласна олімпіада з інформатики (Хмельницька обл.)
8 лютого 2004 року

2 тур (практичний)

 

Задача 5. Екзамен

Коли Максим Розуменко вчився у фінансовому коледжі, у нього були дуже погані стосунки з вчителем інформатики. Тому, на випускному екзамені вчитель дав йому індивідуальне завдання. Так як Максим був крутим хакером, він зміг скопіювати з сервера 10 тестів, на яких вчитель збирався тестувати його розв’язок. На жаль, на сервері не було відповідей на ці тести. І зараз Максиму якнайшвидше потрібно знайти відповіді.

Завдання.
Вчитель задав Максиму таке завдання:

"На проміжку [A,B] необхідно знайти кількість натуральних чисел X таких, що:

1) X, X+1, X+2, ..., X+K-1 належать [A,B];

2) для кажного натурального Y з [X, X+K-1] знайдеться натуральне Z<>Y з [X,X+K-1] таке, що у чисел Z і Y є хоча б один спільний дільник більший 1.

Крім того, знайдіть хоча б одне таке X (якщо воно існує)."

Вхідні данні.
Вам дається 10 вхідних файлів з іменами 1.IN, 2.IN, ..., 10.IN. В кажному з них записані три числа: K, A, B - по одному числу в рядку.

Вихідні дані.
Вам потрібно здати на преревірку 10 вихідних файлів з іменами 1.OUT, 2.OUT, ..., 10.OUT, де i.OUT - вихідний файл для i.IN (i = 1, 2, ..., 10). Кожний з цих файлів повинен містити два рядки. В першому рядку повинно бути записана кількість чисел X, що задовільняють вищезаписані умови. В другому рядку повинно бути записане одне з таких X. У випадку, коли таких X не існує, файл повинен складатися з одного числа - 0.

 

Задача 6. Телепортація

Вхідний файл: стандартний вхідний потік
Вихідний файл: стандартний вихідний потік
Час на тест: 1 секунда

Розглянемо прямокутну декартову систему координат OXY (будемо вважати її моделлю Всесвіту). Припустимо, що в точці (x1, y1) знаходиться космічний корабель. За одну секунду з точки (x, y) він може телепортуватися в точки (x+C, y+C), (x+C, y-C), (x-C, y+C), (x-C, y-C), де C - довільне натуральне число. Який мінімальний час знадобиться кораблю для того, щоб досягти точки (x2, y2)?

Введення

Ваша програма повинна вводити з клавіатури числа x1, y1, x2, y2. Числа x1 і y1 повинні бути введені в першому рядку, числа x2 і y2 - в другому рядку.

Виведення

Якщо можна досягти точку (x2, y2) з точки (x1, y1), то виведіть на екран мінімальний час в секундах, необхідний для цього. В противному випадку виведіть на екран число 0.

Приклад

Введення
0 0
0 2

Виведення
2

В даному прикладі до успіху приводить така послідовність телепортацій:

(0, 0) - (1, 1) - (0, 2).

Обмеження.

0≤x1, y1, x2, y2≤1000000000; всі числа при введенні цілі; точки (x1, y1) і (x2, y2) не співпадають.

Зауваження.

Якщо ваша програма видає однакову відповідь на всіх тестових прикладах, то вона отримає 0 балів.

 

Задача 7. Копперфільд

Вхідний файл: input.txt
Вихідний файл: output.txt
Час на тест: 1 секунда

Кожний рік відомий іллюзіоніст Копперфільд проводить копперфільдівську лотерею. Переможець лотереї отримує право зіграти з Копперфільдом в гру в його замку, результат якої визначає виграш переможця. Замок складається з M*N червоних і зелених квадратних кімнат, які розміщуються в шахматному порядку. В деяких кімнатах замку включене світло. Переможець лотереї (гравець) спочатку вибирає любу кімнату кольору, який вкаже Копперфільд, і в якій горить світло. В кажній кімнаті лежить чек на $1000, і гравець, проходячи через кімнату, забирає чек собі. Щоб обмежити переміщення гравця, Копперфільд виключає світло в деяких кімнатах, після чого гравець переходить в одну із сусідніх кімнат, в якій ще горить світло. Гра закінчується, коли гравець опиняється в єдиній світлій кімнаті. Тоді гравець виграє ту суму грошей, яку він зібрав, проходячи через кімнати замку. Якщо ж в процесі гри Копперфільд виключить світло в кімнаті, в якій знаходиться гравець, то гравець отримує всі M*N*1000 доларів. Копперфільд діє так, щоб навіть при найбільш несприятливих для Копперфільда діях гравця, той зібрав якомога менше чеків. Визначити гарантований виграш гравця.

Пояснення.

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

Вхідні дані

Першими задаються розміри замку M і N (4 < N, M < 100). Потім, починаючи з нового рядка, задається план замку. План замку складається з M рядків тексту по N символів в кожному рядку. Символ "0" означає, що світло в текучій кімнаті виключене, а символ "1" - включене. Всі освітлені кімнати замку зв’язані одна з одною, тобто із однієї освітленої кімнати замку завжди можна пройти в любу іншу освітлену кімнату, проходячи тільки через освітлені кімнати. В замку в початковий момент гри є не більше ніж 2000 освітлених кімнат.

Вихідні дані

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

Приклади 

5 5                                                                                                 2 2 2
00100
00100
11111
00100
00100
 
5 5                                                                                                 4 1 3
00000
11110
11110
11110
11110

Задача 8. Інкасатори

Вхідний файл: input.txt
Вихідний файл: output.txt
Час на тест: 2 секунди

Коли Максим Розуменко закінчив фінансовий коледж, він став керуючим міського банку. Вже з перших днів роботи Максим зіткнувся з однією нерозв’язаною для нього проблемою.

В країні, де живе Максим, є N міст. Деякі з них зв’язані двохсторонніми дорогами, які перетинаються тільки в містах. Раз на місяць інкасатори Максима повинні доставити гроші в K зберігальних кас. Всі K зберігальних кас знаходяться в різних містах. Поки банк Максима небагатий і має всього одну машину для перевезення грошей. Вам необхідно допомогти Максиму скласти маршрут, який починається в місті L (в цьому місті знаходиться банк Максима), проходить по всіх K містах, де знаходяться потрібні зберігальні каси, і закінчується також в місті L. Цей маршрут повинен мати мінімальну довжину (довжиною маршруту назвемо суму довжин всіх доріг, що входять в цей маршрут).

Вхідні дані: input.txt

В першому рядку через пропуск записані три числа: N M K, де N – загальне число  міст в країні, M - загальне число  двохсторонніх доріг, K - кількість зберігальних кас, які повинні відвідати інкасатори (без врахування міста L).

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

Наступні M рядків містять опис доріг. В кожному рядку описується одна дорога у виді X Y S, де X,Y - номери міст, які зв’язані дорогою і S - довжина цієї дороги.

В останньому рядку дано число L - номер міста, де знаходиться банк Максима.

Вихідні данні: output.txt

Єдиний рядок вихідного файла повинен містити набір чисел - номери міст шуканого маршруту в порядку обходу. Ці числа повинні бути розділені одинарним пропуском. У випадку, коли такого маршруту не існує, вихідний файл повинен містити одне слово "NO".

Обмеження.

1 < N <= 100
0 < M <= N(N-1)/2
0 < K < 18, K < N
0 < S <= 50000
1 <= L,X,Y <= N
Всі вхідні данні - натуральні числа.

input.txt                 output.txt                     input.txt                  output.txt
4 6 3                     1 3 2 4 1                      6 9 2                       1 2 6 4 3 5 2 1   
2 4 3                                                         3 4 
1 2 10                                                       1 3 24            
2 4 3                                                         1 2 10            
1 3 5                                                         2 6 5 
1 4 4                                                         2 5 6
3 2 7                                                         3 5 7
4 3 8                                                         3 4 16
1                                                               4 5 9
                                                                 4 6 8
                                                                 5 6 4  
                                                                 1
 

 

Примітка. Задачі називати за правилом:  uxxn6.pas (або bas чи cpp) для шостої задачі,   uxxn7.pas (або bas чи cpp) для сьомої задачі,  uxxn8.pas (або bas чи cpp) для восьмої задачі, де xx – код учасника. Для п’ятої задачі здавати 10 текстових файлів в папці uxxn5, де xx – код учасника, а самі програми здавати  не треба.