Блог пользователя aloo08051999

Please help me with how to approach these question?
Автор aloo08051999, история, 3 года назад, По-английски

Problem is- given two piles of stones having a,b stones respectively(a,b <200000). in each move one player takes out 3*x stones from one and add x to other. Both player play optimally.Player who cant make a move loses. Who wins ?

This is problem from newton coding challenge i am unable to come up with any optimised approach/expression.I was thinking to find intermediate states and find if any is forcefully losing for player 2 then player 1 wins but constraint are high.Please help by providing some hints on how to solve similar pattern problem.

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I found the answer by brute force for all a, b <= 100 and got the pattern. And then in the end got very simple result:

if (abs(l1 - l2) <= 2) {
  if (l1 == l2) {
    cout << "Solo\n";
  } else if (l1 % 2 == 1 && l2 % 2 == 1) {
    cout << "Tono\n";
  } else {
    cout << "Solo\n";
  }
} else {
  cout << "Tono\n";
}
→ Ответить