Tuyển sinh 10 chuyên Tin Phổ thông Năng khiếu 2024

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Số may mắn

Trên bàn có một dãy các ô, các ô đánh số liên tiếp bắt đầu từ $1$ , từ trái sang phải. An có một bộ bài gồm $n$ lá bài có số hiệu là $1, 2, 3, \dots, n$ . Để chọn ra lá bài may mắn bạn An thực hiện các thao tác như sau:

Bước 1: An chia các lá bài hiện có vào các ô liên tiếp bắt đầu từ ô thứ nhất với số hiệu các lá bài theo thứ tự tăng dần.

Bước 2: An nhặt các lá bài trong các ô có số thứ tự chia cho $3$ dư $2$ và loại bỏ các lá bài còn lại trên dãy. Nếu số lá bài nhặt được nhiều hơn $1$ thì quay lại thực hiện Bước 1. Trong trường hợp nhặt được đúng $1$ lá thì lá bài đó là lá bài may mắn.

Ví dụ: Với $n = 15$ :

Lần thứ nhất An sẽ chia các lá bài: $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15$ Nhặt các lá bài $2, 5, 8, 11, 14$ .

Lần thứ hai An sẽ chia các lá bài: $2, 5, 8, 11, 14$ Nhặt các lá bài $5, 14$ .

Lần thứ ba An sẽ chia các lá bài: $5, 14$ Nhặt lá bài $14$ là lá bài may mắn.

Yêu cầu: Cho biết $n$ , hãy tìm ra số hiệu của lá bài may mắn.

Input

Gồm một số nguyên dương $n$ ( $2 \leq n \leq 109$ ).

Output

Ghi ra một số nguyên dương duy nhất là số hiệu của lá bài may mắn.

Sample Input 1

Sample Output 1

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. San lấp

Bản đồ một vùng đất là một hình chữ nhật kích thước $m \times n$ được chia làm lưới ô vuông đơn vị, các hàng của lưới được đánh số từ $1$ tới $m$ từ trên xuống dưới và các cột của lưới được đánh số từ $1$ tới $n$ từ trái qua phải. Ô nằm trên giao của hàng $x$ , cột $y$ được gọi là ô $(x, y)$ , mỗi ô có hai trạng thái là ô nước hay ô đất. Bản đồ được mô tả bởi bảng $h(m \times n)$ với $h xy = 1$ nếu ô $(x, y)$ là đất và $h xy = 0$ nếu ô $(x, y)$ là nước.

Những ô đất tạo thành những "đảo" định nghĩa như sau: Hai ô đất gọi là cùng đảo nếu ta có thể đi từ ô này tới ô kia bằng cách di chuyển qua các ô kề cạnh là đất, ngược lại hai ô đó được coi là nằm trên hai đảo khác nhau.

Yêu cầu: Bạn được phép lấp đúng $1$ ô nước để trở thành ô đất (tức là đổi giá trị một ô $0$ thành $1$ ) sao cho sau khi lấp thì nhận được một đảo có diện tích lớn nhất có thể.

Input

Dòng $1$ chứa hai số nguyên dương $m, n \leq 1000$ .

$m$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số, số thứ $j$ là $h ij = 0$ hoặc $1$ . Các số trên một dòng của input file được ghi cách nhau ít nhất một dấu cách. Dữ liệu đảm bảo trên bản đồ có ít nhất một ô bằng $0$ .

Output

Ghi ra một số nguyên duy nhất là số ô của đảo lớn nhất nhận được sau khi lấp một ô.

Sample Input 1

6 6
1 0 1 0 1 1
1 0 1 0 1 1
1 1 1 0 0 0
0 0 0 1 1 1
1 1 0 0 1 0
1 1 1 0 1 1

Sample Output 1

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Mật khẩu

Nam viết liên tiếp các số nguyên dương bắt đầu từ $1$ thành một dãy các chữ số vô hạn và đánh số các chữ số này bắt đầu từ $1$ tạo thành dãy số $a = a 1 a 2 a 3 \dots$ . Dãy chữ số khi viết tới số $24$ là: $a = 123456789101112131415161718192021222324 \dots$

Như vậy chữ số thứ $20$ là $1$ ( $a 20 = 1$ ), chữ số thứ $21$ là $5$ ( $a 21 = 5$ ).

Nam chọn một số nguyên dương $k$ và $4$ chữ số liên tiếp bắt đầu từ chữ số thứ $k$ : $a k a k+1 a k+2 a k+3$ là mật khẩu chiếc Iphone của Nam.

Yêu cầu: Cho số $k$ , hãy tìm $4$ chữ số $a k a k+1 a k+2 a k+3$ là mật khẩu chiếc Iphone của Nam.

Input

Gồm duy nhất một số nguyên dương $k \leq 1014$ .

Output

Ghi một dòng ghi liên tiếp $4$ chữ số $a k a k+1 a k+2 a k+3$ tìm được.

Sample Input 1

Sample Output 1

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Cấu trúc đề và tiến độ