Tổng hợp THTB các năm

Một số tự nhiên được gọi là số Py−ta−go là số được tạo thành từ việc ghép \(3\) số tự nhiên \(a, b, c\) theo một trật tự bất kì với nhau (không thay đổi trật tự các chữ số trong mỗi số \(a, b, c\)), trong đó \(3\) số \(a, b, c\) thỏa mãn điều kiện tổng bình phương của \(2\) số nào đó trong \(3\) số này bằng bình phương của số còn lại.

Ví dụ: Với \(3\) số \(a = 6, b = 8, c = 10\), ta có \(6^2 + 8^2 = 10^2\) và nếu ghép chúng lại với nhau theo một trật tự bất kì thì ta có được tất cả \(6\) số Py−ta−go như sau: \(6810, 6108, 8610, 8106, 1068, 1086\).

Yêu cầu: Cho \(x\) là một số Py−ta−go được ghép từ bộ ba số \(a, b, c\) như đã trình bày ở trên. Hãy tìm số lớn nhất trong \(3\) số \(a, b, c\).

Input

• Một dòng chứa số nguyên dương \(x\) có ít nhất \(3\) chữ số và có nhiều nhất \(24\) chữ số.

Output

• Ghi ra số nguyên dương cần tìm theo yêu cầu của đề. Nếu có nhiều kết quả thì chỉ ghi ra số lớn nhất trong các kết quả tìm được.

Example

6810

10

Cho một lưới hình vuông chứa rất nhiều ô vuông nhỏ. Mỗi ô vuông trong lưới hình vuông này được xác định vị trí bởi một cặp số \((i,j)\), trong đó \(i\) là chỉ số hàng và \(j\) là chỉ số cột. Các hàng được đánh chỉ số bởi các số tự nhiên bắt đầu từ \(1, 2, 3, \dots\) kể từ trên xuống dưới; các cột được đánh chỉ số bởi các số tự nhiên bắt đầu từ \(1, 2, 3, \dots\) kể từ trái sang phải. Các ô vuông trong lưới hình vuông được ghi một số tự nhiên bằng tích của chỉ số hàng và chỉ số cột của ô vuông đó.

Chọn ra hình vuông chứa \(K \times K\) ô vuông trong lưới hình vuông đã cho. Gọi \(T\) là tổng các số trong các ô vuông có trong hình vuông đã chọn.

Yêu cầu: Hãy tìm số dư trong phép chia \(T : 20192020\).

Ví dụ: Cho lưới hình vuông, ta chọn một hình vuông gồm \(3 \times 3\) ô vuông, trong đó ô vuông ở góc bên trái có chỉ số hàng bằng \(2\) và chỉ số cột bằng \(1\) (hình minh họa).

Input

• Một dòng duy nhất chứa 3 số nguyên \(i, j, K\) (\(1 \leq i \leq 1000; 1 \leq j \leq 1000; 1 \leq K \leq 10^8\)). Trong đó \(i\) và \(j\) lần lượt là chỉ số hàng và chỉ số cột của ô vuông ở góc bên trái của hình vuông được chọn; \(K\) là số ô vuông trên một hàng (và là số ô vuông trên một cột) của hình vuông được chọn.

Output

• Số dư của phép chia \(T : 20192020\).

Example

2 1 3 

54

Từ một số nguyên dương \(k\) ban đầu, ta thực hiện biến đổi số \(k\) theo quy tắc biến đổi sau đây:

Nếu \(k\) chia hết cho \(6\) thì thay số \(k\) bởi thương \(k:6\); còn nếu \(k\) không chia hết cho \(6\) thì thay số \(k\) bởi tích \(3 \cdot k\).

Yêu cầu: Hãy xác định số lần biến đổi theo quy tắc trên để \(k\) bằng \(1\). Trong trường hợp không thể biến đổi \(k\) bằng \(1\) thì in ra kết quả \(-1\).

Input

• Một dòng chứa số nguyên \(k\) (\(k \le 10^9\)).

