|
Завдання
|
Написав Стеблевець Олександр Леонідович
|
|
Понеділок, 06 грудня 2010, 09:12 |
|
1. Задача METRO (20 балів)
Ім’я вхідного файлу: METRO.DAT
Ім’я вихідного файлу: METRO.SOL
Максимальний час роботи на одному тесті: 20с
Метрополітен складається з декількох ліній метро. Усі станції метро в місті пронумеровані натуральними числами від 1 до N. На кожній лінії розташовано декілька станцій. Якщо одна і та ж станція розташована відразу на декількох лініях то вона є станцією пересадки і на цій станції можна пересісти з будь-якої лінії, яка через неї проходить, на будь-яку іншу (що знову ж таки проходить через неї).
Напишіть програму, яка по даному вам опису метрополітену визначить з яким мінімальним числом пересадок можна добратися із станції A на станцію B. Якщо цей метрополітен не сполучає усі лінії в одну систему, то може так вийти, що із станції A на станцію B добратися неможливо, в цьому випадку ваша програма повинна це визначити.
Формат вхідних даних
У вхідному файлі записано спочатку число N - кількість станцій метро в місті (2≤N≤100). Далі записано число M - кількість ліній метро (1≤M≤20). Далі йде опис M ліній. Опис кожної лінії полягає з числа Pi - кількість станцій на цій лінії (2≤Pi≤50) і Pi чисел, що задають номери станцій, через які проходить лінія (ні через яку станцію лінія не проходить двічі).
У кінці файлу записані два різних: числа A - номер початкової станції, і B - номер станції, на яку нам треба потрапити. При цьому якщо через станцію A проходить декілька ліній, то ми можемо спуститися на будь-яку з них. Так само якщо через станцію B проходить декілька ліній, то нам не важливо, по якій лінії ми приїдемо.
Формат вихідних даних
У вихідний файл виведіть мінімальну кількість пересадок, яка нам знадобиться. Якщо добратися із станції A на станцію B неможливо, виведіть у вихідний файл одне число - 1 (мінус один).
Приклад
|
METRO.DAT
|
METRO.SOL
|
|
5
2
4 1 2 3 4
2 5 3
3 1
|
0
|
|
5
5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5
|
2
|
|
10
2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8
|
1
|
|
4
2
2 1 2
2 3 4
1 3
|
-1
|
2. Задача “Школи” (100 балів)
Ім’я вхідного файлу: S.DAT
Ім’я вихідного файлу: S.SOL
Максимальний час роботи на одному тесті: 20с
З метою підготовки до проведення олімпіади з інформатики мер вирішив забезпечити надійним електропостачанням всі школи міста. Для цього потрібно провести лінію електропередач від альтернативного джерела електроенергії "ЕНЕРГЕТИК" до однієї з шкіл (не має значення до якої), а також з'єднати лініями електропередач деякі школи між собою. Вважається, що школа має надійне електропостачання, якщо вона напряму з’єднана з "ЕНЕРГЕТИК", або з однією з шкіл, яка має надійне електропостачання.
Відома вартість з’єднань між деякими парами шкіл. Мер міста вирішив обрати одну з двох найекономніших схем електропостачання (вартість схеми дорівнює сумі вартостей з’єднань пар шкіл).
Складіть програму SCHOOLS, яка обчислює вартість двох найекономічніших схем альтернативного енергопостачання шкіл.
Формат вхідних даних
У першому рядку вхідного файлу S.DAT розташовані два натуральних числа, відокремлених пропусками: N (3 ≤ N ≤ 100), кількість шкіл в місті, та M - кількість можливих з’єднань між ними. В кожному з наступних M рядків знаходяться по три числа: Ai, Bi, Ci, відокремлених пропусками, де Ci - вартість прокладання лінії електропостачання (1 ≤ Ci ≤ 300) від школи Ai до школи Bi (i=1,2,…,N).
Формат вихідних даних
В єдиному рядку вихідного файлу S.SOL мають міститись два натуральних числа S1 та S2, відокремлених пропусками – дві найменші вартості схем (S1≤S2). S1=S2 тільки тоді, коли існує декілька варіантів схем надійного електропостачання найменшої вартості.
Приклад
|
S.DAT
|
S.SOL
|
|
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
|
110 121
|
|
|
Останнє оновлення на Четвер, 08 вересня 2011, 07:28 |
|
|
Написав Глова Анатолий Миколайович
|
|
Понеділок, 22 листопада 2010, 01:59 |
|
Розв’язки задач відправляти з 22.11 по 5.12.2010 р.
Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.
1. Задача DOMINO (20 балів)
Ім’я вхідного файлу: DOMINO.DAT
Ім’я вихідного файлу: DOMINO.SOL
Максимальний час роботи на одному тесті: 20с
Написати програму, яка буде підраховувати кількість варіантів покриття прямокутника 2хN прямокутниками 2х1. Покриття, які перетворюються одне в одне симетріями рахувати різними.
Вхідні дані. Вхідний файл DOMINO.DAT містить число N (0 < N < 65536).
Вихідні дані. Вихідний файл DOMINO.SOL повинен містити одне число: кількість варіантів.
Приклади вводу і виводу
DOMINO.DAT :
1
DOMINO.SOL :
1
2. Задача FRACTION(100 балів)
Ім’я вхідного файлу: FRACTION.DAT
Ім’я вихідного файлу: FRACTION.SOL
Максимальний час роботи на одному тесті: 3с
Знайти суму двох нескоротних дробів A/B i C/D. Результат записати у вигляді нескоротного дробу.
Вхідні дані. Вхідний файл FRACTION.DAT містить числа A, B, C, D (1 < A, B, C, D < 10^1000), кожне з яких записане в окремому рядку.
Вихідні дані. Вихідний файл FRACTION.SOL повинен містити два числа, записаних у різних рядках: чисельник дробу і знаменник дробу.
Приклади вводу і виводу
FRACTION.DAT :
1
6
1
3
FRACTION.SOL :
1
2
|
|
Останнє оновлення на Четвер, 08 вересня 2011, 07:29 |
|
Написав Давидюк Віталій Саватійович
|
|
Понеділок, 08 листопада 2010, 09:00 |
|
Четвертий тур
Розв’язки задач відправляти з 08.11 по 21.11.2010 р.
Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.
1. Задача river (20 балів)
Ім’я вхідного файлу: river.DAT
Ім’я вихідного файлу: river.SOL
Максимальний час роботи на одному тесті: 3с
Між двома королівствами Читанія та Писанія протікає річка Пряма, яка тече або з Півночі на Південь, або з Заходу на Схід. Король Писанії вирішив завоювати Читанію. Для нападу необхідно збудувати переправу.
Де розпочинати будівництво, якщо король хоче, щоб всі війська, що розташовані в N (1<=N<=100) гарнізонах, могли якнайшвидше зібратися біля переправи? Війська вирушають з пунктів дислокації одночасно і рухаються з однаковою швидкістю по прямій до переправи.
Формат вхідних даних
Перший рядок вхідного файлу містить чотири цілих числа: a1, a2, b1, b2 ((a1,a2), (b1,b2) – координати двох точок річки Прямої).
Відомо, що або a1=b1 , або a2=b2, -30000<=a1, a2, b1, b2 <=30000.
У другому рядку знаходиться ціле число N – кількість гарнізонів (1<=N<=100).
В наступних N рядках записано по два цілих числа xj та yj – координати гарнізонів
(-30000<= xj,yj<=30000), відокремлених одним пробілом.
Формат вихідних даних
Ваша програма повинна вивести у вихідний файл рядок, що містить два числа X, Y – координати переправи з точністю до двох знаків після коми, розділених одним пропуском.
Приклад
|
river.DAT
|
river.SOL
|
|
2 1 2 4
4
3 2
6 3
9 9
8 6
|
2.00 8.75
|
2. Задача Island (100 балів)
Ім’я вхідного файлу: Island.DAT
Ім’я вихідного файлу: Island.SOL
Максимальний час роботи на одному тесті: 5с
Якось на Багатокутію напали Трикутники. Королівство Багатокутія лежить на острові і займає всю його територію. Острів має вигляд опуклого багатокутника (такого багатокутника, у якого кожен внутрішній кут менший від 180°). У Багатокутії знаходиться певне число фабрик програмного забезпечення. Кожна фабрика приносить певні постійні прибутки або збитки.
Трикутники вирішили заволодіти частиною площі Багатокутії, яка має наступні властивості:
• має вигляд трикутника, вершинами якого є три різні вершини багатокутника-острова;
• принесе їм якнайбільші прибутки, тобто сума прибутків (збитків), що приносять фабрики, які знаходяться на території, буде якнайбільшою.
Відомо, що якщо фабрика лежить на границі або у вершині території, якою заволоділи Трикутники, то вона належить їй. Територія, яка не містить жодної фабрики, приносить прибуток рівний 0.
Король Багатокутії вирішив порахувати, наскільки великі збитки для економіки країни може принести нашестя Трикутників. Допоможіть йому і напишіть програму, яка визначає суму прибутків (збитків), що дають фабрики, якими хочуть заволодіти Трикутники.
Формат вхідних даних
Перший рядок вхідного файлу містить одне ціле число n (3<=n<=600), число вершин багатокутника-острова.
В наступних n рядках записано по два цілих числа xj та yj - координати вершин багатокутника-острова у порядку його обходу за годинниковою стрілкою (-10000<= xj,yj<=10000), відокремлених одним пробілом.
В (n+2)-му рядку міститься одне ціле число m – число фабрик (1<=m<=10000), що розташовані на острові.
В наступних m рядках міститься по три цілих числа: x'i, y'i і wi (-10000<=x'i, y'i<=10000, -100000<=wi<=100000), відокремлених одним проміжком і такі, що означають відповідно x'i, y'i – координати фабрик, а також прибуток (для wi>=0) або збиток (для wi<0), який фабрика приносить. Кожна фабрика лежить на острові-багатокутнику, тобто всередині його або на його границі (березі). Декілька фабрик можуть лежати в одному і тому ж місці, тобто мати ті самі координати.
Формат вихідних даних
Перший і єдиний рядок вихідного файлу повинен містити одне ціле число, що означає максимальну суму прибутків, які приносять фабрики, що знаходяться в межі трикутника, вершинами якого є три різні вершини багатокутника-острова. Може бути, що число це буде від’ємним.
Приклад
|
Island.DAT
|
Island.SOL
|
|
5
4 1
1 4
8 9
11 5
8 1
4
7 2 3
6 3 -1
4 5 3
9 6 -4
|
5
|
|
|
Останнє оновлення на Четвер, 08 вересня 2011, 07:28 |
|
|
Написав Середа Олег Володимирович
|
|
Неділя, 24 жовтня 2010, 22:40 |
|
Третій тур
Розв’язки задач відправляти з 25.10 по 07.11.2010р.
Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.
1. Задача TABLE (20 балів)
Ім’я вхідного файлу: TABLE.DAT
Ім’я вихідного файлу: TABLE.SOL
Максимальний час роботи на одному тесті: 2с
В прямокутній таблиці, що складається з M рядків та N стовпчиків, можна за один крок рухатись тільки:
- на одну клітинку вниз;
- через одну клітинку вниз;
- на одну клітинку вправо;
- через одну клітинку вправо.
Необхідно написати програму для знаходження кількості всіх можливих варіантів руху з лівого верхнього кутка таблиці в правий нижній куток.
Формат вхідних даних.
Єдиний рядок вхідного файлу TABLE.DAT містить два натуральні числа M та N (1<=M,N<=1000). Числа між собою розділені пробілами.
Формат вихідних даних.
Єдиний рядок вихідного файлу TABLE.SOL повинен містити одне натуральне число – кількість всіх можливих варіантів руху.
Приклад.
TABLE.DAT:
3 2
TABLE.SOL:
5
2. Задача ROUTES (100 балів)
Ім’я вхідного файлу: ROUTES.dat
Ім’я вихідного файлу: ROUTES.sol
Максимальний час роботи на одному тесті: 5 с.
Один палкий футбольний вболівальник хоче підтримати свою улюблену команду, яка має грати у виїзному матчі, в місті, що знаходиться досить далеко від дому. Щоб потрапити до місця призначення, йому, можливо, прийдеться прямувати через інші населенні пункти. Тому вболівальник заздалегідь дізнався розклад щоденного руху транспорту в кожному з населених пунктів, а також вартість кожного рейсу. Він пронумерував всі населенні пункти від 1 (рідне місто) до N (місто проведення матчу) та виписав розклад в вигляді таблиці, кожен рядок якої мав вигляд
Nвідпр. Nпризн. Tвідпр. Tприб. V,
де Nвідпр. – номер пункту відправлення, Nпризн. – номер пункту призначення, Tвідпр. – час відправлення, Tприб. – час прибуття, V – вартість проїзду.
Матч відбудеться в суботу о 19:00, але так як вболівальник у будні працює до 19:00, він може виїхати зі свого міста не раніше, ніж в п’ятницю, о 19:01.
Необхідно написати програму для знаходження найменшої вартості проїзду для вболівальника, за умови, що він вчасно потрапляє на матч. Якщо ж це неможливо то необхідно вивести повідомлення “impossible”.
Формат вхідних даних.
Перший рядок вхідного файлу ROUTES.dat містить одне натуральне число N (1<=N<=100). Решта рядків – розклад руху транспорту в описаному вище форматі, причому величини часу задаються у вигляді h:m, де h – приймає одне із значень від 0 до 23, а m – від 00 до 59; вартість проїзду задається дійсними числами з двома знаками після коми, такими, що будь-яка сумарна вартість проїзду не перевищує 1000,00. Кількість рейсів з кожного населеного пункту не перевищує 100.
Всі числа між собою розділені пробілами.
Формат вихідних даних.
Єдиний рядок вихідного файлу ROUTES.SOL має містити одне дійсне число з двома знаками після коми – найменшу вартість проїзду або рядок “impossible”.
Примітка.
1. Тривалість кожного рейсу із розкладу менше 24год.
2. Вважається що час на пересадку між рейсами та час, затрачений від місця прибуття до стадіону, рівні 0.
3. При написанні програми не дозволяється використовувати змінні спеціалізованих типів дати та часу.
Приклад.
ROUTES.DAT
4
1 4 16:30 18:59 15.20
1 2 20:00 1:58 3.40
1 3 19:01 10:30 1.50
2 4 2:20 16:50 5.20
2 4 2:50 19:01 4.40
3 4 11:20 17:20 8.20
ROUTES.SOL
8.60
ROUTES.DAT
2
1 2 12:15 2:20 11.60
1 2 6:00 19:01 10.48
ROUTES.SOL
impossible
Умови завдань в форматі МS Word скачати |
|
Останнє оновлення на Четвер, 08 вересня 2011, 07:29 |
|
Написав Друкачук Юрій Олексійович
|
|
Неділя, 10 жовтня 2010, 11:37 |
|
Другий тур
Розв’язки задач відправляти з 11.10 по 24.10.2010 р.
Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.
Задача 1. Замовлення комп’ютерів (20 балів)
Ім’я вхідного файлу: comp.dat
Ім’я вихідного файлу: comp.sol
Максимальний час роботи на одному тесті: 2с
В рамках національної програми «Комп’ютеризація шкіл» одна школа замовила декілька системних блоків і стільки ж моніторів. При складанні замовленні ніхто не врахував того, що існують два типи інтерфейсів для з’єднання системних блоків і моніторів: VGA і DVI. При цьому існують системні блоки і монітори, які підтримують як один із цих інтерфейсів, так і обидва.
Фірма, яка доставляла техніку, виявилась не дуже порядною – в доставці виявилось а1 системних блоків, які підтримують тільки VGA, а2 системних блоків, які підтримують тільки DVI, і а3 системних блоків, які підтримують обидва інтерфейси. З моніторами ситуація аналогічна: b1 моніторів підтримують тільки VGA, b2 –тільки DVI, b3 – підтримують обидва інтерфейси.
Необхідно вияснити, скільки комплектів із монітора і системного блока можна зібрати. При цьому з’єднувати монітор і системний блок можна тільки, якщо у них спільний інтерфейс.
Перший рядок вхідного файла містить три числа а1, а2 і а3 (0≤ а1,а2,а3 ≤100). Другий рядок вхідного файла містить три числа b1, b2 і b3 (0≤ b1,b2,b3≤100). При цьому виконується рівність а1+а2+а3=b1+b2+b3.
У вихідному файлі виведіть максимальну кількість комплектів із монітора і системного блока, які можна зібрати.
Приклад.
|
Comp.dat
|
Comp.sol
|
|
3 4 6
2 3 8
|
13
|
|
3 4 6
2 11 0
|
12
|
Задача 2. Привабливі номери (100 балів)
Ім’я вхідного файлу: phone.dat
Ім’я вихідного файлу: phone.sol
Максимальний час роботи на одному тесті: 2с
Багато компаній використовують для реклами «красиві» номери телефонів, які зручні для запам’ятовування потенційними клієнтами. Але що ж робити, якщо в номері вашої компанії нічого особливого? Можна придивись до нього, а можливо, якщо перегрупувати цифри номера певним чином, номер стане набагато красивішим? Наприклад, якщо у вашої компанії номер 972-74-44, то його можна зробити красивішим, якщо перегрупувати цифри так: 9727-444.
Введемо наступну оцінку краси розбиття номера. Будемо розбивати номер дефісами на групи розміром від 2 до 4 цифр. Тепер красою розбиття назвемо суму балів, які приносить кожна група. Ці бали будемо рахувати, використовуючи таблицю:
|
Шаблон групи
|
бали
|
|
аа
|
2
|
|
aba
|
2
|
|
aab, abb
|
2
|
|
aaa
|
3
|
|
abac, baca
|
2
|
|
abab
|
3
|
|
aabb
|
3
|
|
abba
|
4
|
|
baaa, abaa,aaba, aaab
|
3
|
|
aaaa
|
5
|
В цій таблиці символами a,b,c позначено різні цифри. Наприклад, під шаблон «aab» підходять групи 223, 667, але не підходять 123 і 888.
Вхідний файл містить один рядок із 7 цифр – заданий номер телефона.
Виведіть в першому рядку вихідного файлу найбільш красиве розбиття номера, а в другий – величину його краси.
Якщо розбиттів з максимальною величиною краси декілька, виведіть у вихідний файл будь-яке із цих розбиттів.
Приклад
|
phone.dat
|
phone.sol
|
|
8727333
|
8727-333
5
|
|
8827291
|
88-272-91
4
|
Умови завдань в форматі МS Word скачати
|
|
Останнє оновлення на Четвер, 08 вересня 2011, 07:29 |
|
Детальніше...
|
|
|
|
|
|
|
Сторінка 1 з 2 |
|
|
|
