Nhảy về 0 div 2

Cho một mảng gồm \(N\) phần tử \(A[1],A[2],...,A[N]\) với \(A[i]\in \left\{0,1\right\}\text{ }\forall 1\le i\le N\) và ta có một phép toán sau:

• Chọn \(j(1\le j\le n)\) bất kì và gán \(A[j]=1-A[j]\)

Hỏi ta cần thực hiện ít nhất bao nhiêu phép toán để mảng trên chứa các phần tử \(0,1\) xen kẻ nhau.

Input

• Dòng thứ nhất chứa số nguyên \(T(1\le T\le 100)\)- Thể hiện số lượng testcase.
• Ứng với mỗi testcase, sẽ là một block có dạng như sau:
• Dòng thứ nhất chứa số nguyên \(N(1\le N\le 10000)\)
• Dòng thứ hai chứa \(N\) số nguyên \(A[i](1\le i\le n)\) với \(A[i]\in \left\{0,1\right\}\)

Output

• Ứng với mỗi testcase, in ra kết quả cần tìm tương ứng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1\le N\le 200\)
• Subtask \(2\) (\(80\%\) số điểm): \(1\le N\le 10000\)

Example

3
3
0 0 0
3
0 1 0
3
1 1 1   

1
0
1

Một số nguyên dương \(N\) được gọi là hợp số đơn giản nếu nó có thể viết được dưới dạng: \(N=p_1 \cdot p_2\) với \(p_1,p_2\) đều là các số nguyên tố.

Cho số nguyên dương \(N\). Kiểm tra xem \(N\) có phải là hợp số đơn giản hay không?

Input