Output

• Số nguyên \(m\) là số lần biến đổi để \(k\) bằng \(1\).

Example

12 

3

10

-1

Có một dãy các số nguyên \(a_1,a_2,...,a_n\). Ta chia dãy số này thành 2 dãy con như sau:

• Dãy con thứ nhất gồm \(k\) số đầu tiên trong dãy đã cho và tổng các phần tử của dãy con này là \(T_1\).
• Dãy con thứ hai gồm các số còn lại của dãy số đã cho và tổng các phần tử của dãy con này là \(T_2\).

Yêu cầu: Tìm số nguyên dương \(k\) là độ dài của dãy con thứ nhất sao cho \(|T_1−T_2|\) nhỏ nhất.

Chú ý: Nếu có hơn một số \(k\) thỏa mãn thì ghi ra số \(k\) nhỏ nhất.

Input

• Dòng đầu tiên ghi một số nguyên dương \(n\) \((n \leq 1000000)\)
• Dòng thứ hai ghi \(n\) số nguyên \(a_1,a_2,...,a_n\) với \(|ai| \leq 10\) \((1 \leq i \leq n)\), mỗi số cách nhau một dấu cách.

Output

• Ghi ra một số nguyên dương \(k\) thỏa mãn yêu cầu của đề bài.

Example

6
4 7 1 1 4 6 

2

Mọi số nguyên dương \(a\) đều có thể viết được dưới dạng lũy thừa bậc \(n\) của số nguyên dương \(b\) (với \(n\) là số tự nhiên). Chẳng hạn: \(27 = 3^3\); \(8 = 8^1\). Một số nguyên dương \(a\) có thể có nhiều cách biểu diễn dưới dạng một lũy thừa, chẳng hạn: \(81 = 81^1 = 9^2 = 3^4\).
Yêu cầu: Cho trước 3 số nguyên dương \(a; b; c\). Gọi \(x\) là tích của 3 số \(a; b; c\). Hỏi trong các cách viết số \(x\) thành một lũy thừa bậc \(n\) của một số nguyên dương thì số mũ \(n\) lớn nhất bằng bao nhiêu?

Input

• Chứa 3 số \(a; b; c\) mỗi số nằm trên một dòng \((a;b;c \leq 10^{12})\).

Output

• Ghi ra số \(n\) thỏa mãn yêu cầu trên.

Example

3 
3
9 

4

Có một tháp các ô vuông bằng nhau có hình dạng giống một tam giác cân. Các hàng tính từ trên xuống dưới có số ô vuông lần lượt là \(1; 3; 5; 7; …\). Một tháp ô vuông có \(n\) hàng gọi là tháp ô vuông bậc \(n\) (\(n\) là số tự nhiên).

Ví dụ ở hình vẽ sau ta có một tháp ô vuông bậc \(3\):

Yêu cầu: Cho trước một tháp ô vuông bậc \(n\). Hãy tính xem trong tháp ô vuông này có tất cả mấy hình vuông tạo thành từ các ô vuông đó.

Input

• Chứa một số \(n\) (\(n \le 5 \times 10^5\)).

Output

• Ghi ra số nguyên \(m\) là số các hình vuông cần tìm.

Example

3

11

Nhập vào từ bàn phím 2 số nguyên dương khác nhau \(x, y\) (\(x, y \le 60000\)). Hãy tìm và in ra màn hình số nguyên dương \(z\) sao cho tam giác có độ dài 3 cạnh là 3 số \(x, y, z\) là tam giác cân có diện tích lớn nhất.

Input

• Hai số nguyên dương \(x, y\)

Output

• In ra một số nguyên dương \(z\)

Example

5 
7

7

Hiếu đi dự đám cưới ở một nhà hàng trong thành phố. Trời nắng nên con đường hành lang đi từ nhà hàng ra bãi giữ xe được che bởi các tấm bạt có kích thước khác nhau (đường hành lang là đường thẳng). Nhưng vì các chú bảo vệ lo nhận và giữ xe nên che các tấm bạt rất lộn xộn chỗ thì khít, chỗ thì chồng lên nhau, chỗ thì hở ra. Hiếu muốn tìm đoạn đường dài nhất trên đường mình đi được che kín bởi các tấm bạt.

