hotel

Time limit: 0.03s Memory limit: 64MB Input: hotel.in Output: hotel.outPoints by default: 10p

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

Cerință

  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 (11, 22 sau 33). Pe linia a doua a fișierului de intrare sunt scrise valorile k m n zk \ m \ n \ z (kk - numărul de camere din hotel, mm - zile carantină, nn - numărul pacienților, zz - perioada). Pe următoarea linie (a treia) sunt scrise nn 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 11, 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 22 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 33 pe prima linie se vor afișa două numere naturale aa și bb, 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 33, se va afișa cea cu numărul de ordine al primului pacient minim.

Restricții și precizări

  • 1k1001 \leq k \leq 100
  • 1z3651 \leq z \leq 365
  • 1mz1 \leq m \leq z
  • 1n10001 \leq n \leq 1000
  • solicitările de cazare corespund numai celor zz zile din perioada de utilizare a hotelului, ceea ce înseamnă că un pacient nu poate fi cazat mai puțin de mm zile şi acestea trebuie să facă parte din perioada de zz zile
  • cel puțin un pacient poate fi cazat, iar dacă toți pacienții au fost cazați, la cerința 33 se vor afișa două valori 00
  • cerința 113939 puncte; cerința 223030 puncte; cerința 332121 puncte
  • 1010 puncte se acordă din oficiu

Exemplul 1

hotel.in

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

hotel.out

5

Explicație

Cerința 11. Sunt 22 camere, perioada de carantină este de 77 zile, sunt 88 pacienți, hotelul este utilizat 365 zile. Pot fi cazați 55 pacienți adică pacienții cu numerele de ordine 1,5,2,4,81, 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 22. Sunt cazați pacienții cu numerele de ordine 11 și 55, în această ordine. Ambele camere devin disponibile din ziua 88. În ziua 1010 este cazat în camera 11 pacientul cu numărul de ordine 22, iar în ziua 1111 pacientul cu numărul de ordine 44 în camera 22. Camera 11 devine liberă din ziua 1818, pacientul cu numărul de ordine 88 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 33. Nu au putut fi cazați pacienții cu numerele de ordine 3,63, 6 și 77. Deci secvența cu număr maxim de pacienți necazați este 6 76 \ 7. Secvența are 22 pacienți, primul având numărul de ordine 66.

Log in or sign up to be able to send submissions!