Hogy kéne megoldani ezt a feladatot? (C# de mindegy a nyelv végülis)

" Tudok megoldást, nem segítek" 4 szavazat.

Annak a 4 embernek a válaszát én is várnám. :)

Mivel fogalmunk sincs, hogy mi az optimális, de abból kiindulva, hogy az N lehet négyzetszám is, így biztos van olyan helyzet, hogy józsika nyerhet.

[link]

> Matematikai képletre kell megoldás

> Ha meg van a formula akkor, a formulát használod. Ha az N szám megfelel a formulára akkor return false

FYI: nem minden algoritmus fejezhető ki formulában / képletben.

Ez klasszikus dp gyakorló feladat, csak most épp Józsikával meg golyókkal megfogalmazva.

[link]

Ja, most nézem, hogy C# van a kérdésben, én C++-t írtam, de kb. annyi a különbség, hogy vector<bool> helyett bool[]-t használnék.

Nyilván van top-down dp megoldás is, az valszeg lassabb a rekurzivitásból adódóan, de nem próbáltam ki.

Istencsászár? Ilyen szintű feladatot hamarabb oldanak meg emberek Div 2-es versenyeken, minthogy elolvasnám mi a kérdés.

Elkezded felépíteni alulról a dp táblát (ezért bottom-up dp).

Mivel csak négyzetszámokat lehet elvenni, ezért értelemszerűen azokat kell megpróbálni. Ha adott játékos el tud venni egy négyzetszámot úgy, hogy a maradék vereséghez vezet (!dp[i-j*j], akkor az nyerő ág. Így mész fel n-ig, mivel arra vagyunk kíváncsiak, hogy az n kiindulópontból nyerhetünk-e, de ehhez ismerni kell az alatta lévő részfák eredményét.

#49: köszi, ez egy korrekt magyarázat

sorry a toxic reakciómért