trang chủ / đề bài / icpc22_mn_a

Trò chơi Síp

Đề bài

Mô tả

Cường và Mai đang chơi một trò chơi với các con số, có nguồn gốc từ Síp, một quốc gia nhỏ ở châu Âu. Trò chơi bắt đầu với một cặp số nguyên dương (x,y). Hai người lần lượt biến đổi cặp số này, Cường đi trước. Ở mỗi lượt, người chơi có thể thực hiện một trong các nước đi sau:

  • Nếu x chẵn: (x,y)→(x2,y+x2);
  • Nếu y chẵn: (x,y)→(x+y2,y2).

Trò chơi có 3 kết cục:

  • Nếu trò chơi đến một trạng thái mà cả x và y đều lẻ, người đến lượt không có nước đi hợp lệ và thua cuộc.
  • Nếu trò chơi đến một trạng thái đã từng xuất hiện trước đó, trò chơi kết thúc với kết quả hòa.

Giả sử cả Cường và Mai đều chơi tối ưu. Cho n, hãy đếm số trạng thái bắt đầu (x,y) với 1≤x,y≤n mà trò chơi kết thúc theo mỗi kết cục trong 3 kết cục.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên n (1≤n≤109).

Dữ liệu ra

In ra 3 số nguyên trên 3 dòng:

  • Số trạng thái bắt đầu mà Cường thắng;
  • Số trạng thái bắt đầu dẫn đến kết quả hòa;
  • Số trạng thái bắt đầu mà Mai thắng.

Ràng buộc

  • 1≤n≤109

Ví dụ

Input Output Giải thích
2 1
2
1
Có 4 trạng thái bắt đầu. (1,1): Cường không có nước đi, Mai thắng. (2,1): Cường chỉ có một nước đi đến (1,2), rồi Mai chỉ có một nước đi đến (2,1), trò chơi hòa. (1,2): tương tự trạng thái trước. (2,2): Cường có hai nước đi đến (1,3) hoặc (3,1), cả hai trường hợp Mai đều không còn nước đi, Cường thắng.
3 1
4
4
Ví dụ bổ sung (không có trong đề gốc). Cường chỉ thắng ở (2,2). Hòa ở (1,2), (2,1), (2,3), (3,2). Mai thắng ở (1,1), (1,3), (3,1), (3,3).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0