Mùa nhập học sắp đến, GDSC và BKAC đang gấp rút tuyển thành viên! Vì vậy họ đang thu thập những chữ cái để tạo ra bảng hiệu nhằm thu hút mọi người tham gia câu lạc bộ của mình.
Hai bên sẽ đi tìm chữ cái mình muốn trong một xâu $$$s_1s_2\ldots s_n$$$ có độ dài $$$n$$$. Biết rằng, đôi bên sẽ kiểm tra các ký tự theo thứ tự lần lượt từ $$$1$$$ đến $$$n$$$. Nếu bên nào thành công lấy được đủ các ký tự để làm bảng hiệu trước, bên đó sẽ thắng. Lưu ý, nếu cả hai bên đều tìm thấy ký tự mình muốn thì cả hai đều sẽ được ký tự đó.
GDSC mong muốn thu thập các ký tự G, D, S, C.
BKAC mong muốn thu thập các ký tự B, K, A, C.
Vì cả GDSC và BKAC đều không muốn mất đi những thành viên tiềm năng, hãy cho biết bên nào sẽ là bên hoàn thành bảng hiệu trước hoặc hai bên đều hoàn thành cùng lúc.
Dữ liệu vào luôn bảo đảm một trong hai bên sẽ hoàn thành được bảng hiệu.
Dòng đầu tiên gồm một số nguyên dương duy nhất $$$t$$$ ($$$1 \le t \le 100$$$) $$$-$$$ số testcases.
Dòng đầu tiên của mỗi testcase gồm một số nguyên dương $$$n$$$ ($$$4 \le n \le 100$$$) $$$-$$$ độ dài của xâu.
Dòng thứ hai của mỗi testcase là một xâu độ dài $$$n$$$ gồm các ký tự in hoa trong bảng chữ cái alphabet $$$s_1s_2\ldots s_n$$$.
Với mỗi testcase, trên một dòng, in ra GDSC hoặc BKAC tùy thuộc vào đội nào hoàn thành bảng hiệu trước. Nếu hai bên hoàn thành cùng lúc thì in ra DRAW.
34CKAB4GSDC10BAKAZPGDSC
BKAC GDSC DRAW
Bảo sở hữu một cái máy bán kẹo, nguyên lý hoạt động của máy này là kẹo sẽ được trữ bên trong một đường ống, khi nhấn nút để mua kẹo, thì kẹo ở cuối đường ống sẽ được nhả ra.
Trong một ngày Bảo có $$$q$$$ sự kiện diễn ra bao gồm hai loại sau:
- $$$1$$$ $$$x$$$ $$$a$$$: Bảo nạp $$$x$$$ viên kẹo loại $$$a$$$, có giá $$$a$$$/viên vào đầu đường ống của máy bán kẹo
- $$$2$$$ $$$c$$$: Khách hàng mua $$$c$$$ viên kẹo.
Hãy cho biết mỗi lần mua kẹo, khách hàng sẽ phải trả bao nhiêu tiền.
Dữ liệu vào luôn bảo đảm có đủ kẹo cho mỗi lần khách mua và sẽ có ít nhất một lần khách mua kẹo.
Dòng đầu tiên gồm một số nguyên duy nhất $$$t$$$ ($$$1 \le t \le 10^4$$$) $$$-$$$ số testcases
Dòng đầu tiên của mỗi testcase gồm một số nguyên duy nhất $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) $$$-$$$ số sự kiện trong ngày.
$$$q$$$ dòng tiếp theo của mỗi testcase thuộc một trong hai dạng sau:
- $$$1$$$ $$$x$$$ $$$a$$$ ($$$1 \le x, a \le 10^9$$$) $$$-$$$ Bảo nạp $$$x$$$ viên kẹo loại $$$a$$$ vào đầu đường ống của máy bán kẹo
- $$$2$$$ $$$c$$$ ($$$1 \le c \le 10^9$$$) $$$-$$$ Khách hàng mua $$$c$$$ viên kẹo.
Dữ liệu vào bảo đảm tổng $$$q$$$ ở mọi testcases không vượt quá $$$2 \cdot 10^5$$$.
Ở mỗi testcase, gọi $$$k$$$ là số sự kiện loại $$$2$$$ $$$c$$$. Trên $$$k$$$ dòng hãy in số tiền cần để mua kẹo.
151 2 32 11 4 52 32 2
3 13 10
Ở ví dụ đầu tiên:
Sau sự kiện thứ nhất, đường ống như sau:
Sau sự kiện thứ hai, số tiền mua kẹo là $$$1 \times 3 = 3$$$. Lúc này đường ống như sau:
Sau sự kiện thứ ba, đường ống như sau:
Sau sự kiện thứ tư, số tiền mua kẹo là $$$1 \times 3 + 2 \times 5 = 13$$$. Lúc này đường ống như sau:
Sau sự kiện thứ năm, số tiền mua kẹo là $$$2 \times 5 = 10$$$. Lúc này đường ống như sau:
Huy được Bảo giao một bài toán sau:
Cho một dãy gồm $$$n$$$ con số $$$a_1, a_2, \ldots, a_n$$$. Gọi $$$P$$$ là kết quả sau khi nhân các con số trong dãy trên lại với nhau. Hãy tìm số chữ số $$$0$$$ ở tận cùng của $$$P$$$.
Huy thấy bài toán trên là quá khó, các bạn hãy giúp Huy.
Biết rằng số chữ số $$$0$$$ tận cùng của $$$x$$$ là số $$$k$$$ ($$$k \ge 0$$$) lớn nhất mà $$$y \times 10^k = x$$$.
Dòng đầu tiên gồm một số nguyên dương $$$t$$$ ($$$1 \le t \le 10^4$$$) $$$-$$$ số testcase.
Dòng đầu tiên của mỗi testcase là một số nguyên $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) $$$-$$$ số phần tử trong dãy.
Dòng thứ hai của mỗi testcase gồm $$$n$$$ số nguyên dương $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) $$$-$$$ các phần tử trong dãy.
Với mỗi testcase, trên một dòng, in ra số chữ số $$$0$$$ tận cùng của $$$P$$$.
354 5 7 1 621000 1000011
1 7 0
Ở ví dụ đầu tiên, $$$840 = 4 \times 5 \times 6 \times 7 \times 1$$$, có một chữ số $$$0$$$ tận cùng.
Ở ví dụ thứ hai, $$$1000000 = 1000 \times 10000$$$, có bảy chữ số $$$0$$$ tận cùng.
Ở ví dụ thứ ba, $$$1$$$ không có chữ số $$$0$$$ tận cùng nào.
Bảo đang có một đồ thị vô hướng cần được xử lý. Mục tiêu của Bảo là biến đồ thị trên thành một cây$$$^\dagger$$$ duy nhất.
Vì quá bận Bảo quyết định nhờ bạn giúp xử lí đồ thị trên. Bạn được phép thực hiện các thao tác sau:
- Xóa cạnh: Loại bỏ một cạnh bất kỳ khỏi đồ thị.
- Thêm cạnh: Thêm một cạnh vô hướng mới giữa hai đỉnh bất kỳ.
Cây$$$^\dagger$$$: Là một đồ thị đơn giản (simple graph), vô hướng, không chu trình và liên thông.
Dòng đầu tiên gồm một số nguyên dương $$$t$$$ ($$$1 \le t \le 1000$$$) $$$-$$$ số testcases.
Dòng đầu tiên của mỗi testcase gồm hai số nguyên $$$n$$$ và $$$m$$$ ($$$0 \le m \le 5 \cdot 10^5$$$, $$$1 \le n \le 2 \cdot 10^5$$$) $$$-$$$ số đỉnh và cạnh của đồ thị.
$$$m$$$ dòng tiếp theo của mỗi testcase gồm hai số nguyên dương $$$u_i$$$ và $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) $$$-$$$ biểu diễn cạnh thứ $$$i$$$ ($$$1 \le i \le m$$$) của đồ thị.
Dữ liệu vào bảo đảm tổng $$$n$$$ ở mọi testcases không vượt quá $$$2 \cdot 10^5$$$ và tổng $$$m$$$ ở mọi testcases không vượt quá $$$5 \cdot 10^5$$$.
Với mỗi testcase in ra như sau:
Dòng đầu tiên là một số nguyên $$$k$$$ thể hiện số cạnh bị xóa.
$$$k$$$ dòng tiếp theo in ra một số nguyên dương $$$i$$$ ($$$1 \le i \le m$$$) $$$-$$$ cạnh được chọn để xóa.
Dòng thứ tiếp theo in ra một số nguyên dương $$$t$$$ thể hiện số cạnh được thêm.
$$$t$$$ dòng tiếp theo in ra hai số nguyên dương $$$u$$$ và $$$v$$$ ($$$1 \le u, v \le n$$$) $$$-$$$ biểu diễn cạnh thêm.
15 61 11 22 31 34 55 4
3 1 4 6 1 1 4
Tại ví dụ thứ nhất, các thao tác có thể được biểu diễn như sau:
Đồ thị ban đầu. 
Đồ thị sau khi xóa cạnh. 
Đồ thị sau khi thêm cạnh.
Tổ chức Global Data Science Collective (GDSC) vừa phát hiện ra một ma trận dữ liệu có $$$n$$$ hàng và $$$m$$$ cột. Biết rằng ô dữ liệu ở hàng thứ $$$i$$$ từ trên xuống và cột $$$j$$$ từ bên trái sang ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$) có giá trị $$$a_{ij}$$$.
Sau khi nghiên cứu kỹ lưỡng, tổ chức cần chọn ra hai vùng không phủ nhau có diện tích $$$k \times k$$$ để tiến hành đào dữ liệu. Bạn hãy giúp tổ chức tìm ra hai vùng có tổng giá trị lớn nhất.
Dòng đầu tiên gồm một số nguyên dương $$$t$$$ ($$$1 \le t \le 500$$$) $$$-$$$ số testcases.
Dòng đầu tiên ở mỗi testcase gồm ba số nguyên dương $$$n$$$, $$$m$$$ và $$$k$$$ ($$$2 \le n, m \le 10^3$$$, $$$1 \le k \le \lfloor\frac{\mathrm{min}(n, m)}{2}\rfloor$$$) $$$-$$$ số hàng, số cột và độ dài cạnh của vùng cần tìm.
$$$n$$$ dòng tiếp theo ở mỗi testcase gồm $$$m$$$ số nguyên dương $$$a_{i1}, a_{i2}, \ldots, a_{im}$$$ ($$$0 \le a_{ij} \le 10^9$$$) $$$-$$$ giá trị của mỗi ô dữ liệu.
Dữ liệu vào bảo đảm tổng $$$n$$$ không vượt quá $$$10^3$$$ và tổng $$$m$$$ không vượt quá $$$10^3$$$.
Với mỗi test case, trên một dòng, in ra tổng giá trị lớn nhất thu được từ hai vùng đã chọn.
24 4 25 2 1 64 3 2 51 2 5 36 9 2 12 2 11 11 1
33 2
Sử dụng ($$$x_1, y_1, x_2, y_2$$$) đại diện cho một vùng (diện tích $$$k \times k$$$) với ($$$x_1, y_1$$$) đại diện cho tọa độ của ô trái trên, và ($$$x_2, y_2$$$) đại diện cho tọa độ của ô phải dưới.
Ở ví dụ thứ nhất, hai vùng ($$$3, 1, 4, 2$$$) và ($$$2, 3, 3, 4$$$) đã được chọn với tổng các ô nằm trên chúng là $$$33$$$.
Ở ví dụ thứ hai, bất kì vùng nào cũng cho giá trị là $$$1$$$, ta chọn hai trong số chúng từ đó có đáp án là $$$2$$$.
Lễ hội trường đã bắt đầu với những trò chơi hấp dẫn. Lễ hội có $$$n$$$ trò chơi được đánh số từ $$$1$$$ đến $$$n$$$, nếu tham gia trò chơi thứ $$$i$$$, Bảo sẽ trả $$$b_i$$$ đồng lệ phí và trò chơi có $$$p_i$$$ tỉ lệ chiến thắng. Nếu thắng, Bảo được thưởng $$$a_i$$$ đồng và nhận lại $$$b_i$$$ đồng (tổng số tiền nhận được là $$$a_i + b_i$$$ đồng).
Với mỗi trò chơi lần lượt từ $$$1$$$ đến $$$n$$$, tại trò chơi thứ $$$i$$$, Bảo có hai sự lựa chọn:
- Tham gia trò chơi thứ $$$i$$$.
- Bỏ qua trò chơi thứ $$$i$$$.
Vì Bảo là học sinh ưu tú, nhà trường đã cho Bảo được hưởng đặc quyền như sau. Cứ sau mỗi $$$k$$$ lần tham gia các trò chơi ($$$k$$$ là số do nhà trường chỉ định), tiền thưởng sẽ được nhân đôi ở chính xác một trò chơi sau đó.
Tức là, nếu đủ $$$k$$$ lần tham gia ở trò chơi thứ $$$i$$$, thì đặc quyền chỉ có hiệu lực ở trò chơi thứ $$$i + 1$$$, số lần tham gia trò chơi cũng sẽ được tính lại từ đầu ở lượt này. Lưu ý: Nếu bạn tham gia chơi ở lượt chơi được nhân đôi, thì lượt chơi đó vẫn sẽ được tính là một lần tham gia trò chơi.
Bảo rất háo hức trước lễ hội trường sắp tới, hãy tính giá trị kỳ vọng tối đa là số tiền mà Bảo nhận được khi lễ hội trường kết thúc.
Biết rằng tỉ lệ chiến thắng $$$p_i$$$ là độc lập cho trò chơi thứ $$$i$$$ và các sự lựa chọn có thể được quyết định bằng cách quan sát kết quả của các trò chơi trước đó.
Dòng đầu tiên gồm hai số nguyên $$$n$$$ và $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le min(n, 10)$$$) — số trò chơi và số $$$k$$$ mà nhà trường chỉ định.
Dòng tiếp theo gồm $$$n$$$ số thực $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i \le 1$$$) — tỉ lệ thắng của các trò chơi.
Dòng tiếp theo gồm $$$n$$$ số nguyên $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^4$$$) — số tiền nhận được khi chiến thắng.
Dòng tiếp theo gồm $$$n$$$ số nguyên $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 10^4$$$) — lệ phí tham gia trò chơi.
In ra một số thực duy nhất là giá trị kỳ vọng tối đa khi lễ hội trường kết thúc, đáp án của bạn được cho là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án của ban tổ chức không quá $$$10^{-6}$$$.
2 20.3 0.610 32 5
1.6
3 20.3 0.6 0.510 3 22 5 1
2.9
5 20.5 0.2 0.7 0.9 0.13 3 2 8 23 2 10 4 5
12.4
Ở ví dụ thứ nhất, Bảo tham gia trò chơi đầu tiên và bỏ qua trò chơi thứ hai.
Ở ví dụ thứ hai, Bảo tham gia tất cả trò chơi.
Ở ví dụ thứ ba, tham gia trò chơi thứ nhất, thứ ba và thứ tư.
Chung có hai con mèo, mèo A và mèo B (nên nghĩ tên khác :>). Mỗi ngày trong $$$m$$$ ngày, Chung cho hai con mèo ăn cá. Trong ngày thứ $$$i$$$, Chung có $$$c_i$$$ con cá để chia cho hai con mèo ăn và hai con mèo phải ăn hết số cá này.
Tuy nhiên, hai con mèo này khá dị đặc biệt. Con mèo A ngày càng ăn nhiều, còn mèo B lại ngày càng ăn ít. Nghĩa là $$$\forall i \in [2,m], a_i \ge a_{i - 1}$$$ và $$$b_{i} \le b_{i - 1}$$$ với $$$a_i,b_i$$$ lần lượt là số con cá mà mèo A,B ăn trong ngày thứ $$$i$$$.
Chung muốn cho hai con mèo ăn sao cho số cá chênh lệch ($$$|a_i - b_i|$$$) tối đa trong $$$m$$$ ngày trên là nhỏ nhất. Hoặc cũng có thể không có cách cho hai con mèo ăn thỏa mãn các điều kiện trên. Khi đó, hãy in ra $$$-1$$$. Hãy giúp Chung nhé.
Dòng đầu tiên chứa số nguyên dương $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — Số ngày Chung cho mèo ăn.
Dòng tiếp theo chứa $$$m$$$ số nguyên dương $$$a_1,a_2,\cdots,a_m$$$ ($$$1 \le a_i \le 10^9$$$)— Số cá Chung cho 2 con mèo ăn mỗi ngày.
In ra một số nguyên duy nhất — số cá chệnh lệch tối đa nhỏ nhất đạt được, hoặc $$$-1$$$.
54 7 4 3 2
-1
55 4 6 5 4
3
Ở ví dụ 2, ta có thể cho mèo ăn như sau
- Ngày 1: Mèo A ăn $$$1$$$ con cá, mèo B ăn $$$4$$$ con cá.
- Ngày 1: Mèo A ăn $$$1$$$ con cá, mèo B ăn $$$3$$$ con cá.
- Ngày 1: Mèo A ăn $$$3$$$ con cá, mèo B ăn $$$3$$$ con cá.
- Ngày 1: Mèo A ăn $$$3$$$ con cá, mèo B ăn $$$2$$$ con cá.
- Ngày 1: Mèo A ăn $$$3$$$ con cá, mèo B ăn $$$1$$$ con cá.
Vậy chênh lệch số cá 2 con mèo ăn lần lượt là $$$3,2,0,1,2$$$. Chênh lệch lớn nhất trong các ngày là $$$3$$$.
Chung có dãy $$$a$$$ gồm $$$n$$$ số nhị phân, được đánh số bắt đầu từ 1 ($$$a_1,a_2,\cdots,a_n$$$). Ban đầu toàn bộ dãy $$$a$$$ bằng 0.
Hãy xử lý các truy vấn sau:
- $$$1 \; i$$$ ($$$1 \le 1 \le n$$$): Flip giá trị phần tử $$$a_i$$$.
- $$$2 \; l \; r$$$ $$$ $$$ ($$$1 \le l \le r \le n$$$): Đếm số cách chia đoạn $$$[l,r]$$$ thành các đoạn con liên tiếp sao cho mỗi phần tử $$$a_i$$$ ($$$i \in [l,r]$$$) thuộc đúng 1 đoạn và mỗi đoạn chứa ít nhất một số 1, chia lấy dư cho $$$998244353$$$.
Dòng đầu tiên chứa số nguyên dương $$$t$$$ ($$$t \le 100$$$)— số testcase.
Mỗi testcase được mô tả như sau:
- Dòng đầu tiên chứa số nguyên dương $$$n,q$$$ ($$$1 \le n,q \le 5 \cdot 10^5$$$) — Độ dài dãy nhị phân.
- $$$q$$$ dòng tiếp theo chứa truy vấn được mô tả như trên.
Dữ liệu đầu vào đảm bảo tổng $$$n$$$ và tổng $$$q$$$ trong tất cả các testcase nhỏ hơn hoặc bằng $$$5 \cdot 10^5$$$;
Với mỗi truy vấn 2, in ra đáp án tìm được.
15 61 11 31 42 1 41 12 1 5
6 2
Một cách chia là việc chia đoạn $$$[l,r]$$$ thành các đoạn $$$[l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]$$$ ($$$1 \le k$$$) sao cho $$$l_1=l,r_k=r$$$ và $$$l_i=r_{i-1}+1 \; \forall i \in [2,k]$$$.
Giải thích ví dụ:
- Sau truy vấn 1: dãy $$$a$$$ trở thành $$$10000$$$.
- Sau truy vấn 2: dãy $$$a$$$ trở thành $$$10100$$$.
- Sau truy vấn 3: dãy $$$a$$$ trở thành $$$10110$$$.
- Ở truy vấn 4, có 6 cách chia đoạn $$$[1,4]$$$ như sau:
- $$$[1,3],[4,4]$$$
- $$$[1,2],[3,3],[4,4]$$$
- $$$[1,1],[2,3],[4,4]$$$
- $$$[1,4]$$$
- $$$[1,2],[3,4]$$$
- $$$[1,1],[2,4]$$$
- Sau truy vấn 5: dãy $$$a$$$ trở thành $$$00110$$$.
- Ở truy vấn 6, có 2 cách chia đoạn $$$[1,5]$$$ như sau:
- $$$[1,3],[2,5]$$$
- $$$[1,5]$$$