|
A zár
A csapattárs megmentése után felötlött bennünk a gondolat, hogy "mi van
ha a terroristák ismét támadást indítanak ellenünk?", ezért úgy
határoztunk, hogy itt az ideje a "VÉGSŐ LESZÁMOLÁS"-nak és ezúttal mi
fogunk behatolni az ő bázisukra! Az Informatikai Kar rendszergazdái
félállásban a Nemzeti Hírszerzési Ügynökségnél dolgoznak, így
"megmozgattak néhány szálat", hogy megszerezzék a terroristák
rejtekhelyének koordinátáit. Amint azonban a progverseny
csapattagjaiból összeállított speciális különítmény eljutott a
megjelölt helyszínre, egy furcsa számzáras ajtó előtt találták magukat.
A Ti feladatotok eldönteni, hogy a zár feltörhető-e!
Input
A bemenet egyetlen, sor vége jellel lezárt sor, mely egyetlen
olyan pozitív egész n számot tartalmaz, melynek
egyetlen számjegye sem 0.
Szabályok
A feladat ellenőrizni, hogy a kód feltörhető-e, mely alatt azt
értjük, hogy "kitörölhető-e n az alábbi szabályok
szerint?"
- Tekintsük n első számjegyét,
d-t.
- Választunk egy 1 és d
közé eső k számot (a végpontokat is beleértve), majd kitöröljük
n első k karakterét.
Természetesen több karaktert nem tudunk törölni, mint amennyi a
szám hossza.
- Ezt követően az így megmaradt szám első számjegyéből
kötelezően levonjuk k-t amennyiben az így
kapott szám pozitív.
Ha nem akkor az új szám első számjegyét változatlanul hagyjuk.
- Az eljárást folytatjuk ezzel az új n-el egészen addig amíg el nem akadunk,
vagy ameddig a számot teljesen ki nem töröljük.
Megjegyzés: az utolsó törlésnek
pontosnak kell lennie, tehát a feladat csakis
akkor megoldható ha a legutolsó lépésben a szám első számjegye
pontosan megegyezik a szám hosszával. Pontosabb leírásért lásd
a példát és a magyarázatot!
Megjegyzés: gyakran többféle módon is ki lehet
törölni a kezdeti számot, ám a kérdés csupán arra vonatkozik, hogy
lehetséges-e a kitörlés avagy nem.
Output
A kimenet az 1-es szám ha a kód feltörhető és a
0-s szám amennyiben nem.
Példa
Magyarázat
Az első esetben a szám kitörölhető például úgy, hogy az elején 2-t
választunk (1 és 7 között kell választani) és letöröljük az első 2
karaktert. Így 45-höz jutunk, viszont mivel 2 karaktert töröltünk,
így a 4-es számot kötelezően 2-vel csökkentenünk kell. Így az új
számunk 25. Ismét 2-t választva az egész szám eltűnik. Mivel ez a
törlés pontos volt, így a feladat megoldható.
A második esetben az elején csakis 1-et választhatunk, így az első
karaktert törölve 2345-höz jutunk. A 2-est kötelezően csökkentve
1-el az új számunk 1345. Ismét csak 1-et választhatunk, így az első
karaktert törölve 345 a számunk. A 3-ast kötelezően csökkentve 1-el
az új szám 245. Itt választhatunk 1, vagy 2 karakternyi törlést. Ha
2 karaktert választunk akkor a fennmaradó szám az 5-ös, melyet
kötelezően 2-vel csökkentve 3-at kapunk. Viszont ezt nem lehet
pontos törléssel eltüntetni. Ha a 245-ből 1 karakternyi törlést
választunk, úgy a 45 marad meg, ami a kötelező 1-es csökkentés után
35 lesz. Itt a pontos törlés elve miatt nem választhatunk 2
karakternyi törlést, a hossz miatt pedig 3 karakternyit sem, így
csakis 1 karaktert tudunk törölni. Ennek eredménye az 5-ös szám,
melyből a kötelező 1-es csökkentés után 4 marad. Ez pedig ismét nem
eltűntethető a pontos törlés miatt.
Az utolsó számnál (3531211749446117) csak egy lehetséges megoldás
menetét adjuk meg az alábbi rövidítésekkel: Dx = x számjegy
törlése és S = a fennmaradó első számjegy csökkentése. S esetében
nincs paraméter, mert a csökkentés mindig pontosan annyival
történik amennyi számjegyet töröltünk (ha lehetséges).
3531211749446127 -D1,S- 431211749446127 -D4- 11749446127 -D1-
1749446127 -D1,S- 649446127 -D4- 46127 -D3- 27 -D2- NULL
|
|