Вівторок, 21.09.2021, 22:51
Головна Реєстрація RSS
Вітаю Вас, Гість
Наше опитування
Оцініть мій сайт
Всього відповідей: 62
Завдання ІІ етапу Всеукраїнської учнівської олімпіади з інформатики 2012-2013 н.р.

У М О В И    Т А    В К А З І В К И
до розв’язування завдань І-го етапу Всеукраїнської олімпіади з інформатики 2016-17 н.р.

Задача 1. POINTS
Ім’я вхідного файлу:
Ім’я вихідного файлу:
Вихідний текст програми:
Загальна кількість балів:




Points.inp
Points.out
Points.*
100 балів



На колі взято k точок (3 ≤ k ≤ 100), частина з яких (можливо всі) сполучені відрізками (хордами). Написати програму, що визначає min - мінімальну кількість хорд, які треба додатково провести, щоб утворився вписаний у коло опуклий многокутник, для якого дані хорди є сторонами або діагоналями, та n – число ще не проведених діагоналей утвореного многокутника.

Формат вхідних даних:
У єдиному рядку через пропуск записано числа x1 y1 x2 y2 … xi yi – номери кінців даних хорд.

Формат вихідних даних:
У єдиному рядку через пропуск записати числа min і n.

Приклад вхідних та вихідних даних:
Points.inp: 1 3 1 4 1 5 2 5 3 4 3 6        Points.out: 5 4

Вказівки до розв’язування.
Перш за все необхідно визначити і записати у порядку зростання вершини многокутника, їх кількість – k дорівнює числу точок, що є кінцями даних хорд (на мал. 1.1 k = 6). Зауважимо, що точки, не сполучені відрізками, до уваги брати зовсім не слід, адже вони не використовуються у задачі. Саме тому k, яке в умові означає загальну кількість точок, на першому ж етапі розв’язування становитиме кількість задіяних точок. У даному прикладі k дорівнює c – числу проведених хорд. Сторонами даного многокутника є хорди, які не мають внутрішніх перетинів, а його діагоналями (мал. 1.2) є хорди, що перетинаються. Дані задачі можна ізоморфно відобразити на відрізок з координатами 1 - 6 (мал. 1.3), поєднавши допоміжними відрізками координати, відповідні номерам кінців даних хорд. Кількість даних діагоналей многокутника d дорівнює кількості пар допоміжних відрізків, які мають не пусті і не рівні одному з відрізків перерізи. Проте, можна без цього обійтись, якщо помітити, що ті з хорд, що є сторонами многокутника, на кінцях мають точки, різниця номерів яких дорівнює 1. Якщо позначити p – число проведених сторін многокутника, то d = cp.
Число min – кількість не побудованих сторін многокутника (на мал. 1.2 зображені пунктиром) дорівнює k-(ld), тобто min = kp. Кількість не проведених діагоналей обчислюється за формулою n = k*(k - 3)/2 - d.
Основною робочою підпрограмою може бути логічна функція перевірки на перетин двох хорд. Кожну хорду зручно записати у записі
lin = record
            begln, endln: integer;
        end,
де begln та endln – координати початку та кінця хорд, а всі хорди – у масиві
lines: array[1..100] of lin.

Оцінка тестів до задачі Points:
12345678910
5 б.5 б.5 б.5 б.10 б.10 б.10 б.15 б.15 б.20 б.

Моє рішення на Free Pascal:


Задача 2. TRANSP
Ім’я вхідного файлу:
Ім’я вихідного файлу:
Вихідний текст програми:
Загальна кількість балів:





Transp.inp
Transp.out
Transp.*
100 балів




У місті працює мережа мікроавтобусів, що має кілька маршрутів, кожен із яких не замкнений і без самоперетинів. На кожному з маршрутів є по кілька зупинок, причому, деякі стоять на перетині маршрутів. Всі зупинки пронумеровані натураль-ными числами от 1 до n. Написати програму, яка за даним описом транспортної мережі визначить найменшу кількість пересадок, щоб дістатись від зупинки A до зупинки B.

Формат вхідних даних:
У першому рядку через пропуск записані числа: m (1 ≤ m ≤ 20) - кількість маршрутів, n (2 ≤ n ≤ 100) - кількість зупинок, A та B – номери зупинок, для яких потрібно підрахувати кількість пересадок. Кожен із наступних m рядків складається з pi чисел (2 ≤ pi ≤ 100) – номерів зупинок на i-му маршруті.

