Problemi 024

Kërkesa

Në brinjët e një trekëndëshi barabrinjës vendosim disa pika të baraslarguara nga njëra-tjetra, dhe i bashkojmë me vija, si në figurë:

Le të quajmë të rregullt vetëm trekëndëshat që e kanë majën lart dhe bazën poshtë. Nqs ndarjet e brinjëve i quajmë 1 njësi, dhe trekëndëshi i madh e ka brinjën \(L\) njësi, sa trekëndësha të rregullt me brinjë \(K\) njësi (ku \(1 \leq K \leq N\)) ndodhen në figurë?

Referenca: https://www.codechef.com/problems/ZUBTRCNT

Shembull

$ cat input.txt
2
4 3
4 4

$ python3 prog.py < input.txt
Case 1: 3
Case 2: 1

Rezultati duhet të shfaqet në formën Case i: dhe pastaj përgjigja.

Zgjidhja 1

Sqarime

Sado që të jetë K-ja, kemi të paktën një trekëndësh të rregullt me brinjë K njësi (i cili e ka kulmin në pikën \(A\)). Kështu që fillimisht shënojmë nr = 1. Pastaj, duke e ulur kulmin e trekëndëshit një nivel më poshtë, do kemi 2 trekëndësha të tjerë (me kulme në pikat \(P_1\) dhe \(P_2\)). Në nivelin e tretë do kemi 3 trekëndësha të tjerë (me kulme në \(Q_1\), \(Q_2\) dhe \(Q_3\)), e kështu me radhë. Gjatësia K e brinjës së trekëndëshit të rregullt na kufizon sa nivele mund të ulemi.

Detyra

Mamaja i ka blerë Cufit dy shporta me fruta, njëra ka N mollë dhe tjera ka M portokalle. Cufit i pëlqejnë edhe mollët edhe portokallet dhe do që ti ketë në sasi të barabartë. Çdo kokërr mollë ose portokalle kushton 1 monedhë, dhe Cufi ka K monedha në xhep. Me këto monedha ai mund të blejë mollë ose portokalle dhe të përpiqet ta bëjë ndryshimin midis tyre sa më të vogël.

Bëni një program që të gjejë ndryshimin më të vogël të mundshëm që mund të arrijë Cufi midis mollëve dhe portokalleve.

Referenca: https://www.codechef.com/problems/FRUITS

Shembull

$ cat input.txt
3
3 4 1
5 2 1
3 4 3

$ python3 prog.py < input.txt
0
2
0

Jepen numrat N, M dhe K. Në rastin e parë Cufi mund të blejë një mollë dhe ti bëjë të barabarta. Në rastin e dytë mund të blejë vetëm një portokalle dhe diferenca bëhet 2. Në rastin e tretë mund të blejë 2 mollë dhe një portokalle, duke e bërë diferencën 0.