Задача A. Бiнарна матриця

Дано матрицю a розмiром n × n, що складається з нулiв i одиниць.

Будемо вважати, що рядки матрицi пронумерованi зверху вниз вiд 1 до n, а стовпцi злiва направо вiд 1 до n. Нехай ai,j — число на перетинi i-го рядка та j-го стовпчика. Вам потрiбно знайти кiлькiсть гарних пiдматриць цiєї матрицi.

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

В данiй задачi пiдматрицею i1,j1,i2,j2 (1 ⩽ i1 < i2 n,1 ⩽ j1 < j2 n) будемо називати такi елементи ai,j заданої матрицi, для яких виконуються умови i1 i i2 та j1 j j2. Звернiть увагу, що довжина кожної сторони пiдматрицi має бути принаймнi 2. Формат вхiдних даних

Перший рядок мiстить одне цiле число n (1 ⩽ n ⩽ 1200) — розмiр матрицi. Кожний з наступних n рядкiв мiстить по n символiв «0» та «1».

Формат вихiдних даних

Виведiть одне цiле число — кiлькiсть гарних пiдматриць матрицi a.

Приклади

standard input

standard output

3

101

101

010

5

1

1

0

5

11001

10101

10111

00000

00010

22

Примiтка

Координати протилежних кутiв п’яти гарних пiдматриць у першому прикладi:

  1. (1,1), (2,3).
  2. (1,1), (3,2).
  3. (1,2), (3,3).
  4. (2,1), (3,2).
  5. (2,2), (3,3).

 

Задача B. Граф

Дано граф з n вершинами та m ребрами. У i-й вершинi графу записано число ai. У кожнiй компонентi зв’язностi вибирається одна головна вершина, пiсля чого виконується операцiя побiтового OR з усiма числами, записаними у вiдповiдних обраних головних вершинах.

Необхiдно мiнiмiзувати результат побiтового OR.

Формат вхiдних даних

Перший рядок мiстить два цiлих числа — n та m (1 ⩽ n,m ⩽ 2 · 105) — кiлькiсть вершин та ребер.

Другий рядок мiстить n цiлих чисел a1,a2,...,an (0 ⩽ ai < 230) — числа, записанi у вершинах.

Кожний з наступних m рядкiв мiстить по два цiлих числа vi та ui (1 ⩽ vi,ui n) — вершини, мiж якими є ребро.

Не гарантується, що у графi немає кратних ребер та петель.

Формат вихiдних даних

Потрiбно вивести єдине число — мiнiмально можливе значення побiтового OR.

Приклади

 

standard input

standard output

5 2

9 133

1 2

5 3

1 2 3

11

8 7

22 20

1 3

4 1

3 4

3 4

2 2

2 7

6 5

17 8 1 18 33 6

22

Примiтка

 

У другому прикладi вигiдно вибрати вершини з номерами 1, 2, 6 та 8.

 

Задача C. Два масиви

Дано двi послiдовностi цiлих чисел a та b однакової довжини n. Вартiстю послiдовностей a та b назвемо:

 

Iншими словами, aibi — числа ai та bi записанi поспiль без пробiлу. Наприклад, якщо ai = 562, а bi = 12, то aibi = 56212.

Знайдiть мiнiмальну можливу вартiсть послiдовностей a i b, якщо ви можете переставляти елементи послiдовностi a як вам заманеться.

Формат вхiдних даних

Перший рядок мiстить одне цiле число n (1 ⩽ n ⩽ 105) — довжину послiдовностей a i b.

Другий рядок мiстить n цiлих чисел a1,a2,...,an (1 ⩽ ai ⩽ 106) — числа послiдовностi a. Третiй рядок мiстить n цiлих чисел b1,b2,...,bn (1 ⩽ bi ⩽ 106) — числа послiдовностi b.

Формат вихiдних даних

Виведiть одне цiле число — мiнiмальну можливу вартiсть двох послiдовностей a та b, якщо можна переставляти елементи послiдовностi a.

Приклади

 

standard input

standard output

4

10 1 5

2 90 3

2

100

1545

8

