USACO 2024 February Contest, Bronze, Palindrome Game

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
admin
Dạng bài
Điểm: 1000 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bessie và Elsie đang chơi một trò chơi những viên đá. Chồng đá ban đầu có \(S\) (\(1\leq S \leq 10^{10^5}\)) viên. Hai cô bò thay phiên nhau loại bỏ \(x\) viên đã ra khỏi chồng đá, trong đó \(x\) là một số nguyên palindrome (những số viết xuôi hay ngược cũng giống nhau, ví dụ: 6446, 232). Cho đến khi không còn viên đá nào thì con bò đi lượt đó sẽ thua.

Hai cô bò dự tính chơi tổng cộng \(T\) ván, với những số đá khác nhau. Hãy tìm ra con bò chiến thắng của mỗi ván biết Bessie luôn đi trước.

Input:

  • Dòng đầu tiên chứa \(T\) là số ván chơi của hai cô bò
  • \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên là số lượng đá trong chồng của một ván chơi mới.

Output:

  • Gồm \(T\) dòng, mỗi dòng chứa một kí tự B nếu Bessie thắng ván chơi và E nếu Elsia thắng.

Scoring:

  • Subtask 1: \(S<100\)
  • Subtask 2: \(S < 10^{6}\)
  • Subtask 3: \(S < 10^{9}\)
  • Subtask 4: Không có ràng buộc gì thêm.

Example

Test 1

Input 
3
8
10
12
Output 
B
E
B
Note

  • Trong trường hợp đầu tiên, Bessie có thể loại bỏ tất cả các viên đá trong lượt đầu tiên, vì 8 là một số palindrome, đảm bảo cô ấy thắng.

  • Trong trường hợp thứ hai, 10 không phải là số palindrome, vì vậy Bessie không thể loại bỏ tất cả các viên đá trong lượt đầu tiên. Bất kể Bessie loại bỏ bao nhiêu viên đá trong lượt đầu tiên, Elsie luôn có thể loại bỏ tất cả các viên đá còn lại trong lượt thứ hai để chiến thắng.

  • Trong trường hợp thứ ba, Bessie loại bỏ 2 viên đá, trong lượt sau, dù Elsia có loại bỏ bao nhiêu viên, Bessie vẫn chiến thắng.

Bình luận

  • danh3003 • 6:57 p.m. 28 Tháng 3, 2025 •
    Hãy cố gắng suy nghĩ trước khi xem
    Định lí \(1\)

    Mọi số palindrome đều không chia hết cho \(10\)
    Chứng minh:

    • Mọi số (trừ số \(0\)) đều bắt đầu bằng số khác \(0\) (không tồn tại số \(00248\) mà chỉ có \(248\))
    • Mà trong số palindrome, đầu khác \(0\) \(\Rightarrow\) đuôi khác \(0\) (không có số \(00248\) thì không có số \(84200\))
    Kết luận

    Vì khi một số chia hết cho \(10\) trừ đi số không chia hết cho \(10\) là số palindrome
    \(\Rightarrow\) Sẽ nhận được một số không chia hết cho \(10\)
    Mà \(0\) lại chia hết cho \(10\)
    \(\Rightarrow\) Nếu đến lượt mình mà có số viên đá chia hết cho \(10\) là thua

    Code
    C++
    #inclue <bit/stdc++h>
#def const
#def unsigned
using namespace std
ll t; string n
int main()
{
    sync_with_stdio(FALSE); cin,tie(null); cout,tie(null);
    freopen("", "r");
    freopen("", "w");
    cin >> t;
    while t--:
        cin >> n;
        if n[n.size() - 1] == '0':
            cout << E\n;
        else:
            cout << B\n;
    return 1;
}
    1
    Phản hồi
    • danh3003 • 6:31 p.m. 28 Tháng 3, 2025 •

      Đùa vậy không vui đâu : |
      Tất cả các test được 0 điểm luôn chớ

      0
      Phản hồi