Формат вихідних даних:
У єдиний рядок записати число k - найменшу кількість потрібних пересадок або число -1, якщо це не можливо.

Приклад вхідних та вихідних даних:











Transp.int
2 5 3 1
1 2 3 4
5 3

2 10 3 8
1 3 5 7 4 9
2 4 6 8 10 7

2 4 1 3
1 2
3 4
Transp.out
0



1



-1



Вказівки до розв’язування.
Зобразимо транспортну мережу у вигляді графа, де зупинками будуть пронумеровані вершини. На малюнку 2.1, який відображає другий приклад, є два маршрути із зупинками 1 – 10. Для наочності зупинки першого маршруту з’єднаємо суцільними стрілками, а зупинки другого маршруту - пунктирними стрілками. Всі зупинки першого маршруту, що містить зупинку А, тобто №3, помітимо числом 0. Зупинки другого маршруту, який має спільні з першим маршрутом зупинки 4 та 7, помітимо числом 1 (малюнок 2.2). Очевидно, до будь-якої зупинки, поміченої числом 1, в тому числі і до зупинки В (№8) від зупинки А можна дістатись з однією пересадкою. Подібним чином, всі зупинки, суміжні з маршрутом, зупинки якого помічені числом 1, помітимо числом 2 і. т.д. Залишиться визначити число, яким помічені зупинки маршруту, що містить зупинку В. Воно і буде шуканим числом k. Використаємо структуру даних множина (set). Нехай L[i] - множина зупинок, розміщених на i-му маршруті (тобто L - масив множин), cur - множина зупинок, до яких можна дістатись, здійснивши не більшее step пересадок. Побудуємо множину next зупинок, до яких можна дістатись, зробивши не більше (step+1) пересадок. По-перше, всі зупинки з множини cur входять до множини next. По-друге, якщо на якусь зупинку можна потрапити не більше ніж за step пересадок, і ця зупинка належить в тому числі й маршруту i, то тоді на будь-яку зупинку маршруту i можна потрапити за не більше ніж (step+1) пересадок. Тобто, якщо переріз множин cur та L[i] не пустий, всі елементи множини L[i] потрібно включити в множину next: next := next + L[i] (об’єднання множин). Залишилось помітити, що коли транспортна мережа міста складається з m маршрутів, то або із зупинки A на зупинку B можна потрапити не більш ніж з (m-1)-ю пересадкою, або не можна потрапити взагалі (A і B лежать в різних компонентах зв’язності графа). Таким чином, для розв’язання задачі Transp необхідно вміти оперувати типом “множина“ (set), до речі, знати елементарні відомості з алгебри логіки та перевіряти граф на зв’язність немає, адже перевірка на зв’язність графа G, який має множини вершин зв’язних підграфів U та V (G=U∪V), здійснюється шляхом перевірки умови U∩V≠∅.

Оцінка тестів до задачі TRANSP:
12345678910
5 б.5 б.5 б.5 б.10 б.10 б.10 б.15 б.15 б.20 б.

Мої вказівки до розв’язування.
Збережемо інформацію про маршрути в масиві множин ss. Тобто для кожного маршруту, номери зупинок, які належать цьому маршруту будуть розміщені у відповідній множині. У множину s будемо поміщати маршрути, які досяжні з початкової зупинки не більше ніж за k пересадок. Якщо мережа маршрутів буде не зв’язною, і з початкової зупинки до кінцевої, не зходячи з маршруту, добратися неможливо, то дана програма також зуміє це визначити: якщо на якомусь кроці ні одного нового маршруту до досяжним не добавиться, то кінцева зупинка не досяжна.

Моє рішення на Free Pascal:


Задача 3. RELATIV
Ім’я вхідного файлу:
Ім’я вихідного файлу:
Вихідний текст програми:
Загальна кількість балів:






Relativ.inp
Relativ.out
Relativ.*
100 балів





Якщо погодитись, що люди походять від Адама та Єви, то всі вони – родичі, правда, серед них небагато прямих родичів (батьки та діти, рідні брати та сестри і т.д.), більшість людей пов’язані між собою лише через спільних родичів. Написати програму, яка для n людей (1 ≤ n ≤ 100), що мають родинні зв’язки, визначає, якщо це можливо, число min (0 ≤ minn/2) - мінімальну кількість тих, що між собою не мають родинних зв’язків, і без кого решта з n людей втратять будь-які родинні зв’язки.