123 51 5 5 91

245 50 2 59 2000 33

25 1 871 303 80

76061

Примiтка

У першому прикладi однiєю з оптимальних перестановок послiдовностi a буде [10,2,5,1], тодi вартiстю послiдовностей буде 102 + 290 + 53 + 1001 = 1545.

 

Задача D. Два числа

Вам дано два числа a та b.

Також у вас є масив простих чисел p розмiром n.

За одну операцiю ви можете взяти будь-яке число з масиву, помножити a або b на нього, та видалити це просте число з масиву. Вам треба вiдповiсти, чи можна зробити так, щоб a дорiвнювало b? А якщо можна, то потрiбно знайти ще й мiнiмальну кiлькiсть операцiй.

Зауважте, що необов’язково використовувати усi числа.

Формат вхiдних даних

Перший рядок мiстить два цiлих числа a та b (2 ⩽ a,b ⩽ 108).

Другий рядок мiстить одне цiле число n (1 ⩽ n ⩽ 103) — кiлькiсть елементiв масиву.

Третiй рядок мiстить n простих чисел p1,p2,...,pn (2 ⩽ pi ⩽ 108). Гарантується, що для кожного цiлого i (1 ⩽ i < n) виконується pi pi+1.

Формат вихiдних даних

В першому рядку вам потрiбно вивести «YES», якщо можна зробити a та b однаковими, iнакше виведiть «NO». Якщо вiдповiдь iснує, в другому рядку потрiбно вивести мiнiмальну кiлькiсть операцiй.

Приклади

standard input

standard output

6 3

3

2 3 5

YES

1

6 3

2

3 5

NO

Примiтка

У першому прикладi можна помножити друге число на 2, тодi 3 · 2 = 6. У другому прикладi неможливо зробити числа рiвними.

 

Задача E. Дерево i вiрус

Вам дано дерево з n вершин. Кожна вершина має ci тварин у нiй. Коренем дерева є 1. Якщо заразити вiрусом одну вершину у деревi, всi тварини, якi живуть в нiй стануть зараженi. Також всiм її синам передасться вiрус. Зауважте, що предку вiрус не передається. Якщо вершина заблокована, то вона не може бути зараженою та вона не може передавати вiрус своїм синам. Вам дано q запитiв (1 ⩽ q ⩽ 105). Запити бувають двох типiв:

  1. Якщо дана вершина незаблокована — заблокувати її. Iнакше розблокувати.
  2. Заразити дану вершину та сказати, скiльки тварин буде заражено. Кожен запит такого типу виконується незалежно один вiд одного, тобто на момент виконання цього запиту, нiяка вершина не є зараженою.

Формат вхiдних даних

Перший рядок мiстить одне цiле число n (1 ⩽ n ⩽ 105) — кiлькiсть вершин у деревi.

Другий рядок мiстить n цiлих чисел 1,2,..., n (1 ⩽ ci ⩽ 109) — кiлькiсть тварин у вершинах.

Кожний з наступних n − 1 рядкiв мiстить по два цiлих числа u i v (1 ⩽ u,v ⩽ 105,u ̸= v) — вершини, мiж якими є ребро.

Наступний рядок мiстить одне цiле число q (1 ⩽ q ⩽ 105) — кiлькiсть запитiв.

Кожний з наступних q рядкiв мiстить два цiлих числа t та u (1 ⩽ t ⩽ 2,1 ⩽ u n) — тип запита та вершина запита.

Формат вихiдних даних

Для кожного запиту другого типу ви маєте вивести кiлькiсть заражених тварин.

Приклад

 

standard input

standard output

7

1 2

1 2

1    3

2    4

2    5

3    6

3 7

7

1    3

2    1

1    5

2    2

1    3

2    1

2 3

3 4 5 6 7

12

6

23

16

Примiтка

Вершини, якi будуть зараженi вiрусом пiсля другого дня [1,2,4,5], якi мiстять 12 тварин. Пiсля четвертого дня зараженими будуть вершини [2,4], якi мiстять 6 тварин. Пiсля шостого дня зараженими верщинами будуть [1,2,3,4,6,7], якi мiстять 23 тварини. Пiсля сьомого дня зараженими будуть [3,6,7] вершини, якi мiстять 16 тварин.

 

