SỞ GIÁO DỤC VÀ ĐÀO TẠO KÌ THI CHỌN HỌC SINH GIỎI
THÀNH PHỐ ĐÀ NẴNG TOÀN THÀNH PHỐ NĂM HỌC 2002-2003
----------------- ----------------------------------
Môn : Tin học
Lớp : 12 THPT (Vòng 2)
Thời gian : 180 phút (Không kể thời gian dò đề)
đề chính thức:
Bài 5: Giao hai dãy số.
Cho hai dãy số nguyên x
1
, x
2
, ...., xn và y
1
, y
2
, ...., yn tăng nghiêm ngặt (xi<xi
+1
,
yi<yi
+1
). Hãy đếm số lượng các phần tử trong dãy x xuất hiện trong dãy y.
Dữ liệu vào : cho ở file DAYSO.INP, gồm :
Dòng đầu chứa số n, các dòng tiếp theo chứa 2n số nguyên (n < 500000), trong đó n
số đầu là dãy x và n số còn lại là dãy y.
Kết quả : ghi ra file DAYSO.OUT chứa một số duy nhất là kết quả tìm được.
Ví dụ:
DAYSO.INP DAYSO.OUT
5 2
1 2 3 5 7
2 4 5 6 8

chứa một số nguyên dương.
Viết chương trình tìm đường đi nối từ ô (1,1) của lưới đến ô (N,N) sao cho tổng các số
trên đường đi là lớn nhất. Biết rằng mỗi lần di chuyển chỉ đi sang một ô bên phải hoặc
đi một ô xuống dưới.
Dổợ lióỷu vaỡo: Từ tập tin văn bản LUOI.INP gồm :
- Dòng đầu tiên là số nguyên dương N.
- N dòng còn lại : mỗi dòng gồm N số nguyên dương cách nhau bởi khoảng trắng là
các số trên lưới.
Kết quả: Đưa ra tập tin LUOI.OUT gồm :
- Dòng đầu tiên là số S : tổng lớn nhất các số trên đường đi từ ô (1,1) đến (N,N).
- Các dòng còn lại là 2 số xi,yi là tọa độ của lưới đi qua, tọa độ dòng ghi trước, tọa độ
cột ghi sau và cách nhau ít nhất một khoảng trắng.
Vi dụ :
Dữ liệu : Từ tập tin văn bản LUOI.INP gồm :
5
2 7 2 6 5
7 1 8 1 4
4 9 3 6 4
1 1 9 5 2
9 5 2 6 1
Kết quả : Ghi ở tập tin văn bản LUOI.OUT gồm :
46
1 1
2 1
3 1
3 2
3 3
4 3
4 4
5 4