Igra sa novcicima (zadatak za posao)

[bmaxa]

Igraju Pat i Matt igru novcica. Novcica ima do 1000.
Ulaz su ukupni brojevi novcica na osnovu kojih treba da se odredi da li Pat ili Matt pobedjuje.
Broj novcica koji se moze uzeti u jednom potezu je uvek kvadrat broja, pobednik je onaj
koji napravi zadnji potez tj broj novcica ostane 0.
Prvi uvek igra Patt.
Izlaz je niz pobednika tako da uvek igraju najbolje poteze.

 

[cronnin]

Компликовано. Задржи свих хиљаду динара

 

[bmaxa]

Компликовано. Задржи свих хиљаду динара

Ma to je juce dobio jedan moj drug da uradi za sat i po da udje kao frilenser u neku americku firmu.
Trazio je dva i po soma evra, kad ono uvalili mu kosku

 

[tab503]

posto se kaze da ima do 1000 znaci moze da ima i dva
uzme pet dva novcica i spusti i ima nula i pobedio je

 

[bmaxa]

posto se kaze da ima do 1000 znaci moze da ima i dva
uzme pet dva novcica i spusti i ima nula i pobedio je

Ulaz je broj novcica. Dakle moze biti bilo sta do 1000
Lako bi bilo da je uvek 1 ili dva u prvom slucaju pobedjuje prvi u drugom drugi
Mozda ova firma ubaci isti zadatak nekom

 

[cronnin]

Колико ја видим треба да пази на један од могућих 31 бројева који завршавају игру. Коме стигне сума од:

1 - добија јер је квадрат
2 - губи (може да узме само 1, што противнику оставља добитничку 1)
3 - добија (може да узме само 1, што противнику оставља губитничку 2)
4 - добија јер је квадрат
5 - губи (може да узме или 1 или 4, што суму противнику своди на добитничке 4 или 1)
6 - добија (може да узме или 1 или 4; што суму противнику своди на губитничке 5 или 2)
7 - губи (може да узме или 1 или 4; што суму противнику своди на добитничке 6 или 3)
8 - добија ( може да узме или 1 или 4; што суму противнику своди на 7 или 4, где у варијанти 7 противник губи)
9 - добија јер је квадрат
10 - губи ( може да узме 1-4-9; што суму противнику своди на добитничке 9-6-1)
11 - добија ( може да узме 1-4-9; што суму противнику своди на губитничке 10-7-2)
12 - губи( мора да узме 1-4-9; што суму противнику своди на добитничке 11-8-3)


И тако до хиљаду. Ако сад уме да направи петљу да му изгенерише ово...

 

[bmaxa]

Колико ја видим треба да пази на један од могућих 31 бројева који завршавају игру. Коме стигне сума од:

1 - добија јер је квадрат
2 - губи (може да узме само 1, што противнику оставља добитничку 1)
3 - добија (може да узме само 1, што противнику оставља губитничку 2)
4 - добија јер је квадрат
5 - губи (може да узме или 1 или 4, што суму противнику своди на добитничке 4 или 1)
6 - добија (може да узме или 1 или 4; што суму противнику своди на губитничке 5 или 2)
7 - губи (може да узме или 1 или 4; што суму противнику своди на добитничке 6 или 3)
8 - добија ( може да узме или 1 или 4; што суму противнику своди на 7 или 4, где у варијанти 7 противник губи)
9 - добија јер је квадрат
10 - губи ( може да узме 1-4-9; што суму противнику своди на добитничке 9-6-1)
11 - добија ( може да узме 1-4-9; што суму противнику своди на губитничке 10-7-2)
12 - губи( мора да узме 1-4-9; што суму противнику своди на добитничке 11-8-3)


И тако до хиљаду. Ако сад уме да направи петљу да му изгенерише ово...

Mozda to sto je kvadrat koji se uzima povlaci neku matematicku pravilnost ili najjednostavnije napraviti stablo poteza pa backtracking, ne znam.
Deluje mi stablo kao resenje.

 

[cronnin]

Ја бих то овако, само три колоне:

да ли добија ?​	тренутна сума​	треба да игра​
0​	0​	нема шта да игра изгубио је​
1​	1​	алгоритам => 1​
0​	2​	1​
1​	3​	1​
1​	4​	4​
0​	5​	1​
1​	6​	1​
0​	7​	1​

Алгоритам:

Од тренутне суме одузимај квадрате природних бројева све док није <0.
За разлику бројева коју добијеш (то је оно што ће противник добити као потез) провераваш прву колону.

• ако је противнику тамо 1, проверавај даље са већим квадратима
• ако је противнику тамо 0, играч добија; у текућем реду упиши 1 у прву колону, а тај број који треба да игра у трећу колону
• ако си стигао до суме која је мања од нуле, значи да не постоји варијанта у којој сигурно добијаш, ираш опортунистички најмањи број 1 у нади да ће противник да се пређе у неком од потеза; у текућем реду упиши 0 у прву колону, а 1 у трећу колону