Tin học trẻ B - TP Đà Nẵng 2022

Nhập vào từ bàn phím một xâu kí tự \(S\) (xâu \(S\) có không quá \(255\) kí tự). Hãy đếm và in ra màn hình số lượng kí tự chữ số 9 có trong xâu \(S\).

Example

CdqC9Cac8ac96c2369

3

Một số nguyên dương được gọi là siêu đối xứng nếu tất cả các chữ số của nó giống nhau. Chẳng hạn số \(777\) hoặc \(4444\) là các số nguyên dương siêu đối xứng.

Nhập từ bàn phím một số nguyên dương \(x\). Hãy tìm và in ra màn hình số nguyên dương \(y\) nhỏ nhất sao cho tổng \(x + y\) là một số nguyên dương siêu đối xứng.

Input

• Gồm 1 dòng duy nhất chứa số nguyên dương \(x\) \((1 \leq x \leq 10^{16})\).

Scoring

• Subtask \(1\) (\(50\%\) số test): \(x \le 10^6\).
• Subtask \(2\) (\(30\%\) số test): \(10^6 < x \le 10^9\).
• Subtask \(3\) (\(20\%\) số test): \(10^9 \le x \le 10^{16}\).

Example

45

10

Giả thuyết Goldbach do nhà toán học người Đức Christian Goldbach (1690-1764) nêu ra vào năm 1742 trong một lá thư gửi tới nhà toán học Leonhard Euler, là một trong những bài toán lâu đời và nổi tiếng còn chưa giải được trong lý thuyết số nói riêng và toán học nói chung. Giả thuyết phỏng đoán rằng:

Mỗi số tự nhiên chẵn lớn hơn \(2\) có thể biểu diễn bằng tổng của hai số nguyên tố.

Giả thuyết đã được chỉ ra là đúng tới \(4 \times 10^{18}\), nhưng hiện nay vẫn chưa được chứng minh hoàn toàn.

Bằng kiến thức tin học em hãy thực hiện thử thách sau: Cho trước số \(x\) là số tự nhiên chẵn lớn hơn \(2\).

Yêu cầu: Hãy cho biết có bao nhiêu cách phân tích số \(x\) thành tổng của 2 số nguyên tố.

Lưu ý: Nếu phân tích được \(x = a + b\) hay \(x = b + a\) (trong đó \(a\) và \(b\) là các số nguyên tố) thì cũng chỉ được tính là một cách phân tích.

Input

• Đọc ở file văn bản GOL.INP một số \(x\) là số tự nhiên chẵn lớn hơn \(2\).

Output

• Ghi ra file văn bản GOL.OUT một số \(m\) theo yêu cầu.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(x \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(10^3 < x \le 10^4\).
• Subtask \(3\) (\(20\%\) số điểm): \(10^4 < x \le 10^6\).

Example

10

2

Có một lưới ô vuông có kích thước \(N × N\) được đánh chỉ số hàng từ \(1\) đến \(N\) (theo chiều từ trên xuống dưới) và chỉ số cột từ \(1\) đến \(N\) (theo chiều từ trái sang phải). Mỗi ô trong lưới đượ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.

Tại ô \((1; 1)\) người ta đặt một con robot tự hành. Mỗi lần di chuyển robot chỉ đi sang phải một ô hoặc đi xuống dưới một ô. Trong lưới ô vuông này người ta đặt một viên đá vào một số ô để làm vật cản.

Yêu cầu: Hãy tính xem có bao nhiêu đường đi từ ô \((1; 1)\) đến ô \((N; N)\). Biết rằng robot không thể đi vào ô có vật cản và hai đường đi được gọi là khác nhau nếu có ít nhất một ô thuộc đường đi này nhưng không thuộc đường đi kia.

VD: Xét lưới ô vuông kích thước \(3\times 3\) như hình vẽ sau:

Trong lưới ô vuông \(3\times 3\) này người ta đặt viên đá vào ô \((1;3)\) và ô \((2;1)\).
Với dữ kiện trên thì robot có tất cả 2 đường đi như sau:

\((1;1) → (1;2) → (2;2) → (2;3) → (3;3)\)

\((1;1) → (1;2) → (2;2) → (3;2) → (3;3)\)

Input

Đọc từ file văn bản ROBOT.INP có cấu trúc như sau:

• Dòng đầu tiên chứa 2 số nguyên dương \(N\) và \(M\) (mỗi số cách nhau 1 dấu cách; \(M < N\)).
• \(M\) dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương \(i\) và \(j\) (mỗi số cách nhau một dấu cách) là chỉ số hàng và chỉ số cột của ô được đặt vào đó một viên đá là vật cản.

Output

• Ghi ra file văn bản ROBOT.OUT một số \(k\) là số đường đi của robot từ ô \((1; 1)\) đến ô \((N; N)\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 10\).
• Subtask \(2\) (\(40\%\) số điểm): \(10 < N \le 30\).
• Subtask \(3\) (\(30\%\) số điểm): \(30 < N \le 100\).

Example

3 2
1 3
2 1

2