Nhảy về 0 div 1 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

1. Cặp số "đẹp đôi"

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input

2
4
0

Output

0
2

Note

Ta nhận thấy rằng, ứng với $a=2$, không tồn tại $n$ nào thỏa mãn để $(a,n)$ là cặp "đẹp đôi" nên đáp án là $0$.
Ứng với $a=4$, ta tìm được $n=2$ thỏa mãn $(4,2)$ là cặp đẹp đôi vì ta tìm được dãy $\left\{u\right\}=\left\{4\right\}$ vì $3, 5$ là các số nguyên tố.

Gợi ý: Phần đọc input có thể dùng như sau:

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

2. Tam giác "gần hoàn hảo"

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input

Output

Note

Giải thích: Chỉ có duy nhất $1$ tam giác "gần hoàn hảo" thỏa mãn yêu cầu bài toán đó là : $(5;5;6)$. Vậy nên đáp án là $16$

3. Tập hợp "kì dị"

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input

2 4

Output

Note

Xét tập hợp "kì dị" $S$ gồm $11$ phần tử. Khi đó $S=\left\{1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9\right\}$. Khi đó ta có: $W(11,2)=4$ vì số thứ $4$ trong tập $S$ là $2$.

4. Thay thế số 0

Điểm: 100 (p) Thời gian: 5.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input

Output

7 0 3
7 0 3
0 5 0

Note

Ta có: $A[1][1]=0$. Và chỉ có $1$ số duy nhất khác $0$ và gần với nó nhất đó là $A[2][1]=7$. Do đó ta gán $A[1][1]=7$.
Tiếp theo, ta có: $A[1][2]=0$. Và có tới ba số khác $0$ và gần với nó nhất đó là $A[2][1]=7$; $A[2][3]=3$ và $A[3][2]=5$. Nên nó vẫn giữ nguyên giá trị 00. (Ở đây ta không tính $A[1][1]$ là số khác không và gần với $A[1][2]$ nhất vì $A[1][1]$ bản chất nguyên thủy nó là $0$)
Tương tự cho các phần tử $0$ còn lại ta sẽ thu được kết quả cần tìm.

5. Cặp số "hàng xóm"

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Hai số nguyên dương $A$ và $B$ được gọi là cặp số "hàng xóm" nếu chúng thỏa mãn $1$ trong $2$ điều kiện sau:

Trong biểu diễn thập phân, $A$ và $B$ có cùng độ dài và khác nhau chính xác một chữ số. (Ví dụ $\left\{158,198\right\}$ là cặp số "hàng xóm")
Nếu ta thêm một chữ số vào bên trái của $A(\text{ hoặc }B)$ thì ta sẽ thu được $B(\text{ hoặc }A)$ (Ví dụ $\left\{47,147\right\}$ là cặp số "hàng xóm")

Bây giờ, ta gọi số nguyên tố $G$ là "bà con" với số $2$ nếu tồn tại một chuỗi số $a_0,a_1,....a_q$ thỏa mãn điều kiện sau:

$a_0=2;a_q=G$
$\left\{a_i,a_{i+1}\right\}$ là cặp số "hàng xóm" và $a_i\in \mathbb{P},a_{i+1}\in \mathbb{P}$ với mọi $0\le i\le q-1(q\in \mathbb{N}^{*})$
$a_i\le G\text{ }\forall 0\le i\le q$

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

Nói cách khác, tồn tại một dãy chuyển hóa $2$ thành $G$ mà tất cả các số trong dãy là số nguyên tố, hai số kề nhau phải là "hàng xóm" và tất cả các số trong dãy không quá $G$.

Ví dụ, $31$ là số "bà con" với $2$ vì ta có dãy sau: $2, 7, 17, 11, 31$.

Cho số nguyên dương $N$ và gọi $F(N)$ là tổng của tất cả các số nguyên tố không quá $N$ và không "bà con" với số $2$.

Yêu cầu:

Nhập số nguyên dương $N$. In ra $F(N)$ tương ứng.

Input:

Một dòng duy nhất chứa số nguyên dương $N(1\le N\le 10000000)$

Output:

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

Scoring:

Subtask $1$ ($20\%$ số điểm): $1\le N\le 1000$
Subtask $2$ ($80\$$ số điểm): $1000$ $\le N \le$ $10000000$

Example

Test 1

Input

Output

Note

Từ $1$ đến $11$ chỉ có duy nhất số $11$ là số nguyên tố không "bà con" với số $2$ nên đáp án là $11$

6. Cặp số "yêu thương"

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một mảng gồm $n$ số nguyên $a_1,a_2,...a_n$, chúng ta gọi $\left\{a_i,a_j\right\}$ là cặp số "yêu thương" của mảng đã cho nếu $i\ne j$ và $a_i+a_j$ là số nguyên tố.

Cho số nguyên không âm $k$.

Yêu cầu: Chọn ra $m$ cặp "yêu thương" $p_1,p_2,...,p_m$ từ mảng trên thỏa mãn những điều kiện sau:

$m\le k$
$S=|p_1\cup p_2\cup...\cup p_m|$ đạt giá trị lớn nhất. Và xuất kết quả $S $ này ra màn hình.

Input

Dòng thứ nhất chứa số nguyên $T(1\le T\le 20)$ - Thể hiện số testcase
Dòng thứ hai chứa hai số nguyên $n,k(1\le n\le 3000; 0\le k\le \frac{n(n-1)}{2})$
Dòng thứ ba chứa $n$ số nguyên $a_1,a_2,...,a_n$ với $1\le a_i\le 10^6$

Output

In ra giá trị $S$ cần tìm.

Scoring

Subtask $1$ ($20\%$ số điểm): $1\le n\le 10$
Subtask $2$ ($80\%$ số điểm): $1\le n\le 3000$

Example

Test 1

Input

1
4 2 
5 4 3 2

Output

Note

Ở ví dụ 1 ta tìm được hai cặp "yêu thương": $p_1=\left\{a_1,a_4\right\}=\left\{5,2\right\};p_2=\left\{a_2,a_3\right\}=\left\{4,3\right\}$

Do đó $S=|p_1\cup p_2|=4$. (vì $p_1\cup p_2 =\left\{5,2,3,4\right\}$)

Test 2

Input

1
3 2
1 1 2

Output

Note

Ở ví dụ 2 ta tìm được hai cặp "yêu thương": $p_1=\left\{a_1,a_2\right\}=\left\{1,1\right\};p_2=\left\{a_2,a_3\right\}=\left\{1,2\right\}$

Do đó $S=|p_1\cup p_2|=2$. (vì $p_1\cup p_2 =\left\{1,2\right\}$)