Fişierul intrare/ieşire:	ksecv4.in, ksecv4.out	Sursă	ONI 2015 Clasele 11-12
Autor	Mihai Ciucu, Radu Stefan Voroneanu	Adăugată de	Andrei Stanciu •assa98
Timp execuţie pe test	0.15 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Ksecv4

Fie un vector V cu N elemente şi un număr K. Vectorul V trebuie împărţit în exact K subsecvenţe nevide, astfel încât fiecare element din vector să aparţină exact unei subsecvenţe. Această împărţire trebuie făcută astfel încât maximul şmecheriei fiecărei subsecvenţe să fie cât mai mic. (Această problemă concepe greşit sistemul de şmecherie şi valoare). Şmecheria fiecărei subsecvenţe se defineşte ca fiind parte întreagă din ((Vmax – Vmin + 1) / 2), unde Vmax este valoarea maximă din subsecvenţă, iar Vmin este valoarea minimă.

Vectorul V de N elemente va fi generat în felul următor: se dă un număr M şi 2 vectori A şi B de lungime M (indexaţi de la 0 la M – 1). Fiecare element i, 0 ≤ i < N, din vectorul V va fi calculat cu următoarea formulă: V[i] = (A[i mod M] xor B[i / M]), unde x mod y reprezintă restul lui x la împărţirea cu y, x / y reprezintă câtul împărţirii lui x la y, şi x xor y reprezintă rezultatul operaţiei xor (sau exclusiv pe biţi) dintre x şi y.

Date de intrare

Pe prima linie a fişierului ksecv.in se află 3 numere naturale N, K şi M, cu semnificaţia din enunţ, separate prin câte un spaţiu. Pe a doua linie a fişierului se află M numere naturale separate prin câte un spaţiu, reprezentând vectorul A. Pe a treia linie se află M numere naturale separate prin câte un spaţiu, reprezentând vectorul B.

Date de ieşire

Pe prima linie a fişierului de ieşire ksecv.out se va afişa cel mai mic număr natural S pentru care vectorul V poate fi împărţit în exact K subsecvenţe nevide, fiecare având şmecheria mai mică sau egală cu S.

Restricţii

• ... ≤ ... ≤ ...
• 1 ≤ N ≤ 1 000 000
• 1 ≤ K ≤ 1 000
• 1 ≤ M ≤ 2 048
• N < M*M
• 1 ≤ K < N
• Valorile vectorilor A şi B vor fi din intervalul [0, 2⁶⁰ - 1]
• Fiecare din cele K subsecvenţe trebuie să aibă cel puţin un element.
• Pentru 20% din teste N ≤ 100, K ≤ 50.
• Pentru alte 20% din teste N ≤ 100 000, K ≤ 1000.
• Pentru alte 20% din teste N ≤ 1 000 000, K ≤ 50.
• Vectorul V are indicii indexaţi de la 0 la N – 1.
• Vectorii A şi B au indicii indexaţi de la 0 la M – 1.

Exemplu

table(example). |_. ksecv4.in |_. ksecv4.out |
| 6 3 6
13 4 6 19 4 10
0 0 0 0 0 0
| 5
|
|
| 6 4 6
13 4 6 19 4 10
0 0 0 0 0 0
| 3
|
|
| 6 3 3
3 4 2
4 5 3
| 3
|

Explicaţie

In primul exemplu valorile vectorului V sunt 13, 4, 6, 19, 4, 10.
Dacă împărţim şirul în subsecvenţele [0,2] [3,3] [4,5] obţinem şmecheriile 5, 0, 3. Şmecheria maxima este 5.
Nu putem împărţi vectorul V astfel încât şmecheria maximă a unei subsecvenţe să fie mai mică decât 5.

In al doilea exemplu valorile vectorului V sunt 13, 4, 6, 19, 4, 10.
O posibilă împărţire este: [0,0] [1,2] [3,3] [4,5]. Şmecheriile fiecărei subsecvenţe sunt 0, 1, 0, 3.

In al treilea exemplu valorile vectorului V sunt 7, 0, 6, 6, 1, 7.
Dacă împărţim în subsecvenţele [0,0], [1,4] [5,5], obţinem şmecheriile 0, 3, 0.

Cum se trimit solutii?