Đếm số cách xếp $2n$ viên bi lên bảng vuông kích thước $n \times n$ sao cho mỗi hàng và mỗi cột có chính xác hai viên bi.

2

1

3

6

Cho dãy $a$ gồm $n$ phần tử $a_1, a_2, ..., a_n$, hãy in ra tất cả cách điền $n-1$ dấu $+$ và $-$ vào giữa các phần tử để tạo thành $1$ biểu thức sao cho biểu thức nhận được có kết quả là $m$.

6 7
6 5 8 3 1 2    

2
+-+-+
-+--+

4 5
1 2 3 2   

0

Cho một biểu thức chỉ gồm các số hạng và các phép tính cộng và trừ. Tính giá trị biểu thức được cho.

1+2-3+4-5

-1

Xét một hình thang có hai đáy $AB$ và $CD$ song song với nhau. Biết rằng $AB = a, BC = b, CD = c, DA = d$. Nhiệm vụ của bạn là với mỗi bộ số $(a, b, c, d)$, kiểm tra xem có tồn tại hình thang như vậy hay không.

2
4 2 2 2
1 2 3 4

YES
NO

Một cặp phân số $\frac{a}{b}$ và $\frac{c}{d}$ được gọi là kỳ diệu khi $\frac{a}{b} + \frac{c}{d} = \frac{a + c}{b + d}$.

Bạn được cho một dãy các phân số, đếm xem có bao nhiêu cặp phân số kỳ diệu trong các phân số này.

3
1 -1 -4
2 2 4

2

giaminh2211 gặp phải bài toán sau: Cho số $n$ đếm số bộ ba số nguyên dương đẹp ($a$, $b$, $c$) sao cho $n \ge a \ge b \ge c$, $a$, $b$, $c$ tạo thành 3 cạnh của tam giác vuông và $a + b = c^2$. giaminh2211 đã giải được và thấy bài toán có vẻ hay nên chia sẻ với bạn.

3
3
19
100

0
2
6

Ôi không, bạn đã làm mất streak Duolingo của bạn 💀

Duolingo là một trong những nền tảng học các ngôn ngữ nước ngoài miễn phí và lớn nhất. Mặc dù học tiếng Anh với chú cú xanh Duolingo rất vui, nhưng điều đáng sợ nhất mà đã ám ảnh mondellbit009 suốt đời:

Nếu bạn làm mất streak Duolingo của bạn, ngay lập tức, bạn sẽ bị đưa tới một nơi không xác định để chuộc lại lỗi lầm khi để mất streak 💀. Đến giờ, những người bị mất tích do làm mất streak vấn chưa được tìm thấy 💀💀.

mondellbit009 cũng là một người dùng duolingo lâu năm, nhưng mà cậu ấy vẫn sợ về cái vụ streak ấy, nên là cậu có một phương pháp dàn trận như TFT: Xếp ngày, xếp lịch, chuẩn bị vật phẩm giúp mondellbit009 tránh khỏi việc cậu bị bắt do ngủ quên mà không làm Duolingo.

Phương pháp xếp lịch của mondellbit009 như sau:

• Đâu tiên, cậu ta sẽ cho $n$ ngày làm, và mua $k$ vật phẩm.
• Sau đó cậu ta sẽ xếp vào ngày thứ $i$ ($1 \le i \le n$) là làm hay không làm. Nếu cậu xếp ngày đó là $1$ thì cậu sẽ làm vào ngày đó, còn nếu cậu xếp ngày đó là $0$ thì ngược lại.
• Lưu ý: Cứ với $1$ vật phẩm chỉ được dùng $1$ lần cho cho mỗi ngày không làm.

Biết là có khả năng dàn trận vjp pro ($6$ trận ranked thì $9$ trận Top $8$), nhưng khổ cái là cậu ta được có $5$ điểm toán 💀. Nên là bạn hãy là một teammate tốt để giúp cậu ấy khỏi bị con cú chết tiệt đấy bắt nhé.

4
5 2
1 0 1 1 0
6 6
0 0 0 0 0 0
7 4
1 0 0 0 1 0 0
5 0
1 1 1 1 1 

YES
YES
NO
YES

Cho hai dãy $a_1, a_2, ..., a_n$ và $b_1, b_2, ..., b_m$. Kiểm tra xem tích hai dãy đó có bằng nhau hay không.

