Fişierul intrare/ieşire:socks.in, socks.outSursăACM-ICPC Faza Nationala 2017
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Socks

Citesti tabloidul local, cum faci in fiecare zi. N-ar trebui, dar asta faci. Printre articole:

- "Zece optimizari pe care compilatoarele nu vor sa le stii!"
- "Vezi ce olimpic renumit se muta la ASE!"
- "Cautand prin borderouri: ce olimpic si-a inlocuit cafeaua de dimineata cu ... FFT-ul de dimineata."
- "<M-am gandit la viitorul meu si am decis ca este optim sa fac facultatea la UNIBUC si sa ma sustin financiar facand temele celor de la Poli.> Marturisirea cutremuratoare a unui tanar de clasa a 12-a."
- "SONDAJ: Ce se cere mai mult pe piata muncii? Inteligenta, persistenta sau smenul de la Aliens?"

Same old. Same old. In schimb, la sectiunea "Barfe despre info-vedete", vezi un articol care te stimuleaza algoritmic:

Alex Velea si iubita au probleme cu.. sosetele?

Renumitul artist-tractorist Alex Velea a fost surprins recent impreuna cu iubita sa cumparand sosete. Dupa cum cititorii nostri stiu prea bine, Alex are o istorie complicata cu sosetele. De aceasta data, Alex doreste sa cumpere P tipuri de sosete dintre cele N disponibile la magazinul ales. Fiecare tip este definit de doi parametri: culoarea si marimea. Gurile rele spun ca iubita lui Alex ii impune o restrictie.. neobisnuita achizitiei sale. Ea stie ca Alex este foarte nepasator atunci cand isi imbraca sosetele. Mai exact, pentru Alex este acceptabil sa imbrace doua sosete daca acestea au aceeasi marime sau aceeasi culoare. Prietena lui Alex numeste o pereche in care sosetele au aceeasi marime sau aceeasi culoare dar nu au aceeasi marime si aceeasi culoare ca fiind "ciudata".

Ea ar dori ca Alex sa-si cumpere P tipuri de sosete astfel incat numarul total de perechi de tipuri de sosete ciudate formate sa fie minim posibil. Ea vrea raspunsul pentru fiecare P de la 1 la K.

Date de intrare

Fişierul de intrare socks.in va contine pe prima sa linie numerele N si K, reprezentand numarul de tipuri de sosete disponibile, respectiv limita superioara a P-ului pentru care prietena lui Alex vrea sa afle raspunsul.
Urmatoarele N linii vor contine o pereche culoare marime, culoare fiind un sir de caractere, iar marime este un numar natural.

Date de ieşire

În fişierul de ieşire socks.out se vor afla K linii, a i-a continand raspunsul pentru P = i.

Restricţii

  • 1 ≤ K ≤ N ≤ 1000
  • 1 ≤ Marimile sosetelor ≤ 109
  • Culorile sosetelor sunt siruri de caractere de lungime maxim 20, fara spatii.
  • Toate cele N tipuri de sosete disponibile sunt distincte doua cate doua (difera fie marimea, fie culoarea, fie ambele).

Exemplu

socks.insocks.out
3 3
Nelachet 45
Lachet 43
Lachet 45
0
0
2

Explicaţie

Pentru P = 1 Alex poate cumpara oricare dintre cele trei tipuri de sosete.
Pentru P = 2 Alex va cumpara tipurile 1 si 2, care au atat culorile cat si marimile distincte. Astfel, nu va face nicio pereche ciudata.
Pentru P = 3 Alex va fi obligat sa cumpere si al treilea tip de sosete. Acesta formeaza o pereche ciudata cu tipul 1 (deoarece au aceeasi marime, dar culori diferite) si cu tipul 2 (deoarece au aceeasi culoare, dar marimi diferite). Astfel, raspunsul este 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?