Nosaukums
Tuvošanās skaitlim no apakšas (tuvap)
Laika limits
1.00s
Atmiņas limits
32.0 MB
Grūtība
79%

Definīcija

Pieņemsim, ka jums ir dota papīra strēmele, uz kuras uzrakstīts naturāls skaitlis n. Šo strēmeli drīkst sagriezt daļās tā, ka uz katras no tām paliek uzrakstīts vesels nenegatīvs skaitlis (vairākciparu skaitlis nedrīkst sākties ar 0). Tā, piemēram, ja sākumā uz strēmeles ir rakstīts skaitlis 19073, tad to var sagriezt daļās 190 un 73, vai arī 1 un 9073, vai 19, 0 un 73, vai vēl citos veidos. Katram sagriešanas variantam iespējams aprēķināt uz strēmeles daļām uzrakstīto skaitļu kopsummu. Aplūkotajā piemērā šī summa var būt 19073 (ja nekas netiek griezts), 190+73=263, 1+9073=9074, 19+0+73=92, utt.

Uzrakstiet programmu, kas ievadītam naturālam skaitlim n un naturālam skaitlim m nosaka, kā jāsagriež strēmele, lai pēc sagriešanas uz visām daļām uzrakstīto skaitļu summa būtu pēc iespējas tuvāk skaitlim m, to nepārsniedzot!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dotas divu naturālu skaitļu n un m vērtības. Zināms, ka n un m ciparu skaits nepārsniedz 9.


Izvaddatu raksturojums

Izvaddatu pirmajā rindā jāizvada skaitļu summa, kas iegūta iepriekšaprakstītajā veidā un kas ir vistuvāk skaitlim m.
Ja, neatkarīgi no griešanas veida, iegūtā summa vienmēr pārsniedz skaitli m, tad failā jāizvada skaitlis 0.


Piezīmes

Uzdevuma ideja ņemta no ACSL 1996./97. gada sacensībām. 

Autors: M.Opmanis


Paraugdati

Stdin
23051 1
Stdout
0

Stdin
19967 1000
Stdout
986

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