fork(2) download
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6. int n; cin >> n; //количество зерен
  7. int m; cin >> m; //часть, которую можно съесть за ход
  8. int result[n - m + 1]; //массив значений
  9. for(int i = 0; i < n - m + 1; i++) //очистка массива от мусора
  10. result[i] = 0;
  11. result[0] = 1; //в позиции n = m взять одно зерно и выиграть
  12. result[1] = -1; //из позиции n = m + 1 выиграть нельзя
  13. int take_to_win = 0; //расстояние до ближайшей выигрышной позиции
  14. for(size_t step = m + 2; step < n + 1; step++) //заполнение массива result[]
  15. {
  16. bool good = false; //есть ли возможность перейти на выигрышную позицию из данной
  17. //проверка всех позиций, в которые можно попасть за ход
  18. for(int i = step - m; i >= ((step - step / m) - m) && !good; i--)
  19. {
  20. if(result[i] == -1){ //если выигрышная позиция достижима
  21. good = true; //уведомить об этом программу
  22. take_to_win = n - m - i; //зафиксировать расстояние до позиции
  23. }
  24. }
  25. if(good) result[step - m] = 1; //если возможно, пометить позицию как выгрышную
  26. else result[step - m] = -1; //иначе пометить как прогрышную
  27. }
  28. for(int i = 0; i < n - m + 1; i++) //очистка массива от мусора
  29. cout << i + m << ":\t" << result[i] << endl;
  30. if(result[n - m] == 1) //вывести на экран оптимальное количество зерен на первом шаге
  31. cout << take_to_win << endl;
  32. else //или указать, что позиция проигрышная
  33. cout << -1 << endl;
  34. return 0;
  35. }
Success #stdin #stdout 0s 3464KB
stdin
2 3
stdout
-1