5HẠN CHẾ KỸ THUẬT
17.5
Hạn chế kỹ thuật:
- Ghi tờn file bài làm là DIENTICH.PAS.
- Dữ liệu vào là chớnh xỏc khụng cần kiểm tra.
- Nếu khụng nhập được dữ liệu vào từ file, thớ sinh cú thể nhập dữ liệu vào từ bàn phớm
- Cú khoảng 60% số bộ test cú a < 100.
Bài II(10 điểm): DÃY SỐ.
Cho số nguyờn dương S và dóy số gồm N số nguyờn dương F
1
, F
2
, ..., F
N
. Dóy số đó
cho được gọi là dóy tăng dần nếu: F
i
≤ F
i+1
∀i
∈
{1
,
2
,...,
n
−
1
}( hay F
1
≤ F
2
≤ F
3
≤ ... ≤
F
N
).
Chỳng ta gọi hai số hạng F
i1
và F
i2
trong dóy đó cho (với i1 ≠ i2; i1,i2
∈
{1
,
2
,...,
n
}):
- Là một “cặp đụi xung khắc” nếu F
i1
+ F
i2
= S.
- Là một “cặp đụi lý tưởng” nếu chỳng cựng cú ba chữ số, cỏc chữ số của số hạng này
giống hệt của số hạng kia nhưng khỏc về thứ tự xuất hiện - vớ dụ 123 và 132 hay 121 và
211 là cỏc cặp đụi lý tưởng cũn 121 và 122 hay 457 và 457 thỡ khụng phải.
Yờu cầu: Cho biết S và dóy số F
1
, F
2
, ..., F
N
. Hóy xỏc định xem dóy đó cho cú phải dóy
tăng dần hay khụng, tớnh số cặp đụi xung khắc và tỡm một cặp đụi lý tưởng (nếu cú) trong
dóy đó cho.
Dữ liệu vào: Dữ liệu vào của bài toỏn được cho trong tệp tin DAYSO.INP với cấu
trỳc như sau:
- Dũng đầu tiờn gồm hai số N và S (N ≤ 50000, S <1000).
- Dũng thứ i trong N dũng tiếp theo chứa một số là số F
i
của dóy (F
i
< 500).
Dữ liệu ra: Kết quả ghi ra trờn màn hỡnh (hoặc ghi ra file DAYSO.OUT)bốn dũng:
- Dũng đầu ghi ba số N, S và F
N
.
- Dũng thứ hai ghi CO nếu dóy đó cho là dóy tăng dần, ghi KHONG nếu ngược lại.
- Dũng thứ ba ghi một số là số cặp đụi xung khắc trong dóy đó cho.
- Dũng thứ tư ghi hai số là một cặp đụi lý tưởng tỡm được trong dóy đó cho, nếu
khụng cú cặp đụi lý tưởng nào thỡ ghi hai số 0.
Vớ dụ:
DAYSO.INP
Kết quả trờn màn hỡnh (hoặc file DAYSO.OUT)
5 5
5 5 5
1
CO
2
3
0 0
4
5
10 111
10 111 101
110
KHONG
7
110 101
10
101