• Dòng thứ nhất chứa số nguyên \(T\) (\(1\le T\le 10\)) thể hiện testcase.
• \(T\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(N\) (\(1\le N\le 10^9\)).

Output

• Ứng với mỗi giá trị của \(N\), in ra Yes nếu \(N\) là hợp số đơn giản, ngược lại in ra No.

Scoring

• Subtask 1 (\(20\%\) số điểm): \(N\le 10^3\).
• Subtask 2 (\(20\%\) số điểm): \(N\le 10^6\).
• Subtask 3 (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
4
5

Yes
No

Cặp số \((a,n)\) được gọi là "đẹp đôi" nếu chúng thỏa mãn những điều kiện sau:

• \(a,n\in \mathbb{N}\) và \(a\ge 2,n\ge 2\)

• Tồn tại một dãy số \(\left\{u\right\}\) thỏa mãn:

• \(u_1=p+1;u_i=u_{i-1}+1\) với \(1\le i\le n-1\) và \(p\in \mathbb{P}\)

• \(u_i\notin \mathbb{P}\) với \(1\le i\le n-1\)

• \(u_{n-1}+1 \in \mathbb{P}\)

• Tồn tại chỉ số \(j(1\le j\le n-1)\) thỏa mãn: \(u_j=a\)

(trong đó: \(\mathbb{P}\) là tập hợp các số nguyên tố)

Hay nói cách khác tồn tại dãy \(u\) gồm các số tự nhiên liên tiếp bắt đầu từ \(p + 1\) và kết thúc tại \(p+n-1\) (với \(p\) và \(p+n\) là các số nguyên tố) thỏa mãn \(u\) chỉ chứa hợp số và \(u\) chứa số \(a\)

Yêu cầu: Cho số nguyên dương \(a(a\ge 2)\). Tìm số nguyên dương \(n(n\ge 2)\) thỏa mãn \((a,n)\) là cặp "đẹp đôi". Nếu không tồn tại \(n\) thỏa mãn thì in ra \(0\)

Input

• Input gồm nhiều truy vấn, mỗi truy vấn là một dòng chứa một số nguyên dương \(a(a\ge 2)\)

• Input kết thúc bởi số 0.

Output

• Ứng với mỗi dòng chứa số nguyên dương \(a\), in ra đáp án tương ứng

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(2\le a\le 10\)

• Subtask \(2\) (\(80\%\) số điểm): \(2\le a\le 10^6\)

Example

2
4
0 

0
2

int a;
while(cin >> a) {
    if (a == 0) break;
    // ...
}

• Tam giác \(K\) được gọi là tam giác "gần hoàn hảo" nếu \(K\) thỏa mãn \(2\) điều kiện sau:

• Ba cạnh của tam giác đó có dạng \((a,a,b)\) thỏa mãn \(a>\frac{b}{2}\) và \(|a-b|=1\) với \(a,b\in \mathbb{N}^{*}\)

• Diện tích của \(K\) là số nguyên dương.

Gọi \(Q\) là tập hợp tất cả các tam giác "gần hoàn hảo" .

Yêu cầu: Cho số nguyên dương \(N(1\leq N\leq 10^7)\) .Tính \(T=\sum\limits_{u\in Q\text{ và }P(u)\le N}P(u)\)

(trong đó: \(P(u)\) là chu vi của tam giác \(u\))

Nói cách khác, xét tất cả tam giác "gần hoàn hảo" và có chu vi không vượt quá \(N\). Hãy tính tổng chu vi tất cả tam giác đó.

Chú ý: Các tam giác có các cạnh \((a,a,b),(a,b,a),(b,a,a)\) thì cũng chỉ tính là \(1\) tam giác.

Input

• Một dòng duy nhất chứa số nguyên dương \(N(1\leq N\leq 10^7)\)

Output

• In ra đáp án \(T\) cần tìm.

Scoring

• Subtask #1 (\(20\%\) số điểm): \(1\leq N\leq 300\)
• Subtask #2 (\(80\%\) số điểm): Không có ràng buộc gì thêm

Example

16

16

Cho tập hợp \(S\) gồm \(N\) phần tử. \(S\) được gọi là tập hợp "kì dị" nếu \(S\) chứa tất cả các số từ \(1\) đến \(N\) và các phần tử này được sắp xếp theo thứ tự từ điển từ bé đến lớn.

Gọi \(W(N,K)\) là vị trí của số \(K\) trong tập hợp "kì dị" gồm \(N\) phần tử. (Biết rằng: Các phần tử của tập hợp được đánh số từ \(1\))

Yêu cầu:

• Cho hai số nguyên dương \(K,M\). Tìm số nguyên dương \(N\) nhỏ nhất sao cho \(W(N,K)=M\), nếu không tồn tại \(N\) , in ra \(0\).

Input:

• Dòng duy nhất chứa hai số nguyên \(K,M(1\le K,M\le 10^9)\),

Output:

• In ra đáp án cần tìm

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1\le K,M\le 100\)
• Subtask \(2\) (\(80\%\) số điểm): \(1\le K,M\le 10^9\)

Example

2 4 

11

Cho một bảng \(A\) có kích thước \(N \times N\) \((N ∈ \mathbb{N^*})\)

Khoảng cách giữa hai phần tử \(A[i][j]\) và \(A[p][q]\) được định nghĩa là \(|i−p|+|j−q| (1 \leq i,j,p,q \leq N)\).

(Chú ý: \(A[i][j]\) có nghĩa là phần tử ở hàng thứ \(i\) và cột thứ \(j\))

Yêu cầu: Viết chương trình thay thế mỗi phần tử \(0\) trong bảng \(A\) thành phần tử khác \(0\) và gần với nó nhất. Nếu có hai (hoặc nhiều hơn) phần tử khác \(0\) và gần với nó nhất thì giữ nguyên giá trị \(0\).

Input

• Dòng duy nhất chứa số nguyên dương \(N\)
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) phần tử thể hiện giá trị các phần tử trong bảng, biết rằng mỗi phần tử trong bảng là một số nguyên không âm, và không lớn hơn \(10^6\).

Output

• In ra bảng sau khi biến đổi

Example

3
0 0 0
7 0 3
0 5 0 

7 0 3
7 0 3
0 5 0