Problem I/S. 50. (January 2021)

I/S. 50. Subscribers can reach the text of the problem after signing in. The text will be public from January 28, 2021.]

(10 pont)

Deadline expired on February 18, 2021.

Sorry, the solution is available only in Hungarian. Google translation

Legyenek kezdetben \(\displaystyle a=b=c=0\) és \(\displaystyle x=1\) Olyan \(\displaystyle x\)-et keresünk, melyre léteznek olyan \(\displaystyle a\), \(\displaystyle b\) és \(\displaystyle c\) egészek, melyre \(\displaystyle a/x\), \(\displaystyle b/x\) és \(\displaystyle c/x\) megfelelően formázott (kerekített) értékei megegyeznek a bemenetben lévőkkel. Ehhez azt használjuk ki, hogy ha \(\displaystyle x\)-ről \(\displaystyle x+1\)-re növeljük a nevezőt, akkor a megoldáshoz legközelebb eső \(\displaystyle a, b, c\) számok nem változnak sokat.

Így az algoritmus: ha legközelebbi megoldásban (előző \(\displaystyle a,b,\) és \(\displaystyle c\)) valamelyik kerekített érték a bemenetben lévőnél nagyobb, akkor nincs ilyen \(\displaystyle x\)-el megoldás, így megnöveljük x-et. Ha ez nem igaz, akkor minden tört számlálóját addig növeljük, mígy a kerekített érték el nem éri a cél értéket. Ha egyik sem haladja meg azt, találtunk egy megoldást.

Mivel a 4 változó egyszerre növekszik, nem kell minden lehetőséget kipróbálni. Bizonyítható, hogy így biztosan megtaláljuk a legkisebb \(\displaystyle x\)-et.

A lebegőpontos számábrázolásból adódó pontatlanságok elkerüléséért egész számokat és maradékos osztást érdemes használni.

Statistics:

7 students sent a solution.
10 points:	Szakács Ábel.
9 points:	Melján Dávid Gergő.
4 points:	1 student.
3 points:	1 student.
2 points:	1 student.
1 point:	1 student.
0 point:	1 student.

Problems in Information Technology of KöMaL, January 2021