Kỳ thi HSG Duyên hải và Đồng bằng Bắc Bộ 2020 - Tin học - Khối 10

Minh nhận được một chiếc máy tính bấm tay màn hình LCD. Màn hình được chia thành các ô biểu diễn chữ số, mỗi ô gồm \(7\) vạch LED và mỗi chữ số sẽ tương ứng với một số vạch LED được kích hoạt nổi màu đen trên ô đó. Cách hiển thị các số như sau:

Minh bấm số nguyên dương \(N\) hiển thị trên màn hình và thắc mắc 2 câu hỏi:

1. Có bao nhiêu vạch LED được kích hoạt để hiển thị số \(N\).
2. Tính số lượng các số lớn hơn \(N\), có thể được hiển thị bởi kích hoạt thêm ít nhất một vạch LED ngoài các vạch đang được kích hoạt để hiển thị số \(N\) (không tắt bất kỳ vạch LED nào đang hiển thị và không kích hoạt vạch LED trên ô chưa có vạch kích hoạt).

Yêu cầu: Hãy lập trình giúp Minh trả lời \(2\) câu hỏi trên.

Input

• Dòng đầu tiên ghi mã câu hỏi \(V\) là \(1\) hoặc \(2\).
• Dòng thứ 2 ghi số nguyên dương \(N\) (không bắt đầu bởi chữ số \(0\)).

Output

• Nếu \(V=1\) thì in ra số vạch LED được kích hoạt để hiển thị số \(N\).
• Nếu \(V=2\) thì in ra số lượng số lớn hơn \(N\), có thể được hình thành bằng cách kích hoạt thêm ít nhất một vạch LED, bên cạnh các vạch đã kích hoạt được sử dụng để hiển thị số \(N\).

Constraints

• \(N \leq 10 ^ {18}\)

Scoring

• Subtask \(1\) (\(45\%\) số điểm): \(V = 1, N \leq 10 ^ {18}\).
• Subtask \(2\) (\(20\%\) số điểm): \(V = 2, N < 20\)
• Subtask \(3\) (\(35\%\) số điểm): \(V = 2, 20 \leq N \leq 10 ^ {18}\)

Example

1 
823 

17

2 
823 

5

Bình là một cậu bé rất đam mê toán học, đặt biệt là phần số học. Giải các bài toán về số nguyên tố, số chính phương, chia hết, \(\ldots\) là sở trường của Bình. Nhân dịp Kỳ thi Duyên hải năm nay được tổ chức lần dầu tiên theo hình thức thi online, Bình gửi đến các bạn một bài toán liên quan đến số chính phương.

Với số tự nhiên \(n\) cho trước, Bình yêu cầu bạn đếm số bộ ba số nguyên \((a,b,c)\) với \((1 \leq a < b < c \leq n)\) sao cho tất cả các tích \(a×b,a×c\) và \(b×c\) đều là các số chính phương.

Input

• Duy nhất số nguyên dương n \((n \leq 5 * 10 ^ 6)\)

Output

• Ghi ra số lượng bộ 3 số \(a,b,c\) tìm được.

Scoring

• Subtask \(1\) (\(24\%\) số điểm): \(1 \leq n \leq 100\)
• Subtask \(2\) (\(20\%\) số điểm): \(100 < n \leq 5000\)
• Subtask \(3\) (\(28\%\) số điểm): \(5000 < n \leq 10 ^ 5\)
• Subtask \(4\) (\(28\%\) số điểm): \(10 ^ 5 < n \leq 5 * 10 ^ 6\)

Example

20 

5

Một công ty cung cấp dịch vụ cho các đối tác của mình đặt tại n vùng khác nhau được đánh số \(1, 2, 3, …, n\). Công ty có \(3\) nhân viên phục vụ lưu động. Nếu xuất hiện một yêu cầu tại một địa điểm mà hiện đang không có nhân viên đang ở đó, một trong ba nhân viên di chuyển từ vị trí hiện tại của anh ta đến trực tiếp địa điểm xuất hiện yêu cầu mà không qua bất kỳ một địa điểm trung gian nào khác. Tại mọi thời điểm, chỉ có một nhân viên di chuyển. Các nhân viên chỉ di chuyển khi có yêu cầu phục vụ và không có hai nhân viên nào ở cùng một vị trí tại bất kỳ thời điểm. Chi phí để di chuyển từ vị trí \(i\) đến vị trí \(j\) là \(C_{ij}\). Chú ý rằng hàm chi phí không nhất thiết phải là đối xứng, tuy nhiên chi phí khi không di chuyển luôn bằng \(0(Cii=0)\). Các yêu cầu phải được thực hiện theo thứ tự xuất hiện (yêu cầu xuất hiện trước phải được phục vụ trước, phục vụ xong một yêu cầu mới phục vụ yêu cầu tiếp theo).

