Contest 2

Trong bảng mã ASCII, \(26\) kí tự chữ cái thường từ ‘a’ đến ‘z’ được mã hóa tương ứng bằng các số tự nhiên từ \(97\) đến \(122\).

Cho một xâu kí tự \(S\) chỉ chứa toàn các kí tự chữ cái thường. Gọi \(P\) là xâu mã hóa tương ứng của xâu \(S\) bằng cách mã hóa từng ký tự trong \(S\) (theo bảng mã ASCII) và viết liên tiếp nhau. Ví dụ: \(S\) = ‘ab’ thì \(P\) = ‘9798’.

Hãy viết chương trình nhập vào từ bàn phím một xâu đã mã hóa \(P\) và in ra màn hình xâu kí tự \(S\).

Input

• Một xâu đã mã hóa \(P\).

Output

• In ra màn hình xâu ký tự \(S\).

Constraints

• \(1 \leq P.size() \leq 255\)

Example

979899 

abc

1009711097110103 

danang

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Mỗi phần tử có giá trị không vượt quá \(10^9\) và \(n≤ 10^5\). Một cặp số được gọi là cặp tương đồng với \(x\), nếu cặp số này có tổng bằng số \(x\) cho trước nào đó.

Yêu cầu: Hãy đếm xem trong dãy số \(A\) có bao nhiêu cặp số (\(A_i;A_j\)) tương đồng với \(x\) (có nghĩa là \(A_i+ A_j=x\)) với \(i<j\).

Input

• Dòng đầu tiên chứa dãy số \(n,x\) (\(n≤10^5,x≤10^6\)).
• Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A\) (\(A_i≤10^9\)).

Output

• Ghi ra một số nguyên là cặp đôi tương đồng của dãy số.

Example

7 6
1 2 4 3 4 5 3 

4

Một xâu kí tự được gọi là xâu đối xứng nếu ta đọc xâu này từ trái sang phải hoặc từ phải sang trái là như nhau. Chẳng hạn xâu ‘abcba’ là một xâu đối xứng. Cho trước một xâu kí tự S không chứa kí tự trống (dấu cách). Hãy tìm cách cắt xâu S thành 2 xâu (2 xâu này phải khác xâu rỗng) là P và Q (với P là phần đầu, Q là phần còn lại của xâu S) sao cho khi ghép xâu P vào sau xâu Q ta được một xâu kí tự mới là xâu kí tự đối xứng.

Dữ liệu vào:

• Một xâu kí tự S (xâu S có không quá 255 kí tự)

Kết quả:

• Ghi ra một số nguyên k là độ dài của xâu P. Trường hợp không có cách cắt nào thỏa mãn yêu cầu đề bài thì ghi ra một số 0.

Chú ý: Trường hợp có nhiều cách cắt thỏa mãn yêu cầu đề bài thì chọn cách cắt sao cho độ dài của xâu P là nhỏ nhất.

Input

abaabaabaaba

Output

3

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

Cho số nguyên N (\(0 ≤ N ≤ 10^{15}\)).

Yêu cầu:

• Tìm số nguyên dương \(Q\) nhỏ nhất có hơn một chữ số sao cho tích các chữ số của \(Q\) bằng \(N\).

Dữ liệu:

• Dòng thứ nhất ghi số nguyên dương \(T\) (\(2 ≤ T ≤ 100\)) là số lượng test.
• \(T\) dòng tiếp theo, mỗi dòng ghi một số nguyên dương \(N\).

Kết quả:

• Ghi ra gồm \(T\) dòng, mỗi dòng ghi ra số \(Q\) tìm được tương ứng với số \(N\), nếu không tìm được thì ghi ra số \(-1\).

Input:

4
10
16
13
9

Output:

25
28
-1
19

Nhập vào từ bàn phím một số nguyên dương N (với 2 <= N <= 100000). Gọi X là tích 1.2.3...N.

Yêu cầu: Tìm số nguyên M là số lượng chữ số 0 tận cùng của số X.

