predstavme si, ze nasa postupnost obsahuje nejake cislo vacsie ako 3, povedzme x. Ukazeme, ze to je neefektivne a radsej ho nahradime 2-kami a 3-kami. Rozdelime si to na tri pripady, podla zvysku x po deleni 3:
- ak je x delitelne 3, tak x = 3k. Cize nas sucin S = x*Y = 3*k*Y (Y je sucin tych zvysnych cisel).
Ak namiesto x-iek zoberieme k-krat 3jku (cize sucet sa nezmeni), dostaneme S' = (3^k)*Y.
No a kedze 3*k < 3^k, tak sme prave dostali vacsi sucin.
- ak je x = 3k+1 (cize zvysok 1), nahradime ho 3^(k-1) *2*2. Podobne ako hore ukazes, ze je to lepsie pre hocijake k>0 (a pre k=0 by to znamenalo ze mas v sucine 1, co je uplna volovina, ak sa ho snazis maximalizovat, takze to tam urcite nie je
- podobne pre x = 3k+2, nahradis 3^k * 2.
Takto ukazes, ze v podstate hocijake cislo vacsie ako 3 moze byt nahradene 3-kami a 2-kami, pricom sucet zostane 1000, a sucin zvysis.
Teraz si uz len vsimnes, ze ak tam mas nejaku trojicu 2-iek, tak to ma sucet 2+2+2=6, a s rovnakym suctom mozes zobrat radsej dve 3-ky (co sa ti oplati, lebo 2^3 = 8 < 3^2 =9).
Vysledok: Zober trojek kolko sa da, t.j. 333, a tu zvysnu jednotku prilep k jednej z nich (cize dostanes 4, co je ekvivalent 2*2).
Roleta je špeciálny inkognito mód, ktorým skryješ obsah obrazovky pred samým sebou, alebo inou osobou v tvojej izbe (napr. mama). Roletu odroluješ tak, že na ňu klikneš.
15 komentov
Skus to - ze ak tam mas cislo a, tak jeho rozklad na 3-ky ti da vacsi sucin.
predstavme si, ze nasa postupnost obsahuje nejake cislo vacsie ako 3, povedzme x. Ukazeme, ze to je neefektivne a radsej ho nahradime 2-kami a 3-kami. Rozdelime si to na tri pripady, podla zvysku x po deleni 3:
- ak je x delitelne 3, tak x = 3k. Cize nas sucin S = x*Y = 3*k*Y (Y je sucin tych zvysnych cisel).
Ak namiesto x-iek zoberieme k-krat 3jku (cize sucet sa nezmeni), dostaneme S' = (3^k)*Y.
No a kedze 3*k < 3^k, tak sme prave dostali vacsi sucin.
- ak je x = 3k+1 (cize zvysok 1), nahradime ho 3^(k-1) *2*2. Podobne ako hore ukazes, ze je to lepsie pre hocijake k>0 (a pre k=0 by to znamenalo ze mas v sucine 1, co je uplna volovina, ak sa ho snazis maximalizovat, takze to tam urcite nie je
- podobne pre x = 3k+2, nahradis 3^k * 2.
Takto ukazes, ze v podstate hocijake cislo vacsie ako 3 moze byt nahradene 3-kami a 2-kami, pricom sucet zostane 1000, a sucin zvysis.
Teraz si uz len vsimnes, ze ak tam mas nejaku trojicu 2-iek, tak to ma sucet 2+2+2=6, a s rovnakym suctom mozes zobrat radsej dve 3-ky (co sa ti oplati, lebo 2^3 = 8 < 3^2 =9).
Vysledok: Zober trojek kolko sa da, t.j. 333, a tu zvysnu jednotku prilep k jednej z nich (cize dostanes 4, co je ekvivalent 2*2).
(Prepac, na detailnejsi postup nemam cas )