Nosaukums
Māju būve (buve)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

Neveiksmju salas celtniecības kompānijai ir dots pasūtījums uzbūvēt L vienādas dzīvojamās mājas. Katras mājas uzcelšanai nepieciešami X dēļi un zemes gabals viena salas laukuma vienības lielumā. Pasūtījuma realizācijai ir piešķirta apbūves platība tieši L salas laukuma vienības. Kompānijai jau pieder 10 dēļu izgatavošanas darbnīcas citā salas rajonā. Lai ātrāk izpildītu pasūtījumu, var rasties nepieciešamība pēc papildu darbnīcām. Katras darbnīcas uzcelšanai nepieciešami Y dēļi un zemes gabals viena salas laukuma vienības lielumā. Tā kā salas valdība nav ar mieru piešķirt papildus zemi darbnīcu būvei, tad vienīgā iespēja ir izmantot pasūtījuma izpildei piešķirto zemes gabalu un nepieciešamības gadījumā vēlāk šīs darbnīcas nojaukt.
Katra darbnīca vienā dienā izgatavo 10 dēļus. Visu darbnīcu izgatavotie dēļi ir pilnīgi vienādi. Tie dēļi, kuri to saražošanas dienā nav izmantoti kādai būvei, neglābjami sabojājas - tos pa nakti sagrauž mazie zaļie dēļgrauži. Arī nojaukto darbnīcu dēļus šī iemesla dēļ atkārtoti izmantot nevar.

Vienas dienas laikā kompānijas strādnieki var veikt vienu no sekojošiem trim darbiem:
1) Uzbūvēt jebkuru skaitu darbnīcu, ja tajā dienā strādājošās darbnīcas izgatavo nepieciešamo dēļu skaitu un vēl neapbūvētā platīva ir pietiekoši liela.
2) Uzbūvēt jebkuru skaitu māju, ja tajā dienā strādājošās darbnīcas izgatavo nepieciešamo dēļu skaitu un vēl neapbūvētā platība ir pietiekoši liela.
3) Nojaukt jebkuru skaitu darbnīcu.

Uzbūvētās darbnīcas var sākt darbu (izgatavot 10 dēļus dienā) sākot no nākamās dienas.


Uzrakstiet programmu, kas kompānijas vadītājam palīdz izrēķināt mazāko dienu skaitu, kāds nepieciešams pasūtījuma izpildei.


Ievaddatu raksturojums

Ievaddatu pirmā rinda satur naturālu skaitli L (L <= 2500), kas ir pasūtīto māju skaits. Otrā rinda satur naturālu skaitli X (X <= 255) - dēļu skaitu, kas nepieciešams vienas mājas uzcelšanai. Trešā rinda satur naturālu skaitli Y (Y <= 255) - dēļu skaitu, kas nepieciešams vienas darbnīcas uzcelšanai.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada vesels skaitlis - mazākais dienu skaits, kāds nepieciešams pasūtījuma izpildei.
Ja dotajiem ievaddatiem pasūtījumu izpildīt nav iespējams, failā jāizvada skaitlis 0.


Piezīmes

Dotajā testpiemērā viens no iespējamajiem veidiem pasūtījumu veikt 12 dienās ir sekojošs:

Sākumā [mājas:0, darbnīcas:10, brīvā vieta:50]
1.diena: Uzceļ 10 darbnīcas [0,20,40] 7.diena: Uzceļ 5 mājas [35,15,10]
2.diena: Uzceļ 10 darbnīcas [0,30,30] 8.diena: Uzceļ 5 mājas [40,15,5]
3.diena: Uzceļ 10 mājas [10,30,20] 9.diena: Uzceļ 5 mājas [45,15,0]
4.diena: Uzceļ 10 mājas [20,30,10] 10.diena: Nojauc 5 darbnīcas [45,10,5]
5.diena: Uzceļ 10 mājas [30,30,0] 11.diena: Uzceļ 3 mājas [48,10,2]
6.diena: Nojauc 15 darbnīcas [30,15,15] 12.diena: Uzceļ 2 mājas [50,10,0]

 

Uzdevums izmantots Latvijas 13.informātikas olimpiādes Valsts posma sacensībās 2000.gadā.
Autors: Renārs Gailis


Paraugdati

Stdin
50
30
10
Stdout
12

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