Advertisement
AlexGo11

Untitled

Jan 6th, 2020
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.40 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7.  
  8. int a, b, c;
  9. cin >> a >> b >> c;
  10. vector<int> sg_a(a + 1); //Отдельно посчитаем для каждого из a, b, c функцию Гранди
  11. vector<int> sg_b(b + 1);
  12. vector<int> sg_c(c + 1);
  13. sg_a[1] = sg_b[1] = sg_c[1] = 0;
  14. vector<int> cur(a + 1); //аналог Mex
  15. cur[0] = 1;
  16. for (int i = 2; i <= a; i++) {
  17. if(i % 2 == 1)
  18. cur[sg_a[i / 2]]--;
  19. for (int j = 0; j <= a; j++) {
  20. if (!cur[j]) { //Находим Mex для текущего значения
  21. sg_a[i] = j; //вписываем для текущего состояния это значение
  22. break;
  23. }
  24. }
  25. cur[sg_a[i]]++; // говорим, что текузее состояния уже в мексе есть
  26. }
  27. cur.clear(); cur.resize(b + 1); //аналогично для каждого из б и ц
  28. cur[0] = 1;
  29. for (int i = 2; i <= b; i++) {
  30. if (i % 2 == 1)
  31. cur[sg_b[i / 2]]--;
  32. for (int j = 0; j <= b; j++) {
  33. if (!cur[j]) {
  34. sg_b[i] = j;
  35. break;
  36. }
  37. }
  38. cur[sg_b[i]]++;
  39. }
  40. cur.clear(); cur.resize(c + 1);
  41. cur[0] = 1;
  42. for (int i = 2; i <= c; i++) {
  43. if (i % 2 == 1)
  44. cur[sg_c[i / 2]]--;
  45. for (int j = 0; j <= c; j++) {
  46. if (!cur[j]) {
  47. sg_c[i] = j;
  48. break;
  49. }
  50. }
  51. cur[sg_c[i]]++;
  52. }
  53. int f = sg_a[a] ^ sg_b[b] ^ sg_c[c]; // смотрим, если ксор от а б и ц равен 0, то игра проигрышная
  54. if (f == 0) cout << "NO\n";
  55. else { // иначе выигрышная
  56. cout << "YES\n"; // начинаем искать, какой ход не проигрышный
  57. for (int i = (a + 1) / 2; i < a; i++) { // отдельно смотрим измерение по а, б и ц
  58. if ((sg_a[i] ^ sg_b[b] ^ sg_c[c]) == 0) { // если ход для измерения а ведёт в ксор равный 0, то это выигрышный ход
  59. cout << i << " " << b << " " << c << endl;
  60. return 0;
  61. }
  62. }
  63. for (int i = (b + 1) / 2; i < b; i++) { // аналогично для каждого из б и ц
  64. if ((sg_a[a] ^ sg_b[i] ^ sg_c[c]) == 0) {
  65. cout << a << " " << i << " " << c << endl;
  66. return 0;
  67. }
  68. }
  69. for (int i = (c + 1) / 2; i < c; i++) {
  70. if ((sg_a[a] ^ sg_b[b] ^ sg_c[i]) == 0) {
  71. cout << a << " " << b << " " << i << endl;
  72. return 0;
  73. }
  74. }
  75. }
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement