Tin học trẻ C1 - Thái Bình 2024

Sanji định nghĩa một số đẹp bậc năm là số có từ hai chữ số trở lên và chỉ gồm đúng \(1\) chữ số khác chữ số \(5\). Ví dụ về các số đẹp bậc năm: \(15, 25, 35, 45,50, 51, 52, 53, 54, 56, 57, 58, 59, 65, 75, 85, 95, 155, 255, \ldots\) Viết các số tạo thành dãy số đẹp bậc năm tăng dần. Hãy tìm số nhỏ thứ \(K\) của dãy số đó.

Input

• Một số tự nhiên \(K\) (\(1 \leq K \leq 1000\)).

Output

• Gồm một dòng là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(K \leq 150\).
• Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

5

50

11

57

Vào ngày nghỉ, Đạt và Châu cùng nhau chơi tựa game Liên Minh Huyền Thoại. Để dạy Châu cách ra đòn đánh cuối cùng vào lính, Đạt đã tạo ra \(n\) con lính, con lính thứ \(i\) sẽ bị hạ gục khi nhận ít nhất \(a_{i}\) đòn đánh. Cả hai người đều sử dụng kĩ năng đánh thường, mỗi đòn đánh thường đều sẽ gây \(1\) sát thương cho lính. Hai người đánh các con lính lần lượt theo thứ tự từ \(1\) đến \(n\) cùng với nhau. Khi hạ gục con lính trước, hai người mới cùng chuyển sang đánh con lính sau. Nhân vật của Đạt có thể thực hiện \(x\) đòn đánh mỗi giây (nghĩa là sau mỗi \(\frac{1}{x}\) giây, nhân vật của Đạt sẽ thực hiện một đòn đánh), còn nhân vật của Châu có thể thực hiện \(y\) đòn đánh mỗi giây (nghĩa là sau mỗi \(\frac{1}{y}\) giây, nhân vật của Châu sẽ thực hiện một đòn đánh). Hỏi với mỗi con lính, người tiêu diệt con lính đó sẽ là ai, biết rằng người thực hiện đòn đánh cuối cùng sẽ được tính là người tiêu diệt con lính đó, nếu như hai người cùng thực hiện đòn đánh cuối cùng lên con lính cùng lúc thì sẽ tính là cả hai cùng tiêu diệt con lính đó.

Input

• Dòng thứ nhất chứa ba số nguyên \(n, x, y\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq x, y \leq 10^{6})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\).

Output

• Với mỗi con lính bị tiêu diệt, in ra trên một dòng. Nếu con lính bị hạ gục bởi Đạt, in ra một dòng \texttt{D}, nếu con lính bị hạ gục bởi Châu, in ra một dòng \texttt{C}, nếu con lính bị hạ gục bởi cả hai người, in ra một dòng \texttt{Both}.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(x = 1, y = 2\).
• Subtask \(2\) (\(30\%\) số điểm): \(x = 1\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

4 1 2
5 6 10 12

Both
Both
C
Both

Thuận có một thiết bị đặc biệt và một tập hợp \(S\). Thiết bị của Thuận có thể thực hiện các phép toán sau đây:

• Thêm một số nguyên không âm \(x\) vào một tập hợp \(S\).
• Xóa một số nguyên không âm \(x\) khỏi tập hợp \(S\) (nếu nó tồn tại trong tập hợp \(S\)).
• Đếm số lượng các số \(y\) trong tập hợp \(S\) sao cho \(x \oplus y < k\), với \(x\) là một số nguyên không âm cho trước và \(k\) là một hằng số không âm cho trước. Ở đây, \(\oplus\) đại diện cho phép toán XOR bitwise.

Ban đầu, tập hợp \(S\) là rỗng. Bạn cần xử lý \(q\) truy vấn trên thiết bị này.

Input

• Dòng đầu tiên chứa số nguyên \(q\) \((1 \leq q \leq 10^{5})\) - số lượng truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng thể hiện \(1\) truy vấn thuộc một trong ba dạng sau:
  • \(+\) \(x\): thêm \(x\) vào tập hợp \(S\) \((0 \leq x \leq 10^{8})\).
  • \(-\) \(x\): xóa \(x\) khỏi tập hợp \(S\) \((0 \leq x \leq 10^{8})\).
  • \(?\) \(x\) \(k\): đếm số lượng các số \(y\) trong \(S\) sao cho \(x \oplus y < k\) \((0 \leq x, k \leq 10^{8})\).

Output

• Đối với truy vấn dạng \texttt{?} \(x\) \(k\), in ra trên một dòng số lượng các số \(y\) thỏa mãn điều kiện đã cho.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(q \leq 1000\).
• Subtask \(2\) (\(20\%\) số điểm): \(x\) có dạng \(2^{k}\).
• Subtask \(3\) (\(60\%\) số điểm): Không ràng buộc gì thêm.

Example

5

+ 3
+ 4
? 6 3
- 4
? 6 3

1
0

 Tập $S = \{3 , 4\}$ sau $2$ truy vấn đầu tiên. Ở truy vấn $3$ cho $x = 6$ và $k = 3$, chỉ có một phần tử $y$ thỏa mãn đó là $y = 4$ (vì $x \oplus y = 2 < 3$) nên kết quả in ra là $1$.

Bạn được cho một cây có \(n\) đỉnh và \(n-1\) cạnh và một mảng \(a\) gồm \(n\) phần tử. Ban đầu giá trị của đỉnh thứ \(i\) bằng \(a_i\). Có hai loại truy vấn:

• "1 u v p": Gọi \(s_1, s_2, ..., s_k\) là các đỉnh trên đường đi từ \(u\) đến \(v\). Sau đó ta thực hiện thao tác \(\oplus\) với tất cả các giá trị của các đỉnh đó, nói cách khác ta gán cho \(a_{s_1} = a_{s_1} \oplus p, a_{s_2} = a_{s_2} \oplus p,..., a_{s_k} = a_{s,k} \oplus p\) (\(1 \le u,v \le n, 0 \le p \le 2^{10}-1\)).
• "2 u v": Gọi \(s_1, s_2, ..., s_k\) là các đỉnh trên đường đi từ \(u\) đến \(v\). Sau đó cần đưa ra tổng trọng số đỉnh của các nút trên đường đi từ \(u\) đến \(v\), nói cách khác cần đưa ra tổng \(S = a_{s_1} + a_{s_2} + ... + a_{s_k}\) (\(1 \le u,v \le n\)).

Yêu cầu: Với mỗi truy vấn loại \(2\), in ra kết quả của số \(S\) trên một dòng.

Biểu thức \(x \oplus y\) biểu diễn phép toán tử XOR của hai số \(x\) và \(y\).

Input

• Dòng thứ nhất chứa một số nguyên dương \(\phi\) - số thứ tự của subtask chứa test đó.
• Dòng thứ hai chứa một số nguyên dương \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ ba chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) (\(0 \le a_i \le 2^{10}-1\)).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) - mô tả một cạnh của cây.
• Dòng tiếp theo chứa một số nguyên dương \(q\) (\(q \le 10^5\)) - số lượng truy vấn.
• \(q\) dòng cuối cùng, mỗi dòng chứa một truy vấn như mô tả ở trên.

Output

• Với mỗi truy vấn loại \(2\), in ra kết quả truy vấn đó trên một dòng.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n,q \le 1000\).
• Subtask \(2\) (\(10\%\) số điểm): cây thoả mãn điều kiện với hai cạnh \((u,v)\) bất kì \((u < v)\) thì \(u = \lfloor \frac{v}{2} \rfloor\).
• Subtask \(3\) (\(15\%\) số điểm): mọi truy vấn update (truy vấn loại 1) đều có \(u = v\).
• Subtask \(4\) (\(20\%\) số điểm): cây thoả mãn điều kiện đỉnh \(u\) được nối với đỉnh \(u+1\) với mọi \(1 \le u \le n-1\).
• Subtask \(5\) (\(20\%\) số điểm): cây thoả mãn điều kiện mỗi đỉnh không có nhiều hơn \(2\) cạnh.
• Subtask \(6\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

1
6
4 3 2 5 3 4
1 2
1 3
2 4
2 5
3 6
2
1 2 4 2
2 1 2

5