Bạn phải xử lý nhiều bộ dữ liệu như vậy.

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

YES
NO

Xét một bảng hình chữ nhật gồm $n \times m$ điểm, xếp thành $n$ hàng $m$ cột. Các cột được đánh số từ $1$ đến $m$ từ trái sang phải, các hàng được đánh số từ $1$ đến $n$ từ dưới lên trên. Điểm ở hàng $i$ cột $j$ ký hiệu là $(i, j)$. Hai điểm liên tiếp trên một hàng hoặc một cột cách nhau $1$.

Vẽ một đường tròn có tâm là điểm $(u, v)$ và bán kính $r$. Xóa toàn bộ các điểm nằm trong hoặc trên đường tròn.

In ra bảng sau khi thực hiện thao tác xóa.

6 7 1 1 5

.######
....###
.....##
.....##
.....##
......#

Một dãy đẹp là một dãy $x_1, x_2, ..., x_k$ mà $gcd(x_i, x_{i + 1}) > 1$ với mọi $i$.

Bạn được cho một dãy $a[1], a[2], ..., a[n]$. Tìm một dãy $l_1 < l_2 < ... < l_k$ sao cho $k$ lớn nhất có thể và $a[l_1], a[l_2], ..., a[l_k]$ là một dãy đẹp.

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

2
4

Cho hai số nguyên $k,p$, tìm các số nguyên dương $n$ thỏa mãn:

• $k<n\leq 10^p$
• $2^n$ chia hết cho $n$
• $2^n-1$ chia hết cho $n-1$
• $2^n-2$ chia hết cho $n-2$
• ...
• $2^n-k$ chia hết cho $n-k$

2 0

7
1
2
4
8
16
32
64

Bạn được cho một dãy $a_1, a_2, ..., a_n$. Xét $b$ là dãy gồm các trung vị của các đoạn con liên tiếp của $a$, hãy tính trung vị của $b$.

Nhắc lại:

• Trung vị của một dãy $x_1, x_2, ..., x_n$ đã được sắp xếp là $x_{[\frac{n + 1}{2}]}$, với $[i]$ là số nguyên lớn nhất không lớn hơn $i$.
• Một đoạn con liên tiếp của một dãy $y_1, y_2, ..., y_n$ là một dãy $a_l, a_{l + 1}, ..., a_r$ với $1 \le l \le r \le n$.

4
1 2 3 4

2

4 
1 1 2 2

1

4 
4 3 2 1

2

Một dãy số $a_0,a_1,...,a_k$ được gọi là biểu diễn hệ số $b$ của số nguyên không âm $x$ nếu $0\leq a_i<b$ với mọi $0\leq i\leq k$, $a_k>0$ và $a_0\times b^0 + a_1\times b^1 + a_2\times b^2 + ... + a_k\times b^k = x$.

Cho một dãy số $a_0,a_1,...,a_n$ là biểu diễn hệ số $b_1$ của số $x$. Hãy tìm dãy số là biểu diễn hệ số $b_2$ của $x$.

5 10 2
7 2 7 9 1

1 1 1 1 0 0 0 0 1 0 1 1 0 0 1

Cho một số nguyên dương $n$. Đếm số lượng cặp số nguyên dương $(a, b)$ sao cho $1 \le a < b \le n$ và $a \times b$ là số chính phương.

10

4

Cho dãy số $A$ có $n$ phần tử, phần tử thứ $i$ có giá trị là $a_i$.

Bạn có thể thực hiện hai thao tác sau:

• Chọn $1$ vị trí $i$ $(1\le i\le n)$ và chuyển $a_i$ về đầu dãy và dồn các phần tử phía sau lên trước. (i.e. xoay vòng dãy từ $a_1$ đến $a_i$ theo chiều hướng về phía cuối dãy, sau thao tác dãy sẽ trở thành $a_i, a_1, a_2, ..., a_{i - 1}, a_{i + 1}, a_{i + 2}, ..., a_n$)
• Chọn $1$ vị trí $i$ $(1\le i\le n)$ và chuyển $a_i$ về cuối dãy và dồn các phần tử phía sau lên trước. (i.e. xoay vòng dãy từ $a_i$ đến $a_n$ theo chiều hướng về phía đầu dãy, sau thao tác dãy sẽ trở thành $a_1, a_2, ..., a_{i - 1}, a_{i + 1}, a_{i + 2}, ..., a_n, a_i$)

