Четвер, 23.11.2017, 01:04
Головна Реєстрація Вхід
Вітаю Вас, Гость · RSS
Меню сайту
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0
Форма входу
 Умови
Задача A. "Безкласова адресація"

Бали за задачу: 30
Обмеження часу:


   IPv4-адреса - це 32-бітне число. Будемо писати всі адреси у вигляді чотирьох десяткових чисел із значеннями від 0 до 255, розділених крапками, наприклад:
   ● 0xFFFFFFFF = 255.255.255.255
   ● 0xFF00FF01 = 255.0.255.1
   ● 0x10203040 = 16.32.48.64
   ● 0x00000000 = 0.0.0.0
   IPv4 CIDR (Classless Inter-Domain Routing) інтервал визначає IPv4-мережу (список IPv4 адрес). CIDR інтервал складається із IPv4 адреси та префікса, який вказує скільки бітів утворюють маску мережі. Префікс - це ціле число із інтервалу [0..32]. Шаблон CIDR інтервалу можна записати в такому вигляді: [IPv4-адреса]/[префікс].
   Конкретні приклади:
   ● 192.168.0.1/22
   ● 128.148.128.40/32
   ● 168.0.0.0/0
   ● 10.61.128.218/27
   Тобто, для заданого CIDR інтервалу 255.255.255.255/24 ми знаємо, що тільки 24 біти IPv4-адреси утворюють маску мережі. Біти, які не входять до маски, неважливі. Таким чином, ми можемо декількома способами задавати один і той же CIDR інтервал.
   Наприклад, всі наступні інтервали однакові:
   ● 255.255.255.255/24
   ● 255.255.255.0/24
   ● 255.255.255.100/24
   (тобто, перші 24 біти однакові, відрізняються тільки 8 останіх бітів).
   Вам задано два CIDR інтервала - A та B. LA та LB - довжини префіксів для A та B, відповідно. Нехай N = MIN(LA, LB).
   A - підмножина B, якщо:
   1. Префікс A більше префікса B (тобто LA>LB)
   2. Перші N бітів IPv4-адрес A та B однакові.
   Тепер ми можемо визначити також такі відношення як "рівність”, "супермножина”, "непересічність”.
   Ваше завдання - встановити відношення між двома заданими CIDR інтервалами A та B. Виведіть:
   ● "EQUAL”, якщо А дорівнює B (довжини префіксів однакові та відповідні перші N бітів в IPv4-адресах рівні).
   ● "SUBSET” , якщо А - підмножина В (довжина префікса А більша довжини префікса В та перші N бітів IPv4-адрес однакові).
   ● "SUPERSET”, якщо А - супермножина B (довжина префікса В більша довжини префікса А та перші N бітів IPv4-адрес однакові).
   ● "DISJOINT”, інакше.
Вхідні дані:
   В першому рядку заданий CIDR інтервал А, в другому - В. CIDR інтервали задачі у форматі: [IPv4-адреса]/[префікс].
Вихідні дані:
   Вихідні дані. Встановлене відношення між двома CIDR інтервалами: "EQUAL” або "SUBSET” або "SUPERSET” або "DISJOINT” (без лапок).

Приклад вхідних та вихідних даних.
Приклад вхідних даних: 
Приклад вихідних даних:
23.45.67.89/16
23.45.255.255/16

EQUAL

1.2.3.4/24
1.2.3.4/16
SUBSET

172.84.26.128/16
172.84.26.255/24
SUPERSET

197.54.16.128/25
197.54.16.127/25
DISJOINT


Задача B. "Префікс-суфікс пара"

Бали за задачу: 30
Обмеження часу:


   Вам заданий непустий масив А, який містить N цілих чисел. Префікс-суфікс пара - це пара індексів (P, S), таких що 0P, S<N, а також:
   1. значення всіх елементів підмасиву A[0], A[1], …, A[P] також присутні у підмасиві A[S], A[S+1], …, A[N-1]
   2. значення всіх елементів підмасиву A[S], A[S+1], …, A[N-1] також присутні у підмасиві A[0], A[1], …, A[P]
   Обчисліть кількість префікс-суфікс пар у заданому масиві А.
Вхідні дані:
   В першому рядку задано ціле число N (0<N<50000) - кількість елементів у масиві А. В другому - елементи масива А. Всі елементи масива - цілі числа із інтервалу [-109..109].

Вихідні дані:
   Виведіть одне число - кількість префікс-суфікс пар у заданому масиві А. Примітка. Для заданого масиву в прикладі є 14 префікс-суфікс пар: (1, 4), (1, 3), (2, 2), (2, 1), (2, 0), (3, 2), (3, 1), (3, 0), (4, 2), (4, 1), (4, 0), (5, 2), (5, 1), (5, 0).


Приклад вхідних та вихідних даних.
Приклад вхідних даних: 
Приклад вихідних даних:
6
3 5 7 3 3 5

14


Задача C. "Дивні годинники"

Бали за задачу: 30
Обмеження часу:

   Вам дано N годинників. У кожного із них є M стрілок, які вказують на одну із позицій 1, 2, ..., P. Годинники представлені у вигляді матриці А, яка складається із N рядків та M стовпців. Кожний рядок матриці описує один годинник (куди вказують його M стрілок). Розглянемо наступний приклад. Нехай матриця А складається із 5 рядків та 2 стовпців, а P=4:
   A[0][0] = 1 A[0][1] = 2
   A[1][0] = 2 A[1][1] = 4
   A[2][0] = 4 A[2][1] = 3
   A[3][0] = 2 A[3][1] = 3
   A[4][0] = 1 A[4][1] = 3

   Ви можете повертати годинники. Після чого, деякі годинники можуть виглядати ідентично(однаково). Повертаючись до попереднього прикладу, якщо ви повернете 3-ий, 4-ий та 5-ий годинники, то можете отримати наступну картину:

   Після такої ротації, ви отримали 4 різні пари годинників, які виглядають ідентично: (1, 3), (1, 4), (2, 5) та (3, 4).
   Напишіть програму, яка по заданій матриці А та числу Р повертатиме максимальне число пар годинників, які виглядають ідентично після ротацій.
Вхідні дані:
   В першому рядку задані числа N, M (1N, M500), P (1P109). Далі послідовно задані N рядків матриці А, що описують годинники. Кожний рядок складається із унікальних M чисел, які описують стрілки годинника (відповідно, P>=M). Всі числа матриці знаходяться в інтервалі [1..P].
Вихідні дані:
   Виведіть одне число - максимальна кількість пар годинників, які виглядають ідентично після ротацій.

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

4





ZTV
Copyright MyCorp © 2017
Пошук
Календар
«  Листопад 2017  »
ПнВтСрЧтПтСбНд
  12345
6789101112
13141516171819
20212223242526
27282930
Архів записів
Друзі сайту
Обдаровані діти

Хмельницькі олімпіади

НМЦ ІКТ і ДН

Портал ХОІППО

Створити безкоштовний сайт на uCoz