Zadanie

Mišof doma upratoval a v krabici od topánok našiel celkom peknú úlohu. Bolo mu ju ľúto vyhodiť a na jej riešenie nemal čas, tak sa rozhodol, že ju dá vám. Zadanie vyzerá nasledovne:

Každé číslo je prirodzené číslo od 1 do 100.

Každý výraz je buď súčin, alebo výraz+súčin, alebo výraz-súčin.

Každý súčin je buď term alebo súčin*term.

Každý term je buď číslo, alebo (výraz), alebo unárfcia, alebo binárfcia.

Každá unárfcia je div2(výraz). Funkcia div2 pre vstup \(x\) vracia hodnotu \(x/2\) zaokrúhlenú nadol.

Každá binárfcia je buď min(výraz,výraz) alebo max(výraz,výraz) – význam týchto funkcií je snáď jasný.

Úloha

Na vstupe je nejaký výraz. Naschvál sme ho pokazili: namiesto niektorých čísel v ňom môže byť otáznik.

Zistite, či má daný výraz jednoznačne určenú hodnotu. Ak áno, nájdite ju.

Formát vstupu

Vstup má niekoľko riadkov (od 1 do 10). V každom je jeden výraz. Každý výraz má aspoň 1 a najviac 100 znakov a spĺňa vyššie uvedený popis.

Formát výstupu

Pre každý výraz zo vstupu vypíšte jeden riadok. Ak je jeho hodnota jednoznačne určená, vypíšte ju, inak vypíšte otáznik.

Hodnotenie

Je 20 vstupov. V prvých 6 vstupoch nie sú otázniky. Ďalšie 4 sú v nejakom zmysle ľahké.

Príklad

Input:

2+3*4
?+?
100-?
max(?,100)
div2(div2(div2(div2(div2(div2(div2(?)))))))
((?*?)+(?*?))*(1-1)
100*100*100*100*100*100*100*100*100*100*100

Output:

14
?
?
100
0
0
10000000000000000000000

V prvom rade si všimneme, že hodnota v poslednom príklade v zadaní sa nám nezmestí do 64-bitového intu. Bude teda treba buď implementovať vlastnú aritmetiku veľkých čísel (komu sa chce?) alebo použiť jazyk, ktorý ju už má (teda Python, v najhoršom BigIntegery v Jave).

Druhé užitočné pozorovanie: všetky tri funkcie zo zadania sú neklesajúce. Neformálne: čím väčší vstup, tým väčší výstup.

Pozorovanie číslo tri. Na to, aby sme zistili, či má výraz jednoznačnú hodnotu, stačí nájsť jeho najmenšiu možnú a najväčšiu možnú hodnotu a zistiť, či sa rovnajú.

V tejto chvíli zrejme mnohých pokúšalo hľadať minimum tak, že za všetky otázniky dosadíme nulu a maximum tak, že za všetky dosadíme stovku. Vďaka vyššie uvedenému pozorovaniu číslo dva by tento postup skutočne fungoval – nebyť jedného detailu. Presnejšie: keby jediné povolené binárne operácie boli sčítanie a násobenie (ktoré sú tiež na nezáporných číslach neklesajúce), skutočne by sme takto dostali najmenšiu a najväčšiu hodnotu výrazu.

My tu ale ešte máme jednu koťuhu: operátor mínus. A ten sa správa ináč. Napríklad u výrazu ?-? je najväčšia možná hodnota 100, ale na to treba za prvý otáznik dosadiť inú hodnotu ako za druhý (100-0).

Ale na druhé zamyslenie to ani s tým mínusom nie je až také ťažké. Ak je náš výraz tvaru U-V, tak jeho maximum nájdeme ako maximum U mínus minimum V. A naopak, minimum výrazu U-V je zjavne rovné hodnote minimum U mínus maximum V.

A to už je skoro všetko. Zoberieme výraz zo zadania, rekurzívne ho delíme na menšie výrazy a tie vyhodnocujeme – teda pre každý podvýraz zistíme najmenšiu a najväčšiu hodnotu, ktorú môže nadobúdať.

Posledný detail, na ktorý si treba dať pozor: keď máme mínus, budú niektoré medzivýsledky možno záporné. Predstavte si napríklad, že máme výraz U, ktorého minimum je \(-7\) a maximum 3, a výraz V, ktorého minimum je \(-5\) a maximum 1. Aké je teraz maximum výrazu U*V a prečo? A čo minimum?

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.