Бали за задачу: 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”, інакше.
Вхідні дані: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), таких що 0≤P, 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).
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] = 2A[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 (1≤N, M≤500), P (1≤P≤109). Далі послідовно задані N рядків матриці А, що описують годинники. Кожний рядок складається із унікальних M чисел, які описують стрілки годинника (відповідно, P>=M). Всі числа матриці знаходяться в інтервалі [1..P].
Вихідні дані: Виведіть одне число - максимальна кількість пар годинників, які виглядають ідентично після ротацій.
Приклад вхідних та вихідних даних.
| Приклад вхідних даних: | Приклад вихідних даних: |
| 5 2 4 1 2 2 4 4 3 2 3 1 3 | 4 |
ZTV
