Nosaukums
Gaidītie NLO (nlo)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
50%

Definīcija

Zemi regulāri apmeklē N dažādu veidu NLO. Katra veida NLO parādīšanos raksturo noteikts "periods", attiecīgi p1p2, ..., pN dienas. NLO apciemojumu grafiks tiek sastādīts tā, lai nevienā dienā neparādītos vairāk par vienu NLO:

  • izveido tukšu tabulu, kurā katrai dienai, sākot no Zemes atklāšanas, atbilst viens ieraksts;
  • ieplāno pirmā veida NLO parādīšanos dienās ar numuriem p1, 2p1, ...;
  • otrā veida NLO parādīšanos plāno p2-ajā, 2p2-ajā, ... dienā starp tām, kurās neparādās pirmā veida NLO;
  • trešā veida NLO parādīšanos plāno p3-ajā, 2p3-ajā, ... dienā starp tām, kurās neparādās pirmo divu veidu NLO;
  • ...
  • N-tā veida NLO parādīšanās dienas izvēlas pN-ajā, 2pN-ajā, ... dienā starp tām, kurās nav paredzēta iepriekšējo veidu NLO parādīšanās.

Piemēram, ja 5 dažādu veidu NLO parādīšanās periodi ir attiecīgi 5, 3, 4, 4, 3 dienas, tad pirmo divu nedēļu grafiks izskatās šādi:

	Diena                     | 1  2  3  4  5  6  7  8  9 10 11 12 13 14
	--------------------------+-----------------------------------------
	NLO veids                 | -  -  2  5  1  3  2  4  -  1  2  -  3  2
	Parādīšanās kārtas numurs |       1  2  3  4  5  6     7  8     9 10

Zemes zinātnieki, analizējot vairāku gadsimtu gaitā uzkrātos NLO novērojumu datus, šo principu ir noskaidrojuši un tagad vēlas rūpīgāk sagatavoties nākamo NLO sagaidīšanai. Uzrakstiet programmu, kas spētu paredzēt NLO parādīšanos!


Ievaddatu raksturojums

Teksta faila nlo.dat pirmajā rindā dots naturāls skaitlis N – dažādo NLO veidu skaits, 1 ≤ N ≤ 10000. Otrajā rindā, atdalot ar tukšumsimboliem, doti N naturāli skaitļi p1p2, ..., pN, kas nepārsniedz 10000 – attiecīgo NLO veidu parādīšanās periodi. Trešajā ievaddatu faila rindā atrodas naturāls skaitlis M (1 ≤ M ≤ 100000) – tās NLO parādīšanās kārtas numurs, kuru nepieciešams prognozēt.


Izvaddatu raksturojums

Teksta faila nlo.rez vienīgajā rindā izvadiet dienas numuru, kurā NLO parādīsies M-to reizi, kā arī NLO tipu, kurš šajā dienā apciemos Zemi. Skaitļus atdaliet ar tukšumsimbolu.


Piezīmes

Uzdevums izmantots Igaunijas informātikas olimpiādē 2002. gadā.


Paraugdati

Stdin
5
5 3 4 4 3
1
Stdout
3 2

Stdin
5
5 3 4 4 3
10
Stdout
14 2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.