Cho \(n\) cặp số \([l_{i},r_{i}]\) là vị trí đầu và vị trí cuối của mỗi tấm bạt theo chiều dài hành lang.

Yêu cầu: Viết chương trình tìm độ dài lớn nhất của đoạn đường được che kín bởi các tấm bạt.

Input

• Dòng đầu chứa một số nguyên \(n\) \((1 < n \leq 10000)\) là số lượng tấm bạt.
• \(n\) dòng tiếp theo, mỗi dòng biểu diễn vị trí của mỗi tấm bạt theo chiều dài hành lang là \(l_i\) và \(r_i\) \((0 \leq l_{i}, r_{i} \leq 60000)\).

Output

• Ghi ra một số nguyên duy nhất theo yêu cầu trên.

Example

7
7 12
0 5
20 25
33 38
6 8
27 34
11 19

13

Từ một hình vuông cho trước, ta vẽ các đoạn thẳng nối trung điểm hai cạnh kề của nó thì được một hình vuông mới nhỏ hơn. Tiếp tục, vẽ các đoạn thẳng nối trung điểm hai cạnh kề của hình vuông được tạo thành này thì được một hình vuông mới nhỏ hơn nữa. Cứ làm như vậy cho đến khi được tất cả N hình vuông.

Các hình vuông theo thứ tự tăng dần về độ dài của các cạnh ta đánh số thứ tự từ 1 đến \(N\).

Ở hình vuông thứ nhất ta ghi 4 số tự nhiên \(a, b, c, d\) trên 4 đỉnh của nó.

Mỗi số trên 4 đỉnh của hình vuông thứ hai được xác định bằng tổng của 2 số trên 2 đỉnh gần với nó nhất của hình vuông thứ nhất.

Mỗi số trên 4 đỉnh của hình vuông thứ ba được xác định bằng tổng của 2 số trên 2 đỉnh gần với nó nhất của hình vuông thứ hai. Cứ làm như vậy cho hết \(N\) hình vuông.

Yêu cầu: Tính tổng các số trên 4 đỉnh của hình vuông thứ \(N\).

Input

• Dòng đầu là số \(N\) (\(1\le N\le 50\))
• Dòng thứ 2 chứa 4 số \(a, b, c, d\) mỗi số cách nhau 1 dấu cách (\(1 \le a,b,c,d \le 500\))

Output

• Ghi ra một số nguyên duy nhất theo yêu cầu trên.

Example

3
1 3 5 7

64

Nhập vào từ bàn phím một xâu kí tự \(S\). Hãy viết ra một kí tự có số lần xuất hiện nhiều nhất trong xâu \(S\) (có phân biệt kí tự hoa và kí tự thường).

Lưu ý: Nếu có nhiều kí tự có cùng số lần xuất hiện nhiều nhất trong xâu \(S\) thì in ra kí tự xếp theo thứ tự từ điển nhỏ nhất trong xâu đó.

Input

• Dòng đầu tiên và duy nhất chứa 1 xâu \(S\) (chỉ gồm các chữ cái trong tập \(\{a,\dots,z, A,\dots,Z\}\)) \((|S| \leq 10^6)\)

Output

• In ra kí tự xuất hiện nhiều nhất trong xâu \(S\).

Example

abcdaadDedgdAAA 

d

Nhập vào từ bàn phím một số nguyên dương \(n\) \((n≤10^{16})\). Hãy tìm và in ra màn hình chữ số lớn nhất của số \(n\).

Input

• Số nguyên dương \(n\)

Output

• Kết quả của bài toán

Example

70128 

8

Cho số nguyên dương \(N\).

Yêu cầu: Hãy phân tích \(N\) thành thừa số nguyên tố và đếm ước số của \(N\).

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(N\).