Задача F. K нульових бiтiв

Знайдiть будь-яке число, яке не менше за 10n i у бiнарному записi якого є вiдрiзок довжиною рiвно з k нулiв, що з обох сторiн оточений одиницями.

Наприклад, число 16310 = 101000112 мiстить у собi вiдрiзок iз трьох нулiв, оточений одиницями. Також це число мiстить у собi вiдрiзок з одного нуля, але не мiстить з двох чи чотирьох нулiв.

Формат вхiдних даних

У першому рядку задано два цiлих числа n та k (1 ⩽ n ⩽ 1000, 1 ⩽ k ⩽ 50).

Формат вихiдних даних

Виведiть будь-яке таке число у десятковому записi. Довжина вiдповiдi не має перевищувати 2000 символiв. Можна довести, що вiдповiдь завжди iснує.

Приклади

standard input

 

standard output

2 3

163

 

3 5

2755593

 

Примiтка

У другому прикладi: 275559310 = 10101000001100000010012. Це число бiльше за 103 та двiйковому записi мiстить вiдрiзки з нулiв довжиною 1, 1, 5, 6, 2 символи. Через те, що серед них є i вiдрiзок довжиною 5, то ця вiдповiдь задовольняє умовi.

 

G. Кiлькiсть бiтiв

Дано число n. Знайдiть кiлькiсть одиниць у бiнарному записi числа 2n + n.

Формат вхiдних даних

Перший рядок мiстить одне цiле число t (1 ⩽ t ⩽ 100) — кiлькiсть тестiв. Кожний з наступних t рядкiв мiстить одне цiле число n (0 ⩽ n ⩽ 1018).

Формат вихiдних даних

Для кожного тесту вам потрiбно вивести одне число в окремому рядку — кiлькiсть одиничних бiтiв числа 2n + n.

Приклад

standard input

standard output

3

3

1

2

3

2

2

Примiтка

23 + 3 = 1110 = 10112 — три одиничних бiта.

21 + 1 = 310 = 112 — два одиничних бiта.

22 + 2 = 610 = 1102 — два одиничних бiта.

 

Задача H. Клас

Клас являє собою матрицю n×m. Тобто всього n·m парт, за кожною з яких сидить рiвно один студент.

Час змiн! Усi вони хочуть змiнити свої мiсця. Якщо студент сидить за партою (x,y), то вiн хоче пересiсти на одну з парт: (x+1,y), (x,y +1), (x−1,y), (x,y −1). Якщо певної парти немає, то туди пересiсти неможливо.

Вам потрiбно визначити чи можуть усi студенти пересiсти так, як вони хочуть.

Формат вхiдних даних

Перший рядок мiстить одне цiле число t (1 ⩽ t ⩽ 1000) — кiлькiсть тестiв.

Кожний з наступних t рядкiв мiстить два цiлих числа n та m (1 ⩽ n,m ⩽ 105) — розмiри класу.

Формат вихiдних даних

Для кожного тесту вам потрiбно вивести «TAK», якщо студенти можуть пересiсти так, як вони хочуть, iнакше виведiть «HI».

Звернiть увагу, що вам потрiбно виводити букви латинського алфавiту, а не кирилицького.

Приклад

standard input

standard output

3

2 2

1 1

1 2

TAK

HI

TAK

Примiтка

У першому прикладi студенти, якi сидять в одному ряду, можуть помiнятись мiсцями.

У другому прикладi всього один студент, який не можу нiкуди пересiсти. У третьому прикладi два студенти можуть помiнятись мiсцями.

 

Задача I. Крутi пiдрядки

У вас є рядок s довжини n. Вам потрiбно порахувати кiлькiсть пар (l,r) (1 ⩽ l r n) таких, що пiдрядок s[l...r] є крутим.

Пiдрядок називається крутим, якщо не iснує такого символу, який зустрiчається бiльше   раз, де l — довжина пiдрядка. Формат вхiдних даних

