Rezolvare PBinfo #4340

Un hotel pentru carantină COVID are k camere. În fiecare cameră poate sta la un moment dat un singur pacient. Hotelul este utilizat o perioadă de z zile dintr-un an. Perioada de carantină pentru fiecare pacient este exact m zile din perioada z. DSP a trimis conducerii hotelului o solicitare de cazare pentru n pacienți. Pentru fiecare pacient este precizată prima zi din perioadă începând cu care va trebui să fie cazat – perioada z începe cu ziua 1.

Cerința

1. DSP solicită determinarea numărului maxim de pacienți care vor putea fi primiţi în hotel conform solicitării trimise.
2. DSP solicită o listă cu numerele de ordine a pacienților din lista trimisă, care vor putea fi cazați.
3. Care este cea mai lungă secvență de pacienți din lista trimisă de DSP care nu au putut fi cazați. Afișați lungimea secvenței, precum și numărul de ordine al primului pacient al secvenței.

Date de intrare

Pe prima linie a fișierului de intrare hotel.in este scrisă cerința (1, 2 sau 3). Pe linia a doua a fișierului de intrare sunt scrise valorile k m n z (k – numărul de camere din hotel, m – zile carantină, n – numărul pacienților, z – perioada). Pe următoarea linie (a treia) sunt scrise n numere naturale, separate prin câte un spațiu, reprezentând ziua în care începe carantina pentru pacientul respectiv.

Date de ieșire

Dacă cerința este 1, pe prima linie a fișierului de ieșire hotel.out va fi scris numărul maxim de pacienți care pot fi cazaţi în hotel conform solicitării trimise de DSP. Dacă cerința este 2, pe prima linie vor fi scrise, separate prin câte un spațiu, numerele de ordine ale pacienților cazați, în ordinea în care se va face cazarea lor. Pacienții care sunt cazați în aceiași zi, vor fi cazați în ordinea din lista trimisă de DSP. Dacă cerința este 3 pe prima linie se vor afișa două numere naturale a și b, separate printr-un spațiu, reprezentând numărul maxim de pacienți necazați consecutiv din lista trimisă de DSP, respectiv numărul de ordine al primului pacient din secvența respectivă. Dacă există mai multe soluții la cerința 3, se va afișa cea cu numărul de ordine al primului pacient minim.

Restricții și precizări

• 1 ≤ k ≤ 100
• 1 ≤ z ≤ 365
• 1 ≤ m ≤ z
• 1 ≤ n ≤ 1000
• solicitările de cazare corespund numai celor z zile din perioada de utilizare a hotelului, ceea ce înseamnă că un pacient nu poate fi cazat mai puțin de m zile şi acestea trebuie să facă parte din perioada de z zile
• cel puțin un pacient poate fi cazat, iar dacă toți pacienții au fost cazați, la cerința 3 se vor afișa două valori 0
• cerința 1 – 39 puncte; cerința 2 – 30 puncte; cerința 3 – 21 puncte
• 10 puncte se acordă pentru testele din enunț

Exemplul 1:

hotel.in

1
2 7 8 365
1 10 2 11 1 3 4 18

hotel.out

5

Explicație

Cerința 1. Sunt 2 camere, perioada de carantină este de 7 zile, sunt 8 pacienți, hotelul este utilizat 365 zile. Pot fi cazați 5 pacienți adică pacienții cu numerele de ordine 1, 5, 2, 4, 8.

Exemplul 2:

hotel.in

2
2 7 8 365
1 10 2 11 1 3 4 18

hotel.out

1 5 2 4 8

Explicație

Cerința 2. Sunt cazați pacienții cu numerele de ordine 1 și 5, în această ordine. Ambele camere devin disponibile din ziua 8. În ziua 10 este cazat în camera 1 pacientul cu numărul de ordine 2, iar în ziua 11 pacientul cu numărul de ordine 4 în camera 2. Camera 1 devine liberă din ziua 18, pacientul cu numărul de ordine 8 este cazat aici.

Exemplul 3:

hotel.in

3
2 7 8 365
1 10 2 11 1 3 4 18

hotel.out

2 6

Explicație

Cerința 3. Nu au putut fi cazați pacienții cu numerele de ordine 3, 6 și 7. Deci secvența cu număr maxim de pacienți necazați este 6 7. Secvența are 2 pacienți, primul având numărul de ordine 6.