F2 - Tester

Časový limit: 4s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3.4, Python 3.11

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Palma je obľubená súťaž a jej organizácia si tiež vyžaduje nemálo času. Kedže úloh je veľa, je nutné ich prípravu vhodne manažovať. Počas prípravy kola sa úlohy nielen vymýšlajú, ale aj testujú a to občas býva problém. Máme totiž N organizátorov Palmy potrebujeme nimi otestovať M úloh. Každý organizátor nám zväčšia dopredu povie, koľko úloh by v čase prípravy bol ochotný testovať t₁,t₂,...,t_N. Naviac, ku každému z nich vieme, ktoré úlohy by (chcel) vedel preriešiť. Ľahké úlohy stačí, ak testuje iba jeden, ťažké úlohy treba testovať viacerými. Teda ku každej úlohe máme daný aj počet, koľkokrát by sme ju chceli testovať u₁,u₂,...,u_M.

Úloha

Nájdite také rozdelenie, že i-ty vedúci bude testovať maximálne t_i úloh a j-ta úloha bude testovaná práve u_i krát, pričom každý vedúci vie riešiť všetky úlohy, na ktoré bol pridelený.

Vstup

Prvý riadok vstupu obsahuje dve kladné celé čísla N a M. Druhý riadok obsahuje kladná celé čísla t₁,t₂,...,t_N. (1≤t_i≤M, pre každé i=1,2,...,N). Tretí riadok vstupu obsahuje M kladných celých čísel u₁,u₂,...,u_M. (1≤u_i≤N, pre každé j=1,2,...,M). Každý zo záverečných N riadkov bude v nasledujúcom tvare:

Prvé číslo v i-tom riadku (označme d_i) určuje počet úloh, ktoré vie vyriešiť i-ty vedúci.
Ďalej nasleduje číselný zoznam úloh, ktoré vie i-ty vedúci vyriešiť

Úlohy sú očíslované v poradí 1,2,...,M.

Vstup

Výstup má obsahovať priradenia úloh k vedúcim. Každý riadok výstupu má obsahovať dve kladné celé čísla - číslo vedúceho a číslo úlohy. Kedže možných rozvrhov môže existovať viac, akceptovaný bude ľubovoľný z nich. V prípade, že nie je možné otestovať všetky úlohy podľa nášho plánu, vypíšte jeden riadok (ukončený znakom konca riadku) s obsahom "neda sa".

F1

N ≤ 10
M ≤ 10
1≤ d_i ≤ 2, pre každé i=1,2,...,N.

F2

N ≤ 1.000
M ≤ 1.000
d_i ≤ 50, pre každé i = 1,2,...,N.

Príklad1

Vstup:

4 6
2 2 2 2
1 1 1 1 2 1
2 1 2
2 3 4
2 4 5
2 5 6

Výstup:

Príklad2

Vstup:

4 6
2 2 2 2
1 2 1 1 1 1
2 1 2
2 3 4
2 4 5
2 5 6

Výstup:

neda sa

07 Finále 2