У першому рядку задано одне цiле число n (1 ⩽ n ⩽ 105) — кiлькiсть символiв.

У другому рядку задано рядок з n лiтер латинського алфавiту в нижньому реєстрi вiд «a» до «z».

Формат вихiдних даних

Виведiть кiлькiсть крутих пiдрядкiв.

Приклади

standard input

standard output

5 gccgc

4

6 abbcaa

10

Примiтка

У першому прикладi крутими пiдрядками є [1...2], [1...4], [3...4] та [4...5].

У другому прикладi крутими пiдрядками є [1...2], [1...4], [1...5], [1...6], [2...5], [2...6], [3...4], [3...5], [3...6] та [4...5].

 

Задача J. Покриття

Дано масив a довжини n. Треба виконати m запитiв: додати число x у мультимножину. Пiсля кожного запиту потрiбно сказати, скiльки максимум елементiв масиву a можна покрити елементами мультимножини. Кожен елемент мультимножини не можна використовувати бiльше одного разу. Елемент покриває iнший елемент, якщо вiн бiльший або рiвний за нього. Спочатку мультимножина порожня.

Формат вхiдних даних

Перший рядок мiстить одне цiле число n (1 ⩽ n ⩽ 200000) — довжину масиву a.

Другий рядок мiстить n цiлих чисел a1,a2,...,an (1 ⩽ ai ⩽ 109) — числа масиву a.

Третiй рядок мiстить одне цiле число m (1 ⩽ m ⩽ 200000) — кiлькiсть запитiв.

Кожний з наступних m рядкiв мiстить по одному цiлому числу x (1 ⩽ x ⩽ 109) — запити.

Формат вихiдних даних

На кожен запит виведiть в окремому рядку вiдповiдь на цей запит.

Приклад

standard input

standard output

5

4 5 4 3 1

5

1

1

5

3

3

1

1

2

3

3

Примiтка

Пiсля першого та другого запиту можна покрити лише п’ятий елемент масиву a. Пiсля третього запиту можна покрити третiй та п’ятий елементи (а можна перший або другий замiсть третього). Пiсля четвертого та п’ятого запиту можна покрити третiй, четвертий та п’ятий елементи масиву a (можливi й iншi покриття).


Задача K. Пончик

У Вас є масив iз n чисел. Вам потрiбно знайти кiлькiсть пiдмасивiв цього масиву, для яких виконується правило: кожне число, що зустрiчається хоча б раз на цьому пiдмасивi, має зустрiчатись на ньому не менше нiж m разiв. Пiдмасив — послiдовнiсть сусiднiх позицiй у масивi.

Формат вхiдних даних

Перший рядок мiстить два цiлих числа n та m (1 ⩽ m n ⩽ 5 · 105) — кiлькiсть чисел та мiнiмальна кiлькiсть разiв, скiльки мають зустрiчатись числа.

Другий рядок мiстить n цiлих чисел a1,a2,...,an (1 ⩽ ai ⩽ 5 · 105) — числа масиву.

Формат вихiдних даних

Виведiть одне число — вiдповiдь на задачу.

Приклади

 

 

 

 

standard input

standard output

6 2

1 2

2

1

3

3

4

8 3

1 2

1

1

2

2 1 1

5

5 2

2 1

3

1

2

 

0

Примiтка

У першому прикладi нам пiдiйдуть такi пiдмасиви: [2,2], [3,3], [1,2,2,1], [1,2,2,1,3,3].

У         другому          прикладi         нам      пiдiйдуть        такi      пiдмасиви:      [1,2,1,1,2,2],    [1,2,1,1,2,2,1],

[1,2,1,1,2,2,1,1], [2,1,1,2,2,1], [2,1,1,2,2,1,1].


Задача L. Четвiрки на вiдрiзку

Дано послiдовнiсть цiлих чисел a довжини n i m запитiв двох типiв:

  1. «! l r x» — змiнити ai на x для кожного i на вiдрiзку з l по r.
  2. «? l r» — порахувати по модулю 109 + 7

ai aj ak aw

