Đây là bài toán interactive.
Bảo đang làm tình báo, trong quá trình do tham Bảo đã thu thập được rất nhiều thông tin có giá trị và gửi về cho trụ sở chính BKCC. Tuy nhiên khi quay trở về báo cáo, Bảo phát hiện rằng tất cả dữ liệu mật báo gửi về đều đã bị lỗi và không thể sử dụng được (khiến cho Bảo bị vụt mất KPI và bị cấp trên khiển trách). Sau quá trình phân tích, Bảo phát hiện rằng do thiết bị truyền tin của mình mà tất cả thông tin mà Bảo gửi về đều có một lỗi chung như sau:
Thông tin mà Bảo gửi về có dạng là một mã nhị phân độ dài $$$n$$$, do thiết bị lỗi mà chính xác một bit trong dãy nhị phân này bị biến đổi, tức là bit $$$0$$$ thành $$$1$$$ và ngược lại.
Do không đủ tiền để sửa chữa thiết bị, Bảo quyết định gửi thêm thông tin để khắc phục vấn đề này. Thông tin mà Bảo gửi thêm là các $$$bit$$$ được đính kèm với mật mã gốc gọi là các $$$xor\_bit$$$. Mỗi $$$xor\_bit$$$ có thể chứa $$$k$$$ thông tin $$$i_1, i_2, \ldots, i_k$$$. Trong đoạn mật mã mới, nếu tại $$$pos$$$ là một $$$xor\_bit$$$ nó sẽ có giá trị bằng với $$$a_{i1} \oplus a_{i2} \oplus \ldots, a_{ik}$$$. Với $$$a_i$$$ là giá trị của bit thứ $$$i$$$ trong đoạn mật mã mới.
Đoạn mật mã mới sẽ là đoạn mật mã cũ nhưng được chèn vào các $$$xor\_bit$$$ mà bạn quy định, mà không làm mất đi thứ tự của đoạn mật mã gốc.
Do thông tin mật báo cần được bảo mật chặt chẽ, thông tin sau khi thêm các $$$xor\_bit$$$ mà Bảo có thể gửi không được vượt quá $$$n + 50$$$. Đau đầu vi không biết phải thiết kế dãy $$$xor\_bit$$$ làm sao, Bảo nhờ tới bạn giúp Bảo chọn ra các $$$xor\_bit$$$, sau đó nhận mã truyền tin của Bảo với các $$$xor\_bit$$$ mà bạn đã quy ước, và xác định bit nào bị lỗi trong quá trình truyền tin (hoặc là bit của mã ban đầu hoặc là $$$xor\_bit$$$)
Dòng đầu tiên là một số nguyên dương $$$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$$$ ($$$1 \le n \le 5000$$$) $$$-$$$ Độ dài mật mã.
Dữ liệu vào bảo đảm tổng $$$n$$$ ở mọi testcase không vượt quá $$$5000$$$.
Sau khi đọc vào input cho mỗi testacse, tiến hành quá trình interact như sau.
Với mỗi testcase, thực hiện những điều dưới đây.
Nếu sử dụng $$$k$$$ $$$xor\_bit$$$, hãy in dưới dạng sau:
Sau đó in ra $$$c$$$ dòng, mỗi dòng có dạng sau:
Nếu $$$k = 0$$$ thì $$$xor\_bit = 0$$$.
Lưu ý, các các thông tin của $$$xor\_bit$$$ không thể là vị trí một $$$xor\_bit$$$ nào đó. Hay $$$i, pos$$$ đều phải thõa $$$i \neq pos$$$ với $$$i$$$ là thông tin của một $$$xor\_bit$$$ và $$$pos$$$ là vị trí của $$$xor\_bit$$$ nào đó trong mật mã mới. Đồng thời, các vị trí $$$pos$$$ của các $$$xor\_bit$$$ cũng phải đôi một khác nhau.
Khi đã in ra đầy đủ các thông tin, hãy đọc vào $$$n + c$$$ giá trị $$$a_1, a_2, \ldots a_{n + c}$$$ ($$$a_i \in \{0, 1\}$$$) $$$-$$$ Đoạn mật mã sau sau khi Bảo gửi cho bạn, trong đó có một bit đã bị sai thông tin so với đoạn mật mã gốc.
Nếu bạn biết được vị trí của bit bị sai, hãy in ra một dòng dưới dạng sau: $$$!$$$ $$$id$$$ ($$$1 \le id \le n + c$$$).
Sau khi thực hiện một một thao tác hãy nhớ in ra ký tự xuống dòng và flush output. Nếu không bạn có thể gặp Idleness limit exceeded hoặc các kết quả khác. Để làm điều này, hãy sử dụng:
Khuyến khích các bạn đọc thêm tài liệu về hướng dẫn dành cho các bài toán interactive.
3 1 5 3
? 2 ? 1 1 3 ? 2 1 3 ! 2 ? 1 ? 1 4 2 3 4 5 6 ! 6 ? 0 ! 3
Lưu ý: Đây không phải là các bước để giải bài toán này, đây là ví dụ về cách tương tác với máy chấm.
Ở ví dụ thứ nhất, nhập vào $$$n = 1$$$, lúc này đưa ra các thông tin sau:
Ở ví dụ thứ hai, nhập vào $$$n = 5$$$, giả sử dãy bit ban đầu là $$$[1, 0, 0, 1, 0]$$$. Sau khi thêm $$$xor\_bit$$$, nó trở thành $$$[\underline{0}, 1, 0, 0, 1, 0]$$$, lúc này qua truyền tin nó trở thành $$$[\underline{0}, 1, 0, 0, 1, 1]$$$. Lúc này bit bị sai nằm ở vị trí $$$6$$$, in ra $$$!$$$ $$$6$$$.
Ở ví dụ thứ ba, nhập vào $$$n = 3$$$, giả sử dãy ban đầu là $$$[0, 0, 1]$$$, bạn bằng cách thần kì nào đó không cần $$$xor\_bit$$$, sau khi qua truyền tin nó trở thành $$$[1, 0, 1]$$$. Lúc này bạn in ra $$$!$$$ $$$1$$$.
Một ngày nọ, một bức ảnh đen trắng của chú mèo dễ thương bị lỗi trong quá trình truyền dẫn và gây ra nhiễu. Bức ảnh được biểu diễn bởi ma trận $$$n \times m$$$, mỗi phần tử là một giá trị nguyên từ $$$0$$$ đến $$$10^9$$$, tương ứng với độ sáng của một pixel ($$$0$$$ là đen hoàn toàn, $$$10^9$$$ là trắng hoàn toàn).
Nhiệm vụ của bạn là giúp ảnh của chú mèo trở lại xinh đẹp như ban đầu bằng cách áp dụng bộ lọc trung vị (median filter) kích thước $$$k \times k$$$. Cụ thể, với mỗi vùng $$$k \times k$$$, bạn sẽ thay thế giá trị của ô trung tâm với trung vị của $$$k^2$$$ pixel trong vùng đó.
Lưu ý, bộ lọc trung vị sẽ được áp dụng đồng thời cho mọi pixel.
Giá trị trung vị của một dãy có số phần tử lẻ là số nằm chính giữa dãy đó sau khi đã sắp xếp theo thứ tự tăng dần. Ví dụ, trung vị của dãy [$$$1, 5, 2, 3, 5$$$] là $$$3$$$.
Các pixel khác (không đủ khung $$$k \times k$$$) sẽ giữ nguyên.
Dòng đầu tiên gồm một số nguyên $$$t$$$ ($$$1 \le t \le 1000$$$) — số testcase, mô tả của mỗi testcase như sau.
Dòng đầu tiên của mỗi testcase gồm ba số nguyên dương $$$n$$$, $$$m$$$ và $$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \le k \le \mathrm{min}(n, m)$$$, $$$k$$$ là một số lẻ) — số hàng, số cột và kích thước cạnh của bộ lọc trung vị.
$$$n$$$ dòng tiếp theo của mỗi testcase gồm $$$m$$$ số nguyên $$$a_{i1}, a_{i2}, \ldots, a_{im}$$$ ($$$0 \le a_{ij} \le 10^9$$$) — độ sáng của mỗi pixel.
Dữ liệu vào bảo đảm tổng $$$n \times m \le 2 \cdot 10^5$$$ trong mọi testcases.
Với mỗi testcase, in ra $$$n$$$ dòng, mỗi dòng có $$$m$$$ ký tự cho biết độ sáng của mỗi pixel sau khi đã lọc trung vị.
33 3 320 30 2540 255 3522 28 264 5 383 3 75 32 4232 16 3 50 2986 6 73 32 773 83 16 42 501 1 110
20 30 25 40 28 35 22 28 26 83 3 75 32 42 32 32 32 42 29 86 16 32 42 77 3 83 16 42 50 10
Ở ví dụ thứ nhất, chỉ có một ô sẽ được áp dụng bộ lọc, nằm tại vị trí ($$$2, 2$$$). Chọn ra các ô trong vùng $$$3 \times 3$$$ ta có: dãy [$$$20, 22, 25, 26, 28, 30, 35, 40, 255$$$], thay thế giá trị của ô ($$$2, 2$$$) từ $$$255$$$ thành $$$28$$$. Các ô còn lại giữ nguyên.
Thầy Tuấn đang có $$$n$$$ tấm gỗ được đánh số từ $$$1$$$ đến $$$n$$$ có chiều rộng là $$$w_i$$$ chiều cao là $$$h_i$$$. Do sợ tốn tiền mua sơn nên thầy giao nhiệm vụ cho em Bảo phải mua giấy dán cho những tấm gỗ này.
Hiện tại Bảo xác định được trong cửa hàng đang có các miếng dán kích thước cụ thể là $$$R \times C$$$, tức là độ rộng là $$$R$$$ và chiều cao là $$$C$$$. Do đã in banner BKAC nên Bảo không thể xoay chiều được miếng dán.
Biết rằng khi dán, mỗi miếng chỉ có thể nằm gọn trên một tấm gỗ, không có trường hợp dán cho hai hoặc nhiều tấm cùng lúc. Ngoài ra miếng dán không được đổi chiều (xoay miếng dán) và các cạnh miếng dán phải song song với các cạnh tấm gỗ.
Hãy cho biết số miếng dán ít nhất cần để các tấm gỗ đều được dán kín.
Dòng đầu tiên gồm duy nhất một số nguyên dương $$$t$$$ ($$$1 \le t \le 1000$$$) $$$-$$$ số lượng testcases, mỗi testcase gồm ba dòng.
Dòng đầu tiên của mỗi testcase gồm ba số nguyên dương $$$n$$$, $$$R$$$ và $$$C$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le R, C \le 10^{9}$$$) $$$-$$$ số lượng các tấm gỗ và kích thước của miếng dán.
Dòng thứ hai của mỗi testcase gồm $$$n$$$ số nguyên $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) $$$-$$$ chiều cao của mỗi tấm gỗ.
Dòng thứ ba của mỗi testcase gồm $$$n$$$ số nguyên $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \le w_i \le 10^9$$$) $$$-$$$ chiều rộng của mỗi tấm gỗ.
Dữ liệu đầu vào bảo đảm tổng $$$n$$$ ở mọi testcase không vượt quá $$$2 \cdot 10^5$$$.
Với mỗi testcase, trên một dòng, in ra số lượng miếng dán cần dùng.
62 20 312 1240 1001 1 1428 11 1010 10 10 10 10 40 50 2055 11 55 55 22 33 33 443 7 834 41 3930 26 96 233476014 8031436306847813 323424606 946007923 753712436 361958625 65047772410767748 684568549 39950281 892753411 349000147 6983000632 92526808 107236580539839331 967415484606720335 187353153
28 8 53 59 16 72
Ở ví dụ thứ nhất, tấm gỗ đầu tiên cần $$$8$$$ miếng dán và tấm gỗ thứ hai cần $$$20$$$ miếng dán. Tổng số miếng dán cần dùng là $$$28$$$.
Ở ví dụ thứ hai, cần $$$8$$$ miếng dán cho duy nhất một tấm gỗ.
Ở ví dụ thứ tư, các tấm gỗ lần lượt cần $$$25$$$, $$$24$$$ và $$$10$$$ miếng dán, tổng số miếng dán cần dùng là $$$59$$$.
Bảo được vinh dự mời vào bàn ăn của các triết gia. Bàn ăn là một chiếc bàn tròn với $$$n$$$ chỗ ngồi và hiện tại đang có $$$m$$$ người (tính luôn cả Bảo) đang ngồi trong bàn ở vị trí $$$a_1, a_2, \ldots a_m$$$ ($$$a_i$$$ khác nhau đôi một).
Hiện tại đang có $$$t$$$ chiếc đũa nằm ở vị trí $$$b_1, b_2, \ldots, b_t$$$ ($$$b_i$$$ khác nhau đôi một). Biết rằng một người trong bàn chỉ có thể ăn nếu họ lấy được một đôi đũa. Hãy cho biết liệu tất cả mọi người đều có thể ăn cùng lúc hay không.
Người ngồi ở chỗ ngồi $$$i$$$ ($$$1 \lt i \lt n$$$) sẽ có thể sử dụng chiếc đũa ở vị trí thứ $$$i - 1$$$, $$$i$$$ và $$$i + 1$$$. Người ngồi ở chỗ ngồi $$$n$$$ sẽ có thể sử dụng chiếc đũa ở vị trí $$$n - 1$$$, $$$n$$$ và $$$1$$$. Người ngồi ở chỗ ngồi $$$1$$$ sẽ có thể sử dụng chiếc đũa ở vị trí $$$n$$$, $$$1$$$ và $$$2$$$. Một chiếc đũa chỉ có thể được sử dụng bởi một người.
Dòng đầu tiên là một số nguyên dương $$$t$$$ ($$$1 \le t \le 500$$$) $$$-$$$ số testcase, mô tả của mỗi testcase như sau.
Dòng đầu tiên của mỗi testcase là ba số nguyên dương $$$n$$$, $$$m$$$ và $$$t$$$ ($$$3 \le m, t \le n \le 100$$$) $$$-$$$ số chỗ ngồi trong bàn, số người ăn và số chiếc đũa.
Dòng thứ hai của mỗi testcase là $$$m$$$ số nguyên dương $$$a_1, a_2, \ldots a_m$$$ ($$$1 \le a_i \le n$$$, $$$a_i$$$ khác nhau đôi một) $$$-$$$ vị trí ngồi của mỗi người.
Dòng thứ ba của mỗi testcase là $$$t$$$ số nguyên dương $$$b_1, b_2, \ldots b_t$$$ ($$$1 \le b_i \le n$$$, $$$b_i$$$ khác nhau đôi một) $$$-$$$ vị trí của các chiếc đũa.
Với mỗi testcase, trên một dòng, in ra YES hoặc NO tương ứng với việc tất cả mọi người có thể cùng ăn hay không.
410 3 72 7 109 3 8 1 7 2 104 4 41 2 3 41 2 3 48 4 82 4 6 71 2 3 4 5 6 7 88 3 62 5 81 3 4 5 7 8
YES NO YES YES
Ở ví dụ thứ nhất, người thứ $$$1$$$ ngồi ở vị trí $$$2$$$ và sử dụng chiếc đũa tại $$$2$$$ và $$$3$$$. Người thứ $$$2$$$ ngồi ở vị trí $$$7$$$ và sử dụng chiếc đũa tại $$$7$$$ và $$$8$$$. Người thứ $$$3$$$ ngồi ở vị trí $$$10$$$ và sử dụng chiếc đũa tại $$$10$$$ và $$$1$$$. Tất cả mọi người đều có thể dùng bữa.
Ở ví dụ thứ hai, người thứ $$$1$$$ ngồi ở vị trí $$$1$$$ và sử dụng chiếc đũa tại $$$1$$$ và $$$2$$$, người thứ $$$3$$$ sử dụng chiếc đũa tại $$$3$$$ và $$$4$$$. Người thứ $$$2$$$ và $$$4$$$ không thể dùng bữa.
Cho một dãy số nguyên $$$a$$$ gồm $$$n$$$ phần tử. Một đoạn con (subarray) là một dãy liên tiếp không rỗng các phần tử của mảng, và đoạn con được gọi là tốt nếu trong nó có chính xác k giá trị phân biệt.
Nhiệm vụ của bạn là đếm xem có bao nhiêu đoạn con tốt của mảng được cho.
Dòng đầu tiên chứa một số nguyên $$$t$$$ ($$$1 \leq t \leq 10^{4}$$$) — số lượng truy vấn. Với mỗi truy vấn:
Dữ liệu vào bảo đảm tổng $$$n$$$ trong mọi testcase không vượt quá $$$2 \cdot 10^5$$$.
Đối với mỗi truy vấn, in ra một dòng duy nhất — số đoạn con chứa chính xác $$$k$$$ giá trị phân biệt.
31 1103 13 1 816 18 1 5 8 8 7 4 9 7 10 10 7 5 8 5 5
1 3 19
Nhà Chung có một khu vườn vô cùng tuyệt đẹp. Ở đó, Chung trồng $$$n$$$ cây anh đào tạo thành một vòng tròn. Chung đánh số các cây từ $$$1$$$ đến $$$n$$$. Chung đánh giá cây thứ $$$i$$$ có độ "đẹp" là $$$h_i$$$.
Chung đứng ở trung tâm của vườn hoa và muốn ngắm nhìn hàng cây anh đào của mình. Chung muốn ngắm các cây anh đào của mình. Chung có một số quy tắc rất kì lạ như sau:
Hãy giúp Chung tìm cách cách ngắm các cây để đạt được tổng độ "đẹp" lớn nhất.
Dòng đầu tiên chứa một số nguyên dương $$$t$$$ ($$$1 \le t \le 10^4$$$)— số testcases.
Mỗi testcase được mô tả như sau:
Dữ liệu đảm bảo tổng $$$n$$$ trong tất cả các testcases không vượt quá $$$2 \times 10^5$$$.
Với mỗi testcase, in ra một số nguyên dương duy nhất — Tổng độ "đẹp" lớn nhất có thể đạt được.
153 5 4 2 32 1 3 1 1
17
Ở ví dụ mẫu, quá trình quay của Chung là: $$$2 \rightarrow 1 \rightarrow 4 \rightarrow 3 \rightarrow 5.$$$
Chung rất lười ra đề nhưng vì bị chích điện tâm huyết với BKCC#2, Chung quyết định ra một bài toán rất dễ như sau:
Với hai số nguyên dương $$$T$$$, Chung định nghĩa dãy $$$a$$$ vô hạn phần tử, đánh số từ $$$0$$$, theo nguyên tắc sau:
Mỗi bộ testcase, Chung cho bạn hai số nguyên dương $$$T, n$$$ và bạn được yêu cầu tính giá trị của $$$a_n$$$ với T được cho, chia lấy dư cho $$$10^9 + 7$$$.
Dòng đầu tiên chứa số nguyên dương $$$t$$$ ($$$t \le 10^4$$$) — số testcase.
$$$t$$$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $$$T, n$$$ ($$$2 \le T \le 10^9, 2 \le n \le 10^6$$$) — Dữ liệu của bài toán.
Dữ liệu bài toán đảm bảo rằng tổng $$$n$$$ trong mọi testcase không vượt quá $$$10^6$$$.
Mỗi testcase in ra một số nguyên dương — đáp án của bài toán.
15 6
125
Với $$$T = 5$$$, dãy số $$$a$$$ như sau: $$$5, 5, 5, 5, 25, 25, 125$$$.
Chung có 1 bàn cờ kích thước $$$n \times n$$$. Trên bàn cờ đó, Chung muốn đặt $$$k$$$ quân cờ. Con cờ thứ $$$i$$$ đặt ở ô ($$$r_i,c_i$$$). Chung có thể đặt 2 loại quân cờ: Xe hoặc Tượng.
Chung thắc mắc rằng, có bao nhiêu cách đặt quân cờ sao cho sau khi đặt, không quân cờ nào có thể bị ăn bởi quân cờ khác.
Dòng đầu tiên chứa một số nguyên dương $$$t$$$ — số testcase.
Mỗi bộ test được mô tả như sau:
Dữ liệu đầu vào đảm bảo vị trí $$$k$$$ quân cờ đôi một phân biệt.
Tổng $$$k$$$ trong tất cả các testcase không vượt quá $$$10^6$$$.
Với mỗi testcase, hãy in ra số cách đặt quân cờ thỏa mãn yêu cầu bài toán chia lấy dư cho $$$10^9 + 7$$$.
210 31 32 410 1010 51 15 37 59 210 10
2 2
Ở ví dụ 1, có 2 cách đặt quân cờ vào các ô thứ nhất, hai, ba như sau: Xe, Xe, Xe hoặc Xe, Xe, Tượng.
Ở ví dụ 2, có 2 cách là: Xe, Xe, Xe, Xe, Xe hoặc Xe, Xe, Xe, Tượng, Xe.
Trong một tựa game do Bảo làm ra, bản đồ game là một lưới gồm $$$n$$$ cột, với cột thứ $$$i$$$ chỉ tồn tại các ô từ tọa độ $$$(1, i), (2, i), \ldots, (a_i, i)$$$. Biết rằng ô ($$$i, j$$$) ở hàng thứ $$$i$$$ tính từ trên xuống dưới và cột thứ $$$j$$$ tính từ trái sang phải.
Giả sử nhân vật của bạn đang ở trong bản đồ game, và ở ô ($$$i, j$$$). Bảo có thể thực hiện các thao tác sau:
Dòng đầu tiên gồm một số nguyên dương $$$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 dương duy nhất $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) $$$-$$$ số cột của lưới.
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^9$$$) $$$-$$$ độ cao của mỗi cột.
Dữ liệu vào bảo đảm tổng $$$n$$$ ở mọi testcases không vượt quá $$$2 \cdot 10^5$$$.
Với mỗi testcase, trên một dòng, in ra kết quả của bài toán.
233 2 152 5 4 1 3
4 30