In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Pan Wojciech postanowił rozkręcić nowy biznes i ma zamiar otworzyć Sobotnią Szkółkę Hakowania (SSH), której będzie dyrektorował. Napisał już stosowny program nauczania, który zatwierdziło ministerstwo, zatrudnił nauczycieli, wynajął sal wykładowych w pobliskiej remizie strażackiej i nie pozostało mu nic innego jak ogłosić nabór do klas.
Problem w tym, że trzeba najpierw ułożyć plan zajęć dla SSH. Pan Wojciech już próbował, ale niestety nie jest usatysfakcjonowany ze swojej pracy. Jest świadomy tego, że jako dyrektor będzie musiał siedzieć w szkole od samego rana do czasu, aż ostatni uczeń opuści mury remizy. A z planu, który sobie przygotował, wynikało, że będzie musiał siedzieć tam cały dzień. Twoim zadaniem jest pomóc panu Wojciechowi i przygotować optymalny plan zajęć.
W szkole będzie nauczanych przedmiotów. Każdy przedmiot ma przypisanego nauczyciela, który będzie go wykładał, oraz klasę, która będzie na te wykłady uczęszczała. Każdej soboty na przedmiot ma być przeznaczona jedna godzina lekcyjna.
W danej chwili nauczyciel może prowadzić tylko jeden przedmiot, klasa może słuchać tylko jednego nauczyciela, a w sali mogą odbywać się tylko jedne zajęcia.
Załóżmy, że w SSH jest zatrudnionych dwóch nauczycieli, są dwie klasy oraz sześć przedmiotów: (1,1), (1,1), (1,2), (2,2), (2,2), (2,2). Tutaj przedmioty opisujemy jako pary (numer nauczyciela, numer klasy). Zauważmy, że dany nauczyciel może wykładać dla danej klasy więcej niż jeden przedmiot.
Jeśli mamy do dyspozycji tylko jedną salę wykładową, to pan Wojciech będzie musiał siedzieć w szkole przez 6 godzin (żadne zajęcia nie będą mogły odbywać się równolegle, a mamy ich sześć). Ale już dysponując dwoma salami, będzie można skrócić ten czas do czterech godzin. Optymalny plan może wyglądać następująco:
Godz. | Sala 1 | Sala 2 |
1 | (1,2) | - |
2 | (2,2) | - |
3 | (1,1) | (2,2) |
4 | (1,1) | (2,2) |
W pierwszym wierszu wejścia znajdują się cztery liczby całkowite oddzielone pojedynczymi odstępami (). Oznaczają one kolejno: liczbę nauczycieli w szkole, liczbę klas, liczbę nauczanych przedmiotów oraz liczbę dostępnych sal wykładowych. W kolejnych wierszach opisane są przedmioty. -szy wiersz zawiera dwie liczby całkowite opisujące -ty przedmiot (, ). Oznaczają one odpowiednio: nauczyciela, który będzie uczył -tego przedmiotu, oraz klasę, która będzie uczęszczała na ten przedmiot.
W pierwszym wierszu wyjścia należy zapisać jedną liczbę całkowitą oznaczającą minimalną liczbę godzin, które dyrektor będzie musiał spędzić w szkole każdej soboty. (Nigdzie nie jest powiedziane, że godzina lekcyjna w SSH trwa 45 minut, więc może być całkiem duże.) W kolejnych wierszach należy zapisać plan zajęć realizowalny w godzinach. W -szym wierszu należy wypisać jedną dodatnią liczbę całkowitą nie większą niż oznaczają godzinę lekcyjną, w której będzie się odbywało nauczanie -tego przedmiotu.
Jeśli istnieje więcej niż jedno rozwiązanie, Twój program może wypisać dowolne z nich.
Dla danych wejściowych:
2 2 6 2 1 1 1 1 1 2 2 2 2 2 2 2
poprawną odpowiedzią jest:
4 4 3 1 4 3 2
Autor zadania: Tomasz Idziaszek.