Dữ liệu vào:

• Chứa một số nguyên dương N (với \(2 <= N <= 100000\)).

Kết quả:

• Ghi ra số nguyên M là số lượng chữ số 0 tận cùng của số X.

Input

5

Output

1

Giải thích ví dụ:

X=12345= 120 nên có 1 số 0 (zero) tận cùng.

Nguồn: Bài 1 HSG lớp 9 TPĐN '2015-2016

Lan có 1 tấm bìa hình chữ nhật có các kích thước là \(x\) (cm) và \(y\) (cm), (\(x,y\) là số nguyên dương). Lan muốn cắt tấm bìa này thành những hình vuông bằng nhau có độ dài cạnh là số nguyên (đơn vị cm) sao cho tấm bìa được cắt hết không còn thừa mảnh nào. Hỏi Lan có thể cắt được ít nhất mấy hình vuông?

Yêu cầu: Viết chương trình nhập vào \(x,y\) tính và in ra \(m\) - là số lượng hình vuông cần tìm theo yêu cầu trên.

Input

Nhập từ bàn phím 2 số nguyên dương \(x, y (x, y \le 10^9)\), mỗi số trên 1 dòng:

• Dòng đầu chứa số \(x\)
• Dòng thứ hai chứa số \(y\)

Output

• In ra màn hình số lượng hình vuông.

Example

6 
8

12

Trong Học kỳ I vừa qua, Tý đạt được danh hiệu học sinh giỏi nên được bố
thưởng. Biết Tý là học sinh rất đam mê Toán và Tin học nên bố muốn thử thách Tý
bằng một trò chơi có thưởng như sau:

Bố có rất nhiều hộp hình khối lập phương giống nhau xếp thành một hàng thẳng
và được đánh số ký hiệu bằng các số tự nhiên lẻ bắt đầu từ 1; 3; 5;... Trong các hộp đó
HSG Tin học Lớp 9 NH 2018−2019
có duy nhất 1 hộp đựng phần thưởng, các hộp khác là hộp rỗng. Bố cho Tý biết hộp
đựng phần thưởng là hộp chính giữa của một đoạn dài nhất (ít nhất là 3 hộp liên tiếp)
có tổng các số ký hiệu ghi trên các hộp bằng số m.

Yêu cầu:

• Với số m cho trước, hãy tìm số ký hiệu của hộp có chứa phần thưởng.

Dữ liệu vào:

• Gồm một số nguyên dương m (\(m<=10^{16}\)).

Dữ liệu ra:

• Ghi ra một số k là số ký hiệu của hộp
  có chứa phần thưởng.

Input

45

Output

9

Giải thích

Các hộp được đánh số ký hiệu là 1; 3; 5; 7; 9; 11; 13; 15; 17; 19; 21; 23; 25;…
Đoạn dài nhất có tổng các số ký hiệu ghi trên hộp bằng 45 là các hộp có số ký
hiệu 5; 7; 9; 11; 13. Do đó hộp cần tìm có số ký hiệu là 9.

Cho trước hai số nguyên dương m và n với \(1< m ≤ 10^{15} ; 1 < n ≤ 10^7\) . Hãy xác định có bao nhiêu cặp số nguyên dương \((p; q)\) thỏa mãn đồng thời cả 3 điều kiện: \(p < m; q < n\) và phân số \((m+p)/(n+q)\) có giá trị là một số nguyên.

Dữ liệu vào:

• Dòng thứ nhất chứa số nguyên dương m (\(1< m ≤ 10^{15}\))
• Dòng thứ hai nguyên dương n (\(1< n ≤ 10^7\))

Kết quả:

• Ghi ra một số nguyên k là số cặp số nguyên dương (p;q) thỏa yêu cầu trong đề bài

Input

5
3

Output

1

Giải thích:

• Chỉ có 1 cặp số \((p;q)\) thỏa mãn là \((3;1)\)