Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Завдання XXVII всеукраїнської учнівської олімпіади з інформатики 2013/14 н р

Скачати 426.12 Kb.

Завдання XXVII всеукраїнської учнівської олімпіади з інформатики 2013/14 н р




Скачати 426.12 Kb.
Сторінка1/8
Дата конвертації02.05.2017
Розмір426.12 Kb.
  1   2   3   4   5   6   7   8

Завдання XXVII Всеукраїнської учнівської
олімпіади з інформатики

2013/14 н. р.


Віталій Бондаренко, Данило Мисак, Шаміль Ягіяєв

Зміст


Завдання першого туру 2

1.1. Шоколад (Данило Мисак) 2

Умова 2

Розв’язання 4



1.2. Відрізки (Роман Рубаненко, Роман Фурко) 5

Умова 5


Розв’язання 7

1.3. Торговельний центр (Роман Єдемський) 9

Умова 9

Розв’язання 11



1.4.

Торго́вий центр (ТЦ) інколи торгово-розважальний центр (ТРЦ), галерея, пасаж, торговельний комплекс, торговельно-розважальний комплекс (англ. shopping mall, mall, shopping center) - універсальний магазин або комплекс магазинів, що зазвичай включає підприємства побутового обслуговування, громадського харчування та розважальні заклади.

Граф зсередини (Данило Мисак) 14

Умова 14


Розв’язання 18

Завдання другого туру 21

2.1. Максимум (Данило Мисак) 21

Умова 21


Розв’язання 23

2.2. Числові операції (Данило Мисак) 25

Умова 25

Розв’язання 27

2.3. Декартівщина (Роман Єдемський) 32

Умова 32


Розв’язання 35

2.4. Археологи (Ярослав Твердохліб) 37

Умова 37

Розв’язання 40




Завдання першого туру

1.1. Шоколад (Данило Мисак)

Умова


Шоколад, який виробляє кондитерська компанія «Ням & Ням», має вигляд довгої плитки , що складається з квадратиків.

Археоло́гія (грец. αρχαιος - стародавній, λογος - слово) - наука, що висвітлює історію людського суспільства на основі вивчення пам'яток кам'яної, мідної (бронзової), залізної доби і пізніших часів. До цих пам'яток, що називаються археологічними, належать: стоянки, поселення, поховання, різні типи знарядь праці, зброї, посуду, прикрас, предмети побуту, мистецтво тощо.

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

Завдання. Напишіть програму chocolate, що для заданого порядку портретів на двох плитках шоколаду визначає, на яку найменшу кількість частин доведеться розламати першу плитку, щоб шляхом переставляння частин з неї можна було утворити другу. Ламати плитку можна тільки по межах квадратиків, а перегортати плитку чи її частини не можна.

Вхідні дані. Перший рядок вхідного файла chocolate.dat містить натуральне число (), що задає розмір плитки шоколаду, тобто кількість у ній квадратиків.

Портре́т або Портретний жанр (фр. portrait) - мальоване, скульптурне або фотографічне зображення людини або групи людей, а також відповідний жанр образотворчого мистецтва. Багато портретів створено і в гравюрі.

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

Натура́льні чи́сла - числа, що виникають природним чином при лічбі. Це числа: 1, 2, 3, 4, … Множину натуральних чисел прийнято позначати знаком N . .}

Усіх кондитерів занумеровано числами від до . Другий та третій рядки файла містять по різних натуральних чисел кожен (усі числа не перевищують ) — порядок портретів відповідно на першій і на другій плитках. Відомо, що ці порядки різні.

Вихідні дані. У вихідний файл chocolate.sol слід записати єдине число — найменшу кількість частин, на які доведеться розламати першу плитку так, щоб, якимось чином переставивши частини місцями, отримати порядок портретів на другій плитці.

Оцінювання. Набір тестів складається з блоків, для яких додатково виконуються такі умови:

  • балів: .

  • балів: .

  • балів: .

  • балів: .

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

chocolate.dat

chocolate.sol

5

4 3 2 5 1

1 2 5 3 4


4

Пояснення. Першу плитку можна розламати на такі чотири частини: квадратик , квадратик , два квадратики і , квадратик .

Квадра́т - чотирикутник, у якого всі сторони рівні і всі кути прямі. Для задання квадрата необхідно і достатньо задати дві точки на координатній площині, які відповідатимуть будь-яким двом кутам та врахувати їх суміжність.

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

Розв’язання


Розгляньмо довільні два сусідніх квадратики першої плитки. Якщо на другій плитці вони не стоять поряд, причому в такому ж порядку, то в місці з’єднання цих квадратиків першу плитку так чи інакше доведеться розламати. Разом із тим, розламавши плитку в усіх таких місцях і лише в них, одержимо частини, кожна з яких є фрагментом послідовних квадратиків другої плитки. Тому, склавши їх правильним чином, одержимо той самий порядок портретів, що й на другій плитці. Отже, нам залишилося для кожного числа з’ясувати, чи на першій і на другій плитці перед ним іде одне й те саме значення, чи ні. Щоб це зробити, можна для всіх чисел проводити окремий пошук по одній чи обох плитках (це дасть складність ). Або ж за один лінійний прохід створити для однієї з плиток індексний масив , де для кожного , , зберігати число, що на даній плитці йде перед (чи, скажімо, , якщо — перше число на плитці).

Маси́в - впорядкований набір фіксованої кількості однотипних елементів, що зберігаються в послідовно розташованих комірках оперативної пам'яті, мають порядковий номер і спільне ім'я, що надає користувач.

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

  1   2   3   4   5   6   7   8


Скачати 426.12 Kb.

  • Завдання першого туру
  • Розв’язання