|
Завдання олімпіади 2011
|
Написав Administrator
|
|
Неділя, 04 листопада 2012, 19:36 |
|
Шостий тур
Розв’язки задач відправляти з 05.11 по 18.12.2011р.
Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.
1. Задача POINT (20 балів)
Ім’я вхідного файлу: POINT.DAT
Ім’я вихідного файлу: POINT.SOL
Максимальний час роботи на одному тесті: 1с
Багатокутник (не обов'язково опуклий) на площині заданий координатами своїх вершин. Потрібно підрахувати кількість точок з цілочисельними координатами, що лежать всередині нього (але не на його межі).
Формат вхідних даних
У першому рядку міститься N (3 <= N <= 1000) - число вершин багатокутника. У наступних N рядках йдуть координати (Xi, Yi) вершин багатокутника в порядку обходу за годинниковою стрілкою. Xi і Yi - цілі числа, по модулю не перевищують 1000000.
Формат вихідних даних
У вихідний файл вивести одне число - шукану кількість точок.
Приклади:
|
POINT.DAT
|
POINT.SOL
|
|
4
-1 -1
-1 1
1 1
1 -1
|
1
|
|
3
0 0
0 2
2 0
|
0
|
2. Задача POLYGON (100 балів)
Ім’я вхідного файлу: POLYGON.DAT
Ім’я вихідного файлу: POLYGON.SOL
Максимальний час роботи на одному тесті: 2 с
На площині задано дві фігури, що обмежені опуклими багатокутниками. Фігури розташовані таким чином, що їх вершини не співпадають, а контури мають рівно 2 точки перетину.
Довільним чином розділимо площину прямою. Будемо вважати, що півплощина з одного боку прямої відповідає першій фігурі, а з іншого боку – другій фігурі. Визначимо поняття дефекту розділення – сума площі першої фігури, що розташована на півплощині другої фігури, та площі другої фігури, що розташована на півплощині першої фігури. З двох можливих відповідностей півплощин до фігур оберемо таку відповідність, де значення дефекту менше.
Наприклад, на рисунку зображена пряма, що задає певне розділення багатокутників. Оцінка дефекту цього розділення (два випадки відповідності): (D)+(C+E) та (A+D)+(B+C). З рисунку, D+C+E менше, отже, загалом, оцінка розбиття дефекту розділення утвореного цією прямою є D+C+E.
Завдання
Напишіть програму polygon, що за заданими двома багатокутниками знаходить пряму, що утворює розділення з найменшим дефектом.
Вхідні дані
Перший рядок вхідного файлу polygon.DAT містить одне ціле число N (3<=N<=20) – кількість вершин першого багатокутника. Наступні N рядків містять пари цілих чисел – координати вершин першого багатокутника у порядку обходу. (N+2)-й рядок файлу містить число M (3<=M<=20) – кількість вершин другого багатокутника. Наступні M рядків містять його координати задані таким же чином, як і для першого багатокутника. Координати точок додатні та не перевищують 1000.
Вихідні дані
Єдиний рядок вихідного файлу polygon.SOL має містити дві пари чисел – координат двох точок, що однозначно задають розділення (пряму) з найменшим дефектом. Числа потрібно виводити у порядку: x1 y1 x2 y2. Координати потрібно виводити з точністю 10-3. Координати точок мають бути додатні та не більші за 1000.
Приклад вхідних та вихідних даних
|
polygon.DAT
|
polygon.SOL
|
|
3
2 1
3 3
4 1
3
5 2
3 2
4 3
|
2 5 4 1
|
|
|
|
Написав Administrator
|
|
Неділя, 04 листопада 2012, 19:33 |
|
П'ятий тур
Розв'язки задач відправляти з 21.11 по 04.12.2011р.
Розв'язок задачі розмістити як вкладений текстовий файл з іменем завдання.
1. Задача MATCHES (20 балів)
Ім'я вхідного файлу: MATCHES.DAT
Ім'я вихідного файлу: MATCHES.SOL
Максимальний час роботи на одному тесті: 2с
Відомо, що за перемогу у матчах чемпіонату з футболу команді нараховується три очки, за нічию - одне очко, за поразку очки не нараховуються.
Необхідно написати програму для знаходження числа всіх можливих варіантів здобуття за N матчів деякою футбольною командою M очок.
Формат вхідних даних.
Єдиний рядок вхідного файлу MATCHES.DAT містить два натуральні числа N та M (1<=N<=20,0<=M<=60). Числа між собою розділені пробілами.
Формат вихідних даних.
Єдиний рядок вихідного файлу MATCHES.SOL повинен містити одне натуральне число - кількість всіх можливих варіантів.
Приклад.
MATCHES.DAT:
3 3
MATCHES.SOL:
4
2. Задача MESSAGE (100 балів)
Ім'я вхідного файлу: MESSAGE.dat
Ім'я вихідного файлу: MESSAGE.sol
Максимальний час роботи на одному тесті: 5 с.
Зв'язок між країнами A, B, C та D настільки поганий, що при передачі по каналах зв'язку з однієї країни до іншої будь-якого текстового повідомлення може бути втрачено нуль або декілька символів з цього повідомлення.
Відомо, що з країн A, B та C до країни D, було одночасно надіслано по одному текстовому повідомленню що містило від 1 до 50 маленьких літер латинського алфавіту ('a' - 'z'). Повідомлення між собою не співпадали.
Необхідно написати програму для знаходження кількості різних можливих варіантів спотворень повідомлень в результаті яких країна D отримає з решти країн однаковий текст.
Наприклад, при передачі з країни A до країни D повідомлення "call", з країни B до країни D повідомлення "accelerate", а з країни C до країни D - "candle", можливо 6 різних варіантів спотворень в один і той самий текст: "c", "a", "l", "ca", "cl" та "al".
Формат вхідних даних.
Файл MESSAGE.dat містить три рядки, кожен з яких - початкове повідомлення, надіслане до країни D відповідно з країни A, B та C.
Формат вихідних даних.
Єдиний рядок вихідного файлу MESSAGE.SOL повинен містити одне натуральне число - кількість всіх можливих варіантів.
Приклад.
MESSAGE.DAT
call
accelerate
candle
MESSAGE.sol
6
MESSAGE.DAT
first
second
third
MESSAGE.SOL
0 |
|
Написав Administrator
|
|
Неділя, 04 листопада 2012, 19:30 |
|
Четвертий тур
Розв’язки задач відправляти з 7.11 по 20.11.2011 р.
Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.
1. Сума (20 балів)
Ім’я вхідного файлу: suma.in
Ім’я вихідного файлу: suma.out
Програма: suma.*
Обмеження часу: 1 с
Обмеження пам’яті: 16 мбайт
Знайти суму двох цілих чисел.
Формат вхідного файлу
У двох рядках записані цілі числа, модуль кожного з яких не більше за 10^1000 . Перед від'ємними числами стоїть знак "мінус", пред додатними - нічого не стоїть.
Формат вихідного файлу
Вихідний файл повинен містити одне ціле число – відповідь до задачі.
Приклад
|
suma.in
|
suma.out
|
|
1
2
|
3
|
|
-5
3
|
-2
|
|
-4
-3
|
-7
|
2. Квадратний корінь (100 балів)
Ім’я вхідного файлу: korin.in
Ім’я вихідного файлу: korin.out
Програма: korin.*
Обмеження часу: 2 с
Обмеження пам’яті: 64 мбайт
Для заданого натурального числа А потрібно знайти найбільше число В таке, що B^2 ≤ A.
Технічні умови
Вхідні дані
У вхідному файлі записано натуральне число A (A ≤ 10^3000).
Вихідні дані
У вихідний файл виведіть максимальне натуральне число B, квадрат якого не перевищує A. Число B слід виводити без лідируючих нулів.
Приклад
|
Приклад вхідних даних
27
|
Приклад вихідних даних
5
|
|
|
|
Написав Друкачук Юрій Олексійович
|
|
Неділя, 23 жовтня 2011, 10:24 |
|
Третій тур
Розв’язки задач відправляти з 24.10 по 6.11.2011 р.
Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.
скачати файл
1. Паліндроми (20 балів)
Ім’я вхідного файлу: palind.in
Ім’я вихідного файлу: palind.out
Програма: palindr.*
Обмеження часу: 5с
Обмеження пам’яті: 64 мбайт
Паліндром – слово, яке однаково читається в обох напрямках. Підрахуйте, скільки різних паліндромів можна отримати, переставляючи букви в заданому слові. Так як відповідь може бути дуже великим числом – виведіть остачу від його ділення на 1000000000.
Формат вхідного файлу
Один рядок містить слово із рядкових букв латинського алфавіту довжиною від 1 до 100 символів.
Формат вихідного файлу
Вихідний файл повинен містити одне ціле число від 0 до 1000000000-1 – відповідь до задачі.
Приклад
|
palind.in
|
palind.out
|
|
ababc
|
2
|
|
aaa
|
1
|
|
abc
|
0
|
В першому прикладі можна зробити два паліндроми: abcba, bacab
2. Рядки (100 балів)
Ім’я вхідного файлу: string.in
Ім’я вихідного файлу: string.out
Програма: strings.*
Обмеження часу: 4с
Обмеження пам’яті: 64 мбайт
Маємо два рядка. Із кожного рядка дозволяється видаляти символи, але кількість видалених символів, які йдуть підряд, не повинна перевищувати W. Ваше завдання – видаливши мінімально можливу кількість символів, зробити рядки однаковими (символи різного регістру вважати однаковими).
Формат вхідного файлу
Вхідний файл містить в першому рядку число W (1≤W≤1500), в другому і третьому – два заданих рядка, які складаються із цифр і символів англійського алфавіту від 1 до 1500 символів.
Формат вихідного файлу
Вихідний файл повинен містити один рядок, який можна отримати із обох рядків за правилами задачі. Якщо існує декілька варіантів відповіді, виведіть будь-який. Якщо відповіді не існує виведіть No solution
Приклад
|
String.in
|
String.out
|
|
1
xabcd
aefdz
|
No solution
|
|
2
xabcd
aefdz
|
ad
|
|
|
Останнє оновлення на Неділя, 23 жовтня 2011, 21:36 |
|
Написав Gis
|
|
Неділя, 09 жовтня 2011, 23:04 |
|
Другий тур
Розв’язки задач відправляти з 10.10 по 23.10.2011 р.
Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.
скачати файл
1. Порядок
Максимальна оцінка: 20 балів
Обмеження на час: 5 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: order.dat
Вихідний файл: order.sol
Програма: order.*
Нехай n - довільне натуральне число, а послідовність i1, i2, ... , in містить усі натуральні числа від 1 до n включно. Порушенням порядку у такій послідовності називають систему таких двох нерівностей, що справджуються: j < k та ij > ik. Якщо послідовність зростає, то кількість порушень порядку дорівнює 0. Якщо послідовність спадає, то така кількість дорівнює n(n - 1)/2. В усіх інших випадках ця кількість розташована між вказаними величинами.
Завдання
Встановіть парність кількості порушень порядку послідовності.
Вхідні дані
У першому рядку вхідного файлу вказано кількість послідовностей m. Кожний з наступних m рядків містить натуральне число n і послідовність різних натуральних чисел від 1 до n включно: i1, i2, ... , in при 2 ≤ т ≤ 100, 2 ≤ n ≤ 1 048 576. У 50 % тестів n ≤ 4096.
Вихідні дані
Єдиний рядок вихідного файлу має містити число в шістнадцятковій системі числення, яке відповідає двійковому числу яке утворене з m символів - нулів або одиниць - без пропусків: k-й символ рядка - це залишок від ділення на 2 кількості порушень порядку k-ї послідовності, заданої (k + 1)-м рядком вхідного файлу.
Приклад
|
order.dat
|
orderd.sol
|
|
5
3 1 2 3
3 2 3 1
3 1 3 2
4 2 3 4 1
4 3 4 1 2
|
6
|
Пояснення (00110 )2=(6)16
2. Код Грея
Максимальна оцінка: 100 балів
Обмеження на час: 1 сек.
Обмеження на пам'ять: 32 MБ
Вхідний файл: grey.dat
Вихідний файл: grey.sol
Програма: grey.*
Кодом Грея називають непозиційну систему запису цілих натуральних чисел за допомогою двох символів 0 та 1 таким чином. Нуль кодують послідовністю нулів. При зростанні цілого числа:
- наймолодший 1-й розряд у послідовності символів змінюють у такій послідовності: 0, 1, після чого у наступний 2-й розряд записують 1, а наймолодший розряд змінюють уже у протилежному порядку;
- два наймолодші розряди змінюють у такому порядку: 00, 01, 11, 10, після чого у 3-й розряд записують 1, а два наймолодші розряди змінюють уже у протилежному порядку: 10, 11, 01, 00 ... ;
- k наймолодших розрядів змінюють у порядку, визначеному попередніми кроками, після чого у наступний (k + 1)-й розряд записують 1, а молодші розряди змінюють уже у протилежному порядку.
Коди Грея довжини 4 чисел від 0 до 15 включно такі (записано у порядку зростання числа): 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.
Коди Грея двох послідовних натуральних чисел відрізняються лише в одному розряді. Це використовують для збільшення надійності роботи системи оптичних фотодіодів при встановленні кута повороту дисків - носіїв інформації.
Завдання
Визначте код Грея натурального числа.
Вхідні дані
Вхідний файл містить лише десятковий запис натурального числа n при n < 1018.
Вихідні дані
Вихідний файл має містити код Грея числа n мінімальної довжини. Інакше кажучи, цей код має починатися з одиниці й містити j символів,
де 2j - 1 ≤ n < 2j.
Приклади
|
grey.dat
|
grey.sol
|
|
2
|
11
|
|
7
|
100
|
|
13
|
1011
|
|
|
Останнє оновлення на Понеділок, 10 жовтня 2011, 07:56 |
|
|
|
|
|
|
Сторінка 1 з 2 |
|
|
|
