USACO 2021 - Tháng 2 - Hạng Vàng

Bessie và Elsie chơi một trò chơi với \(N\) đống đá (\(1\le N\le10^5\)), trong đó đống thứ \(i\) có \(a_i\) viên với mọi \(1\le i\le N\) (\(1\le a_i\le10^6\)). Hai cô bò luân phiên lượt chơi và Bessie đi trước.

Đầu tiên, Bessie chọn một số nguyên dương \(s_1\) và lấy \(s_1\) viên khỏi một đống có ít nhất \(s_1\) viên. Sau đó, Elsie chọn một số nguyên dương \(s_2\) sao cho \(s_2\) chia hết cho \(s_1\), rồi lấy \(s_2\) viên khỏi một đống có ít nhất \(s_2\) viên. Tiếp theo, Bessie chọn số nguyên dương \(s_3\) sao cho \(s_3\) chia hết cho \(s_2\) và lấy \(s_3\) viên khỏi một đống có ít nhất \(s_3\) viên, và cứ thế tiếp tục.

Nói chung, số đá \(s_i\) được lấy ở lượt \(i\) phải là ước của \(s_{i+1}\). Người đầu tiên không thể lấy đá trong lượt của mình sẽ thua.

Hãy tính số cách Bessie có thể lấy đá trong lượt đầu để bảo đảm chiến thắng, nghĩa là tồn tại một chiến lược giúp Bessie thắng bất kể Elsie lựa chọn thế nào. Hai cách được coi là khác nhau nếu lấy số viên đá khác nhau hoặc lấy từ các đống khác nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa \(N\) số nguyên \(a_1,\ldots,a_N\), cách nhau bởi dấu cách.

Dữ liệu ra

In số cách Bessie có thể lấy đá trong lượt đầu để bảo đảm chiến thắng. Kết quả có thể cần kiểu số nguyên 64 bit, chẳng hạn long long trong C/C++.

Phân nhóm

• Các test 3-5 thỏa mãn \(N=2\).
• Các test 6-10 thỏa mãn \(N,a_i\le100\).
• Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

1
7

4

6
3 2 3 2 3 1

8

Nguồn

USACO 2021 February Contest, Gold - Stone Game: https://usaco.org/index.php?page=viewproblem2&cpid=1113

Tác giả: Benjamin Qi.

Sau khi chán nghệ thuật hai chiều thông thường và bực mình vì người khác sao chép tác phẩm, nghệ sĩ bò vĩ đại Picowso quyết định chuyển sang phong cách một chiều tối giản hơn. Bức tranh mới nhất của cô được mô tả bằng một mảng màu một chiều độ dài \(N\) (\(1\le N\le300\)), trong đó mỗi màu là một số nguyên thuộc đoạn \(1\ldots N\).

Moonet, đối thủ của Picowso, đã tìm ra cách sao chép cả những bức tranh một chiều này! Trong mỗi nét cọ, Moonet tô một đoạn liên tiếp bằng một màu duy nhất, chờ khô rồi tô một đoạn khác, và cứ thế tiếp tục. Moonet có thể dùng mỗi màu trong \(N\) màu bao nhiêu lần tùy ý, kể cả không lần nào.

Hãy tính số nét cọ ít nhất để Moonet sao chép bức tranh một chiều mới nhất của Picowso.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng tiếp theo chứa \(N\) số nguyên thuộc đoạn \(1\ldots N\), biểu thị màu của từng ô trong bức tranh một chiều.

Dữ liệu ra

In số nét cọ ít nhất cần để sao chép bức tranh.

Phân nhóm

• Trong các test 2-4, bức tranh chỉ có màu \(1\) và \(2\).
• Trong các test 5-10, màu của ô thứ \(i\) thuộc đoạn

với mọi \(1\le i\le N\).

• Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

10
1 2 3 4 1 4 3 2 1 6

6

0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 0
1 2 2 2 2 2 2 2 1 0
1 2 3 3 3 3 3 2 1 0
1 2 3 4 4 4 3 2 1 0
1 2 3 4 1 4 3 2 1 0
1 2 3 4 1 4 3 2 1 6

Nguồn

USACO 2021 February Contest, Gold - Modern Art 3: https://usaco.org/index.php?page=viewproblem2&cpid=1114

Tác giả: Brian Dean và Benjamin Qi.

Cho một bảng có kích thước vô hạn, các hàng và các cột đánh số từ 0.

Ô ở hàng \(x\) cột \(y\) được gọi là ô \((x, y)\) và có giá trị là \(\begin{cases}1 & \text{nếu}\ \forall k: \lfloor\frac{x}{3^k}\rfloor \text{mod}\ 2 = \lfloor\frac{y}{3^k}\rfloor \text{mod}\ 2\\ 0 & \text{nếu ngược lại}\end{cases}\)

Sau đây là \(9 \times 9\) ô đầu tiên của bảng:

        x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101

Có \(Q\) truy vấn có dạng \((d_i, x_i, y_i)\). Với mỗi truy vấn thứ \(i\), bạn cần trả lời tổng các số nằm trên đường chéo \((x_i, y_i), (x_i+1, y_i+1), (x_i+2, y_i+2), \dots, (x_i+d_i, y_i+d_i)\).

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(Q\) \((1 \leq Q \leq 10^4)\)
• \(Q\) dòng tiếp theo, dòng thứ \(i\) lần lượt chứa ba số \(d_i, x_i, y_i\) \((0 \leq x_i, y_i, d_i \leq 10^{18})\)

Định dạng đầu ra

• In ra \(Q\) dòng, dòng thứ \(i\) là đáp án của truy vấn thứ \(i\).

Điểm số

• Test 1 là test ví dụ
• Test 2 thỏa mãn \(d_i \leq 100\) với mỗi truy vấn.
• Test 3-6 thỏa mãn \(x_i+d_i = 3^{30}-1; y=0\) với mỗi truy vấn.
• Test 7-12 không có điều kiện nào khác.

Ví dụ

8
10 0 0
10 0 1
9 0 2
8 0 2
0 1 7
1 1 7
2 1 7
1000000000000000000 1000000000000000000 1000000000000000000

11
0
4
3
1
2
2
1000000000000000001