Yêu cầu: Hãy tìm lịch di chuyển các nhân viên phục vụ yêu cầu sao cho tổng chi phí là nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n,m,\) lần lượt là số vùng khác nhau và số yêu cầu cần phục vụ \((3 \leq n \leq 200,1 \leq m \leq 1000)\).
• n dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên không âm có giá trị không vượt quá \(2000\). Số thứ \(j\) của dòng thứ \(i\) là giá trị của \(C_{ij}\) - chi phí để đi từ \(i\) đến \(j\).
• Dòng cuối cùng chứa \(m\) số nguyên là danh sách các yêu cầu phục vụ theo thứ tự đăng ký. Mỗi yêu cầu được mô tả bằng một số nguyên - số hiệu địa điểm, nơi yêu cầu xảy ra. Ban đầu ba nhân viên phục vụ đang ở các địa điểm \(1, 2\) và \(3\).

Output

• Ghi ra một số nguyên \(S\) là tổng chi phí nhỏ nhất tìm được.

Scoring

• Subtask \(1\) (\(24\%\) số điểm): \(3 \leq n , m \leq 8\)
• Subtask \(2\) (\(20\%\) số điểm): \(8 < n , m \leq 50\)
• Subtask \(3\) (\(28\%\) số điểm): \(50 < n \leq 200, 50 < m \leq 1000\)

Example

5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1 

5

Sau khi khống chế thành công COVID 19, các đường bay đã được mở lại, nhu cầu đi lại tăng cao sau kì nghỉ Tết dài nhất trong lịch sử. Hiện tại là thời điểm 0, có N máy bay đang tiếp cận để hạ cánh tại sân bay Cát Bi. Máy bay thứ \(i\) \((1 \leq i \leq N)\) có thể điều chỉnh tốc độ để hạ cánh ở một mốc thời điểm nguyên trong khoảng thời gian \([L_i,R_i]\). Trong đó \(L_i\) là thời điểm sớm nhất máy bay có thể hạ cánh, \(R_i\) là thời điểm muộn nhất máy bay phải hạ cánh, quá thời gian \(R_i\), máy bay sẽ chuyển hướng hạ cánh tại sân bay khác. Khoảng thời gian \(R_i−L_i\) được gọi là giới hạn chờ của máy bay thứ \(i\) và giới hạn này tất cả N máy bay là giống nhau.

Sân bay có \(K\) đường băng, có thể hoạt động độc lập và tiếp nhận các máy bay hạ cánh. Các máy bay phải thực hiện lệnh giãn cách \(X\) giây. Hay 2 máy bay liên tiếp hạ cánh trên một đường băng phải cách nhau ít nhất \(X\) giây.

Yêu cầu: Hãy lên phương án sắp xếp các máy bay, sao cho số lượng máy bay hạ cánh là nhiều nhất có thể. Nếu có cùng phương án đảm bảo số lượng máy bay hạ cánh nhiều nhất, tìm phương án tối ưu sao cho thời gian chênh lệch nhỏ nhất giữa 2 máy bay cùng hạ cánh trên một đường băng là lớn nhất.

Input

• Dòng đầu tiên ghi \(3\) số nguyên dương \(N,K,X\) \((N \leq 10 ^ 5,K \leq 4,X \leq 10^9)\)
• Tiếp theo là \(N\) dòng, mỗi dòng ghi \(2\) số \(L_i,R_i\) \((0 \leq L_i \leq R_i \leq 10^9)\) Dữ liệu đảm bảo giá trị \(R_i−L_i\) của tất cả các máy bay là giống nhau.

Output

• Ghi ra 2 số nguyên \(T\) và \(P\) được ghi trên một dòng, phân tách bởi dấu cách. Số thứ nhất \(P-\) là số máy bay lớn nhất có thể hạ cánh được. Số thứ hai \(T-\) là giá trị của chênh lệch nhỏ nhất giữa 2 máy bay bất kỳ trên cùng một đường băng trong phương án tối ưu tìm được. Nếu mỗi đường băng chỉ tiếp nhận không quá 1 máy bay thì ghi ra \(-1\).

Scoring

• Subtask \(1\) (\(16\%\) số điểm): \(N \leq 8,K=1\)
• Subtask \(2\) (\(12\%\) số điểm): \(N \leq 8,K=2\)
• Subtask \(3\) (\(20\%\) số điểm): \(N \leq 16,K=1,0 \leq L_i \leq R_i \leq 100\)
• Subtask \(4\) (\(16\%\) số điểm): \(N \leq 16,K=2,0 \leq L_i \leq R_i \leq 100\)
• Subtask \(5\) (\(20\%\) số điểm): \(N \leq 10^5,K=1\)
• Subtask \(6\) (\(16\%\) số điểm): \(N \leq 10^5,2 \leq K \leq 4\)

Example

5 1 60
0 20
0 20
100 120
60 80
110 130 

3 65

5 2 60
0 20
0 20
100 120
60 80
110 130 

5 65

5 3 60
0 20
0 20
100 120
60 80
110 130 

5 120