Output

• Dòng thứ nhất ghi phân tích thừa số của \(N\) dưới dạng \(a * b * c * d\), với \(a, b, c, d\) là các thừa số nguyên tố của \(N\).
• Dòng thứ hai ghi số lượng ước số của \(N\).

Constraints

• \(N\leq 2.10^9\)

Example

10 

2*5
4

100 

2*2*5*5
9

Hãy tìm số lượng lớn nhất ước số là số nguyên tố của một số nguyên bất kỳ trong đoạn từ \(1\) đến \(n\).

Dữ liệu vào:

• Số test \(q ( 1 \le 10^5)\)
• Mỗi test trên \(1\) dòng, số nguyên dương \(n (n \le 10 ^ {18})\)

Dữ liệu ra:

• Mỗi test trên \(1\) dòng, số lượng lớn nhất ước số là số nguyên tố.

Input

6
1
2
3
500
5000
10000000000

Output

0
1
1
4
5
10

Một số được gọi là số nguyên tố cân bằng nếu nó là số nguyên tố có \(2k + 1\) chữ số \((k \in \mathbb{N}^*)\), trong đó có \(2k\) chữ số giống nhau và có đúng \(1\) chữ số ở vị trí chính giữa (tức vị trí thứ \(k + 1\) từ trái sang phải) là khác với các chữ số còn lại.

Ví dụ: Số \(7778777\) là số cân bằng.

Yêu cầu:

Nhập từ bàn phím \(1\) số nguyên dương \(k\) \((k \le 7)\). Hãy tính và in ra màn hình số lượng các số nguyên tố cân bằng có \(2k + 1\) chữ số.

Example

3

7

In ra tất cả cặp số nguyên tố \(A,B(A\le B)\) thỏa mãn \(A+B\) cũng là số nguyên tố và \(A+B\le N\). (In theo thứ tự từ điển từ bé đến lớn)

Input

• Dòng thứ nhất chứa số nguyên dương \(N(1\le N\le 10^6)\)

Output

• Dòng thứ nhất in ra số \(k\) - số lượng cặp \((A,B)\) thỏa mãn yêu cầu bài toán

• In ra \(k\) cặp \((A,B)\) thỏa mãn yêu cầu bài toán (theo thứ tự từ điển từ bé đến lớn).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(0<N\le 10\)

• Subtask \(2\) (\(20\%\) số điểm): \(0<N\le 10^4\)

• Subtask \(3\) (\(60\%\) số điểm): \(\text{Còn lại}\)

Example

7

2
2 3
2 5

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Hãy loại một phần tử bất kỳ trong dãy số và đặt \(P\) tích các số còn lại. Phân tích thừa số nguyên tố của \(P\), sau đó tính tổng các số mũ trong thừa số nguyên tố đó. Hãy tìm cách bỏ loại bỏ số nào để tổng các số mũ nhỏ nhất có thể.

Ví dụ: cho dãy số gồm \(4\) số \(1; 2; 4; 10\). có 2 cách bỏ đều cho tổng số mũ bằng \(3\) là nhỏ nhất:

• Cách 1: Loại bỏ số \(4\), ta có \(P=1 * 2*10=20=2^2*5\) có tổng số mũ bẳng \(3\)
• Cách 2: Loại bỏ số \(10,\) ta có \(P=1 * 2*4=8=2^3\) có tổng số mũ bẳng \(3\)

Yêu cầu: Cho dãy số \(A\), hãy in ra tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Input

• Đọc từ file văn bản TSNT.INP:
• Dòng đầu tiên chứa dãy số \(n\ (n≤10^5)\).
• Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A\ (A_i≤10^6)\).

Output

• Ghi ra file văn bản TSNT.OUT một số nguyên là tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤8\).
• Subtask \(3\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤10^6\).
• Subtask \(4\) (\(10\%\) số điểm): trường hợp còn lại.

Example

4
1 2 4 10 

3