Tin học trẻ C2 - Tỉnh Bắc Giang 2024

Một số được coi là tròn trịa khi và chỉ khi nó chỉ có duy nhất \(1\) chữ số duy nhất khác \(0\). Ví dụ như \(100, 200, 400, 5000, \ldots\) là các số tròn trịa còn \(412, 230, 152, 15324, \ldots\) thì không.

Yếu cầu: cho một số nguyên \(n\). Tìm số nguyên \(x\) tròn trịa lớn nhất sao cho \(x \leq n\).

Input

• Một dòng duy nhất chứa một số nguyên dương \(n\) \((n \leq 10^{100})\).

Output

• Gồm một dòng duy nhất chứa một số nguyên \(x\) là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10^{6}\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{18}\).
• Subtask \(3\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

101

100

Cho hai số nguyên dương \(n, m\) và mảng \(a\) gồm \(n\) số nguyên dương phân biệt \(a_{1}, a_{2}, \ldots, a_{n}\). Tính tích các số nằm trong khoảng từ \(1\) đến \(m\) mà không thuộc mảng \(a\). Do kết quả có thể rất lớn, bạn cần đưa ra kết quả sau khi chia lấy phần dư cho \(10^{9} + 7\).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n, m\) \((1 \leq n \leq m \leq 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên dương phân biệt \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq m)\).

Output

• Gồm một dòng duy nhất chứa một số nguyên là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(m \leq 50\).
• Subtask \(2\) (\(30\%\) số điểm): \(m \leq 120\).
• Subtask \(3\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

3 5
1 2 4

15

Bạn được cho một mảng \(a\) gồm \(n\) (\(n\) chia hết cho \(3\)) phần tử. Bạn được thực hiện vô số thao tác sau: tăng hoặc giảm \(1\) phần tử bất kỳ lên hoặc xuống \(1\) đơn vị. Gọi \(c_{0}, c_{1}\) và \(c_{2}\) lần lượt là số lượng các phần tử trong mảng \(a\) khi chia lấy dư cho 3 có số dư bằng \(0, 1\) và \(2\). Một mảng được gọi là cân đối khi \(c_{0} = c_{1} = c_{2}\).

Yêu cầu: bạn hãy tìm cách cân đối mảng \(a\) ban đầu bằng cách thực hiện \(0\) hoặc nhiều thao tác và in ra số thao tác ít nhất để cân đối mảng \(a\).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) \((1 \leq n \leq 5 \times 10^{5}, n \mod 3 = 0)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((0 \leq a_{i} \leq 10^{9})\).

Output

• Gồm một dòng duy nhất chứa một số nguyên là số thao tác ít nhất để cân đối mảng.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n = 3\).
• Subtask \(2\) (\(40\%\) số điểm): \(a_{i} \leq 2\).
• Subtask \(3\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

6
5 3 8 9 11 34

1

Cho bốn số nguyên dương \(n, a, b, c\) hãy tính tổng sau:

Với \(x\) là số nguyên thỏa mãn các tính chất sau:

• \(x\) chia hết cho \(a\) hoặc \(x\) chia hết cho \(b\) hoặc \(x\) chia hết cho cả \(a\) và \(b\)
• \(x\) không chia hết cho \(c\).

Trong đó \(\left\lfloor x \right\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Input

• Dòng thứ nhất chứa một số nguyên dương \(q\) \((1 \leq q \leq 50)\) là số bộ thử nghiệm.
• \(q\) dòng tiếp theo, dòng thứ \(i\) tương ứng với bộ thử nghiệm thứ \(i\), dòng thứ \(i\) chứa bốn số nguyên \(n, a, b, c\) \((1 \leq n, a, b, c \leq 10^{9})\).

Output

• In ra \(q\) dòng, dòng thứ \(i\) chứa kết quả tương ứng với bộ thử nghiệm thứ \(i\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10^{6}\).
• Subtask \(2\) (\(30\%\) số điểm): \(a = b\) và \(c > n\).
• Subtask \(3\) (\(20\%\) số điểm): \(c > n\).
• Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

2
15 2 3 5
30 2 4 9

21
44