W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Z uwagi na nadchodzące wakacje wiele osób zaczyna planować wyjazdy. Aby zapewnić sobie towarzystwo, każdy chce wybrać się na wycieczkę w grupie ze swoimi znajomymi. Biuro podróży ma w swej ofercie różne wycieczki adresowane do grup o określonej liczebności - dla każdej wycieczki podany jest dolny i górny limit na liczbę osób, które mogą na nią pojechać. Każda grupa może wybrać tylko jedną wycieczkę. Co więcej, każda wycieczka może zostać wybrana przez co najwyżej jedną grupę. Pracownicy biura podróży poprosili Cię o pomoc. Chcą oni zorganizować jak najwięcej wycieczek. Twoim zadaniem jest przyporządkowanie grup do wycieczek w taki sposób, aby można było zorganizować największą możliwą liczbę wycieczek.
Napisz program, który:
Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite oraz oddzielone pojedynczym odstępem, , ; jest liczbą grup, jest liczbą wycieczek. Grupy są ponumerowane od do , a wycieczki od do .
Kolejne wierszy zawiera wielkości poszczególnych grup. Wiersz -szy zawiera liczbę całkowitą - wielkość -tej grupy, .
Kolejne wierszy zawiera opisy wycieczek, jedna wycieczka w wierszu. Wiersz -szy zawiera dwie liczby całkowite i , oddzielone pojedyńczym odstępem: jest minimalną, a maksymalną liczebnością grupy, która może pojechać na tę wycieczkę, .
Pierwszy wiersz wyjścia powinien zawierać jedną liczbę całkowitą - maksymalną liczbę wycieczek, które mogą zostać zorganizowane. Kolejne wierszy powinno zawierać opisy przyporządkowań grup do wycieczek. Każdy z tych wierszy powinien zawierać parę liczb całkowitych oddzielonych pojedynczym odstępem: numer grupy oraz numer wycieczki. Może istnieć wiele poprawnych rozwiązań, a Twój program ma wypisać dowolne z nich.
Dla danych wejściowych:
5 4 54 6 9 42 15 6 6 20 50 2 8 7 20
poprawną odpowiedzią jest:
3 2 1 3 4 4 2
Autor zadania: Krzysztof Sikora.