Māju būve

ID: buve
Grūtība: 4/5
Laika limits: 1

Uzdevums

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.

 

Ievaddati

Teksta faila buve.in 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.

 

Izvaddati

Teksta faila buve.out 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.

 

Piemērs

buve.in buve.out
50
30
10
12

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]

 

Atsauces

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


© 2001-2002 olimps! http://www.lio.lv/olimps/