Yêu cầu: Tìm số thao tác nhỏ nhất tạo ra một dãy mà $1\le i\le n-1$ thì $a_i \ge a_{i + 1}$ (i.e. dãy thu được là dãy không tăng).

4 
2 6 1 4

2

4 
3 1 2 4

2

4 
1 1 2 2

2

giaminh2211 give up on CP chán quá nên ra bài mời mấy đứa bạn vừa bắt đầu học CP làm. Cho số $n$, có thể phân tích $n$ ra làm tổng 3 số nguyên dương chẵn được không. Nếu có in ra $1$, nếu không in ra $0$

3
9
10
11

0
1
0

huyhau6a2 hiện đang có một chương trình tên là binary.cpp. Trong code của cậu có thực hiện các bước như sau:

• Bước 1: Nhập vào chương trình một xâu nhị phân $s$ (xâu nhị phân là xâu chỉ bao gồm các ký tự 0 và 1). Thực hiện bước 2.
• Bước 2: Kiểm tra xem trong xâu $s$ có xuất hiện đoạn ký tự 10 hay không, nếu có thì thực hiện bước 3, còn không thì kết thúc chương trình.
• Bước 3: Thay đồng loạt tất cả các đoạn ký tự 10 xuất hiện trong xâu $s$ thành 01. Quay lại bước 2.

Ví dụ: Với xâu $s=$1100 thì chương trình sẽ thực hiện như sau:

• Kiểm tra thấy có đoạn ký tự 10 xuất hiện, chuyển qua bước 3.
• Thay tất cả đoạn ký tự 10 thành 01. Xâu $s$ trở thành 1010. Quay lại bước 2.
• Kiểm tra thấy có đoạn ký tự 10 xuất hiện, chuyển qua bước 3.
• Thay tất cả đoạn ký tự 10 thành 01. Xâu $s$ trở thành 0101. Quay lại bước 2.
• Kiểm tra thấy có đoạn ký tự 10 xuất hiện, chuyển qua bước 3.
• Thay tất cả đoạn ký tự 10 thành 01. Xâu $s$ trở thành 0011. Quay lại bước 2.
• Kiểm tra thấy không có đoạn ký tự 10 xuất hiện, kết thúc chương trình.
  Vậy với xâu $s=$1010 thì chương trình sẽ thực hiện bước 3 hai lần.

Với chương trình mà huyhau6a2 viết, rõ ràng nó sẽ kết thúc sau một vài lần thực hiện bước 3, tức là nó không chạy vô hạn. Nhiệm vụ của bạn là xác định xem với xâu $s$ mà huyhau6a2 chuẩn bị nhập vào cần thực hiện bước 3 bao nhiêu lần.

Input

• Dòng đầu gồm một số nguyên dương $t$ là số testcase $(1\le t\le 10^5)$.
• Sau đó là $t$ dòng, mỗi dòng gồm một xâu $s$ là xâu mà huyhau6a2 sẽ nhập vào chương trình $(1\le |s|\le 2\times 10^5)$.
• Dữ liệu đảm bảo tổng độ dài của các xâu $s$ trong tất cả testcase không quá $2\times 10^5$.

Output

• Với mỗi testcase, in ra duy nhất một giá trị là số lần thực hiện bước 3 trong một dòng.

Sample

Sample Input 1

4
1100
00011
1011001
1011001110

Sample Output 1

3
0
4
6

Notes

• Testcase thứ nhất đã được giải thích ở phần statement.
• Trong testcase thứ ba, xâu $s$ sau các thao tác như sau: 1011001$\rightarrow$0110101$\rightarrow$0101011$\rightarrow$0010111$\rightarrow$0001111.
• Trong testcase thứ tư, xâu $s$ sau các thao tác như sau: 1011001110$\rightarrow$0110101101$\rightarrow$0101011011$\rightarrow$0010110111$\rightarrow$0001101111$\rightarrow$0001011111$\rightarrow$0000111111

This is a geometry problem since I love geometry so much.

Cho $n$ điểm phân biệt trên mặt phẳng tọa độ Descartes, điểm thứ $i$ có tọa độ là $(x_i, y_i)$. Với mỗi cặp điểm, vẽ một đường tròn có đường kính là đoạn thẳng nối cặp điểm đó lại với nhau. Khi đó, ta sẽ có tổng cộng $\frac{n\times (n-1)}{2}$ đường tròn khác nhau.