Формат вхідних даних:
На перетині i-го рядка та j-го стопчика квадратної таблиці n x n записано число 1, якщо i-а і j-а людини є прямими родичами, і число 0, якщо для цих людей відсутній прямий родинний зв’язок.

Формат вихідних даних:
В єдиному рядку записати число min, або слово "not", якщо це число знайти не можливо.

Приклад вхідних та вихідних даних:









Relativ.int
0 0 0 0 1 1 0 1 0
0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0
1 1 0 0 0 0 0 0 0
1 1 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
Relativ.out
4









Вказівки до розв’язування.
Дані зручно проілюструвати на графі (див. мал. 3.1). У наведеному прикладі маємо справу іх зв’язним графом. Але, як видно з малюнка, відповідно умові, він двохдольний, тобто множина всіх вершин G=UV, де множини U=(1,2,3,4) та V=(5,6,7,8,9), причому UV=∅.
Отже, розв’язування задачі зводиться до:
1) перевірки, чи він двохдольний;
2) якщо так, то визначення серед множин U і V тієї, яка має меншу кількість елементів.
Найпростіше це можна зробити, здійснивши пошук в ширину, позначивши початкову вершину числом 0, безпосередньо пов’язані з нею вершини – числом 1, наступні вершини, безпосередньо пов’язані з вершинами, позначеними числом 1, позначити числом 2 і т.д. У наведеному графі одержимо (мал 3.2):
Всі вершини множини U будуть позначені парними числами, а вершини множини V – непарними.

Оцінка тестів до задачі Relativ:
12345678910
5 б.5 б.5 б.5 б.10 б.10 б.10 б.15 б.15 б.20 б.

Моє рішення на Free Pascal:


Задача 4. PARTS
Ім’я вхідного файлу:
Ім’я вихідного файлу:
Вихідний текст програми:
Загальна кількість балів:




Parts.inp
Parts.out
Parts.*
100 балів



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

Формат вхідних даних:
У першому рядку записано через пропуск числа m та n – довжина і ширина лісу (m, n ≤ 50), у наступних i (im*n) рядках по два числа xi та yi – координати обстежених квадратів.

Формат вихідних даних:
У єдиному рядку записати кількість необхідних бригад рятівників.

Приклад вхідних та вихідних даних:





Parts.int
3 3
1 3
2 2
3 1
3 3
Parts.out
3





Вказівки до розв’язування.
З малюнку 4, де зображено ліс із розмірами та розміщенням обстежених квадратів (заштриховані) відповідно наведеному прикладу, видно, що ізольованих не обстежених ділянок три (вони пронумеровані). Для розв’язування задачі зручно використати структуру “черга”. Спочатку в чергу слід занести будь-який ще не обстежений квадрат. Потім, доки черга не стане пустою, слід видаляти з неї перший квадрат і додавати в чергу всі суміжні з поточним необстежені квадрати. Черга обнулиться, коли закінчиться перша не обстежена ділянка. Далі, доки не закінчаться всі ще не обстежені квадрати, слід шукати новий не обстежений квадрат і повторювати вже щойно описане. Програма може вийти досить громіздкою, тому бажано виділити в окремі підпрограми ВВОД даних, ВИЗНАЧЕННЯ НАЯВНОСТІ НЕ ОБСТЕЖЕНИХ КВАДРАТІВ, ДОДАВАННЯ В ЧЕРГУ та ВИЛУЧЕННЯ З ЧЕРГИ.

Оцінка тестів до задачі PARTS:
12345678910
5 б.5 б.5 б.5 б.10 б.10 б.10 б.15 б.15 б.20 б.

Мої вказівки до розв’язування:
Це класична задача на пошук в глибину графа. Зрозуміло, що треба обходити матрицю і якимось чином обчислювати кількість ізольованих не обстежених ділянок. Варіант вирішення такий: після того, як ми потрапляємо на ділянку, треба це зафіксувати збільшивши змінну-результат на одиницю. Щоб вдруге не порахувати одну і туй ж ділянку, відразу після відвідин необхідно її знищити, тобто присвоїти всім клітинам ділянки значення нуль. Оскільки тест завдання не надто малий, варто написати процедуру знищення ділянок, назвемо її "count". Щоб під час виконання процедуру не «вискочити" за межі масиву, зробимо його не розміром m x n, а розмірів m+2 x n+2, це дасть нам можливість оточити шуканий масив розміром m x n нулями.

Моє рішення на Free Pascal:


Наверх