Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | teams2.in, teams2.out | Sursă | Lot Seniori Dorohoi 2019 - Baraj 2 |
| Autor | Costin Oncescu | Adăugată de |  brebenel mihnea stefan •tryharderul |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Teams2
Liceul de Cultura General nr 2 din Dorohoi organizeaza un concurs pe echipe. Fiecare echipa trebuie sa fie formata din K , 3 ≤ K ≤ 4 elevi din generatii consecutive: un elev de clasa a IX-a (generatia 0), unul de clasa a X-a (generatia 1), unul de clasa a XI-a (generatia 2) si optional un elev de clasa a XII-a (generatia 3), daca cel din urma nu este ocupar cu bacaleaureatul. In mod curios, toate clasele liceului sunt formate din N elevi fiecare, 1 ≤ N ≤ 2000
Organizatorii concursului au masurat cu exactitate inteligenta a fiecarui elev si au observat ca nu exista 2 elevi cu acelasi nivel dde inteligenta in intrega scoala. Fiecare elev a primit un If cuprin intre 1 si N * k. Astfel, daca un copil a este mai inteligent decat un copil b, atuncti ID(a) > ID(b).Ei au mai observat ca niciun elev nu va vrea sa fie in aceeasi echipa cu un elev mai inteligent dintr-o generatie mai tanara, deoarece se va simti prost(la figurat). Organizatorii se intreba in cate moduri se pot alege T echipe de K elevi, astfel incat fiecare elev al liceului sa faca parte din maxim o echipa.
Formal, fie K siruri de N elemente ID0, ID1, ...,IDk-1 , reprezentand Id-urile elevilor din cele K generatii, respectiv. Se cere sa se numere in cate moduri se pot elege T echipi de forma (e[i,0],ei,1,...., ei,K-1), 0 ≤ ei,j ≤ N-1 pentru orice 0 ≤ i ≤ T-1, 0 &l;e j ≤ K-1. Toate echipele trebuie sa respecte proprietatea IDj,ei,j < IDj+1,ei,j+1, pentru orice 0 ≤ i ≤ T-1 , 0 ≤ j ≤ K-2. In plus, niciun elev nu poate sa apara in mai mult de o echipa. Doua modalitati de a alege echipele se considera distincte daca exista cel putin o echipa care apare intr-o modalitate si nu apare in cealalta.
Date de intrare
- linia 1: K N T, reprezentand numarul de generatii, numarul de elevi din fiecare generatie, respectiv numarul de echipe care trebuie formate.
- linia 2 + i: IDi,0 IDi,1 ... IDi,N-1, (0 ≤ i ≤ K-1)
Date de ieşire
În fisierul de iesire se va afla numaruld e echipe ce se pot forma modulo 6 700 417
Punctare
| Subtask | Punctaj | Constrangeri |
|---|---|---|
| 1 | 6 puncte | 1 ≤ T ≤ N ≤ 5 K = 3 |
| 2 | 6 puncte | 1 ≤ T ≤ N ≤ 20 K = 3 |
| 3 | 31 puncte | 1 ≤ T ≤ B ≤ 40 K = 3 |
| 4 | 16 puncte | 1 ≤ T ≤ N ≤ 300 K = 3 |
| 5 | 16 puncte | 1 ≤ T ≤ 2000 K = 3 |
| 6 | 16 puncte | 1 ≤ T ≤ N ≤ 25 K = 4 |
| 7 | 9 puncte | 1 ≤ T ≤ N ≤ 300 K = 4 |
Exemplu
| teams2.in | teams2.out |
|---|---|
| 3 3 2 5 4 2 7 1 3 6 8 9 | 8 |
| 4 3 1 2 1 4 3 7 5 11 6 10 9 8 12 | 31 |
| 3 8 8 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | 4201486 |
Explicaţie
ID-urile elevilor din cele 8 solutii din primul exemplu sunt:
• (5, 7, 8) si (2, 3, 6)
• (5, 7, 8) si (2, 3, 9)
• (5, 7, 9) si (2, 3, 6)
• (5, 7, 9) si (2, 3, 8)
• (4, 7, 8) si (2, 3, 6)
• (4, 7, 8) si (2, 3, 9)
• (4, 7, 9) si (2, 3, 6)
• (4, 7, 9) si (2, 3, 8)