li<j<k<wr

Вираз xy означає застосування побiтової операцiї XOR до чисел x i y. Дана операцiя iснує у всiх сучасних мовах програмування, наприклад, в мовах С++ i Java вона позначена як «ˆ», а в Pascal як «xor».

Формат вхiдних даних

Перший рядок мiстить цiле число n (1 ⩽ n ⩽ 105) — довжину послiдовностi.

Другий рядок мiстить n цiлих чисел a1,a2,...,an (0 ⩽ ai ⩽ 109) — числа послiдовностi.

Третiй рядок мiстить одне цiле число m (1 ⩽ m ⩽ 105) — кiлькiсть запитiв. Кожний з наступних m рядкiв описує один з двох запитiв:

  1. «! l r x» (1 ⩽ l r n,0 ⩽ x ⩽ 109).
  2. «? l r» (1 ⩽ l r n).

Гарантується, що буде принаймнi один запит другого типу.

Формат вихiдних даних

На кожен запит другого типу виведiть в окремому рядку вiдповiдь на цей запит.

Приклади

 

 

standard input

standard output

4

1 9

6

? 1

? 1

! 1

? 1

! 2

? 1

4

3

4

1

4

4

4

5

9

5

0

9

1

12

10

335

446

181

625

10

! 5

? 4

! 2

? 2

! 7

? 5

! 6

? 1

! 3

? 2

27

75

42

71

5

7

6

8

9

10

10

8

10

7

9264   849598327   822889311

5913   526239859   548830120

4399   715477619   342858071

1486

647639160

545923679

389312924

561330066

786119025

375189142

259914062

838908849

461610148

401963966

Примiтка

Пояснення до першого прикладу:

Вiдповiдь на перший запит 0, бо взагалi немає вiдповiдних четвiрок.

Вiдповiдь на другий запит: 1 ⊕ 9 ⊕ 4 ⊕ 5 дорiвнює 9.

Пiсля третього запиту послiдовнiсть буде виглядати як [9,9,4,5].

Вiдповiдь на четвертий запит: 9 ⊕ 9 ⊕ 4 ⊕ 5 дорiвнює 1.

Пiсля п’ятого запиту послiдовнiсть буде виглядати як [9,5,5,5]. Вiдповiдь на шостий запит: 9 ⊕ 5 ⊕ 5 ⊕ 5 дорiвнює 12.

 

Задача M. Роздiлiть послiдовнiсть

Вам дана послiдовнiсть з n невiд’ємних цiлих чисел. Вам треба роздiлити цю послiдовнiсть на k + 1 непустих частин.

Спочатку, ви маєте одну частину. Щоб отримати k + 1 частин, ви маєте повторити наступний алгоритм k разiв:

  1. Виберiть будь-яку частину, у якої бiльше одного елемента, та роздiлiть її на двi непустi частини довiльного розмiру.
  2. До вiдповiдi додайте добуток сум елементiв двох нових частин.

Вам потрiбно максимiзувати фiнальну вiдповiдь.

Формат вхiдних даних

Перший рядок мiстить два цiлих числа n та k (1 ⩽ n ⩽ 105,1 ⩽ k ⩽ 200) — довжину послiдовностi та кiлькiсть операцiй розбиття.

Другий рядок мiстить n цiлих чисел a1,a2,...,an (0 ⩽ ai ⩽ 104) — елементи послiдовностi.

Формат вихiдних даних

У першому рядку виведiть максимально можливий результат.

У другому рядку виведiть k чисел pi (1 ⩽ pi n − 1) — позицiї, пiсля яких треба розрiзати послiдовнiсть. Тобто розрiз проводився мiж pi та pi+1.

Приклади

 

 

 

 

standard input

standard output

7 3

4 1 3

4

0

2

3

108

1 3 4

10 2 1 2 3

4

5

6

7 8 9 10

999

6 8

Примiтка

Пояснення до першого прикладу:

У нас є початкова послiдовнiсть [4,3,3,6,0,4,1].

