CHO ĐỘI TUYỂN HSG

Đề xuất 11 không chuyên
Số Fibonacci (FIBNUM)
Dãy số Fibonacci là dãy số được định nghĩa như sau:

𝑓
0
𝑓
1=1
𝑓
𝑖
𝑓
𝑖−2
𝑓
𝑖−1 ∀𝑖≥2

Cho 𝑁 số nguyên dương, hãy xác định mỗi số có là số Fibonacci hay không.
Dữ liệu
Dòng 1: số nguyên 𝑁
1≤𝑁
10
6

Dòng 2…𝑁+1: mỗi dòng ghi một số nguyên dương, kích thước file input không vượt quá 1𝑀𝐵.
Kết quả
Dòng 1…𝑁: mỗi dòng ghi xâu “Yes” hay “No” là câu trả lời cho các số tương ứng trong input.
Ví dụ
Input
Output

3
1
2
4
Yes
Yes
No


Cặp ô lớn nhất (PLUMB)
Cho bảng số nguyên không âm kích thước 𝑀×𝑁, các hàng đánh số 1…𝑀 từ trên xuống dưới, các cột đánh số 1…𝑁 từ trái sang phải. Hãy xác định số nguyên dương lớn nhất thỏa mãn: trong bảng tồn tại hai ô kề cạnh cùng chứa số đó.
Dữ liệu
Dòng 1: hai số nguyên 𝑀, 𝑁
2≤𝑀, 𝑁≤50

Dòng 2…𝑀+1: mỗi dòng 𝑁 số nguyên trong phạm vi 0
10
6, số thứ 𝑗 trên dòng 𝑖+1 là số ở ô giao của hàng 𝑖 với cột 𝑗 của bảng.
Kết quả
Dòng 1: số nguyên dương tìm được, dữ liệu đảm bảo số này tồn tại.
Ví dụ
plumb.inp
plumb.out

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


Xây dựng dãy số (BUILDSEQ)
Bờm xây dựng một dãy số nguyên không âm 𝑁 phần tử theo quy trình:
Bắt đầu từ dãy gồm 𝑁 phần tử 0
Thực hiện lần lượt 𝑀 thao tác gia tăng phần tử, thao tác 𝑖 tăng các phần tử có chỉ số trong đoạn
𝑙
𝑖
𝑟
𝑖 lên một đơn vị.
Sau khi lập xong danh sách 𝑀 thao tác, Bờm nhận ra rằng một dãy số chỉ được coi là đẹp nếu với mọi chỉ số 𝑖, phần tử thứ 𝑖 có giá trị không vượt quá
𝑎
𝑖.
Để dãy số xây dựng được là đẹp, Bờm quyết định loại bỏ một số thao tác. Bờm nhờ bạn xác định xem số thao tác ít nhất cần loại bỏ là bao nhiêu.
Dữ liệu
Dòng 1: số nguyên 𝑁
1≤𝑁
10
5

Dòng 2: 𝑁 số nguyên
𝑎
1
𝑎
2
𝑎
𝑁
1
𝑎
𝑖
10
5

Dòng 3: số nguyên 𝑀
1≤𝑀
10
5

Dòng 4…𝑀+3: dòng 𝑖+3 ghi hai số nguyên
𝑙
𝑖
𝑟
𝑖
1
𝑙
𝑖
𝑟
𝑖≤𝑁

Kết quả
Dòng 1: số nguyên là số thao tác cần loại bỏ ít nhất.
Ví dụ
buildseq.inp
buildseq.out

4
3 4 4 2
4
3 4
4 4
1 1
3 4
1

Giải thích: sử dụng cả 4 thao tác tăng thu được dãy (1;0;2;3để dãy trở thành dãy đẹp chỉ cần loại bỏ một thao tác, chẳng hạn thao tác (4;4