Nhiệm vụ của bạn là với mỗi điểm trong $n$ điểm trên, bạn hãy xác định số lượng đường tròn mà nó nằm trên với điều kiện nó không trùng với đầu mút của đường kính của những đường tròn đó. Chúc bạn may mắn nhé!

4
3 1
10 1
5 2
3 6

1 0 1 0

4
1 1
1 2
2 1
2 2

1 1 1 1

Một năm nữa lại trôi qua và một năm mới đang đến gần với chúng ta. Đối với flo, năm vừa qua là một năm không có gì là may mắn, khá thăng trầm nhưng cũng để lại trong tâm trí cậu nhiều kỉ niệm khó nhớ. Một trong số đó có lẽ là những ngày ôn tập chuẩn bị cho kì thi cuối kì I của flo diễn ra trong $2$ tuần. Trong thời gian đó, cậu đã phải chịu đựng nhiều đau đớn và trải qua nhiều khó khăn. Nhưng rồi kì thi ấy cũng trôi qua, kết quả mà flo đạt được đã vượt xa mong đợi của cậu. Vì thế mà flo vô cùng vui bởi kết quả cho những đau đớn mà cậu trải qua lại vô cùng xứng đáng.

Năm mới đã đến và kết quả thi cử của flo rất tốt nên cậu đã được mẹ cậu thưởng $n$ hộp kẹo với vô vàng loại kẹo khác nhau. Những hộp kẹo này còn có cho mình $1$ độ ngon nhất định khi hộp thứ $i$ có độ ngon là $a_i$. Tuy nhiên nếu ăn hết bây giờ thì sẽ quá lãng phí nên flo quyết định ăn $n$ hộp kẹo này trong những ngày tới. Mỗi ngày, cậu sẽ chọn $1$ số nguyên dương $m$ bất kỳ và ăn $m$ viên kẹo đầu tiên sao cho độ phong phú của $m$ hộp kẹo đó giao động từ $l$ đến $r$. Đối với flo, độ phong phú của một dãy hộp kẹo là số lượng độ ngon khác nhau của các hộp kẹo đó. Khi ăn như vậy sẽ giúp cậu có thể cảm nhận được sự hòa quyện của các loại kẹo với nhau, từ đó tạo nên một vị ngon khó cưỡng.

Vì là một con người coi trọng việc tiết kiệm, flo muốn ăn theo cách trên nhưng cậu phải ăn hết kẹo mà không chưa lại hộp kẹo nào. Tuy nhiên do số lượng hộp kẹo mà mẹ của flo tặng cho cậu quá lớn làm cho cậu không biết phải phân chia để ăn như thế nào mới có thể thỏa mãn được cậu. Bạn hãy tính giúp flo nhé.

3 1 2
2 3 2

4

6 2 4
1 2 1 3 2 2

3

Một năm mới sắp đến nên flo quyết định chuẩn bị bài cho Bedan Contest #03 như là một món quà nho nhỏ tới những thành viên của TLEoj. Chỉ còn vài ngày nữa là đã đến ngày diễn ra nhưng flo vẫn chưa có ý tưởng nào. Một hôm, khi đọc sách về toán học thì cậu đã thấy được một vài công thức tính tổng các dãy số liên tiếp phổ biển như sau.

• $\sum_{i = 1}^n i = \frac{n\times (n+1)}{2}$.
• $\sum_{i = 1}^n i^2 = \frac{n\times (n+1)\times (2\times n+1)}{6}$.
• $\sum_{i = 1}^n i^3 = (\frac{n\times (n+1)}{2})^2$.
• $...$

flo nhận ra các công thức trên đều tính tổng dãy số có số mũ là số nguyên. Bỗng cậu thắc mắc rằng có cách nào để tính nhanh $\sum_{i = 1}^n \lfloor \sqrt{i} \rfloor$ hay không. Vì đang bí ý tưởng ra bài cho Bedan Contest #03 nên flo quyết định đưa bài này vào để mời các bạn giải thử. Bạn hãy thử sức với bài này nhé.

Nếu như bạn vẫn không biết $\lfloor n \rfloor$ là gì thì nó là $n$ được làm tròn xuống, như $\lfloor 6.9 \rfloor = 6$.

3
4
6
9

5
9
16