Розрiзаємо послiдовнiсть пiсля першої позицiї. Виходить двi новi послiдовностi [4] та [3,3,6,0,4,1]. Вiдповiдь стає 4 · 17 = 68.

Далi розрiзаємо послiдовнiсть пiсля третьої позицiї. Виходить [4], [3,3], [6,0,4,1]. Вiдповiдь стає 68 + 6 · 11 = 134.

Розрiзаємо пiсля четвертої позицiї. Виходить [4], [3,3], [6], [0,4,1]. Вiдповiдь стає 134+6·5 = 164

 

Задача N. У пошуках медiани

Ван дано масив a довжиною n (n — непарне число) i q запитiв до нього. Кожен запит задається двома числами: l та r. Ви маєте додати 1 до всiх елементiв масиву на позицiях вiд l до r включно i пiсля цього знайти медiану масиву та вивести її.

Медiана масиву з непарною довжиною — число, яке стояло б на  позицiї, якщо цей масив вiдсортувати.

Формат вхiдних даних

Перший рядок мiстить два цiлих числа n та q (1 ⩽ n,q ⩽ 105) — кiлькiсть чисел та запитiв вiдповiдно. Число n — непарне.

Другий рядок мiстить n цiлих чисел a1,a2,...,an (0 ⩽ ai ⩽ 109) — елементи масиву. Кожний з наступних m рядкiв мiстить по два цiлих числа li та ri (1 ⩽ li ri n).

Формат вихiдних даних

Виведiть q рядкiв, де в i-му рядку має бути медiана масиву пiсля i-того запиту.

Приклади

 

 

standard input

standard output

5 3

0 0

3 3

1 3

1 2

1

2 0

0

1

2

3 2

1 1

1    2

2    3

1

 

2

2

Примiтка

Пояснення першого прикладу:

Позицiя m, на якiй знаходиться медiана у вiдсортованому масивi, рiвна  = 3

Пiсля першого запиту наш масив виглядає так [0,0,2,2,0]. Якщо його вiдсортувати, то вiн виглядає так [0,0,0,2,2]. На третiй позицiї у нас число 0, то й вiдповiдь 0.

Пiсля другого запиту масив виглядає наступним чином [1,1,3,2,0]. Якщо вiдсортувати, то це буде [0,1,1,2,3]. На третiй позицiї у нас 1.

Пiсля третього запиту масив виглядає наступним чином [2,2,3,2,0]. Якщо вiдсортувати, то це буде [0,2,2,2,3]. На третiй позицiї у нас 2.

 

Задача O. Футбол

Микола Вiкторович прийшов на футбольний матч. Як справжнiй футбольний фанат, вiн записував рахунок гри на листочку пiсля кожного забитого голу. Наприклад, на листочку могли бути записанi в такому порядку рахунки 0:1, 1:1, 2:1, 3:1, 3:2.

Матч був досить цiкавим, а голiв було дуже багато, тому Миколi Вiкторовичу набридло записувати всi рахунки гри. Але вiн ще є хорошим математиком, тому вiн запам’ятав суму всiх чисел в рахунках, якi повиннi були бути записанi.

Вам Микола Вiкторович, як своєму другу, сказав лиш цю суму, яку вiн запам’ятав, а от рахунки гри вiн забув. Та якщо ви просто скажете йому кiлькiсть забитих голiв, його влаштує й це. Ваше завдання — знайти цю кiлькiсть голiв, або повiдомити, що Микола Вiкторович не мiг отримати таку суму i заплутався в розрахунках. Формат вхiдних даних

Перший рядок мiстить одне цiле число x (1 ⩽ x ⩽ 109) — суму, яку запам’ятав Микола Вiкторович.

Формат вихiдних даних

Якщо iснує можлива кiлькiсть голiв — виведiть цю кiлькiсть. В iншому випадку виведiть −1.

Приклади

standard input

standard output

6

3

1

1

5

-1

Примiтка

В першому прикладi можливi такi рахунки: 0:1, 0:2, 1:2. Забитих голiв 3, сума чисел 6.

В другому прикладi можуть бути рахунки 0:1 або 1:0. У третьому прикладi неможливо отримати таке число.