Trang 1 - đề thi gồm có 2 trang ..
Sở Giáo dục và Đào tạo
LONG AN
Bảng C – THPT
ĐỀ CHÍNH THỨC
Kỳ thi Tin học trẻ tỉnh Long An lần thứ 17
Ngày thi : 17/3/2013
Thời gian: 150 phút (không kể phát đề)
Lưu ý: Thí sinh tạo thư mục là số báo danh của mình, làm bài và lưu với tên tập tin là
bai1.pas, bai2.pas, bai3.pas vào thư mục số báo danh vừa tạo. Ví dụ thí sinh có số báo danh
B52 thì tạo thư mục B52 rồi lưu bai1.pas, bai2.pas, bai3.pas vào thư mục B52.
Bài 1: (6 điểm)
Một xâu chữ cái được gọi là xâu số nếu sau khi xoá một vài kí tự ta thu được một trong
các xâu sau: ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT hoặc NINE.
Các xâu ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE được gọi
là các từ số (tương ứng với các số nguyên 1, 2, 3, 4, 5, 6, 7, 8, 9).
Ví dụ:
BOUNCE và ANNOUNCE là hai xâu số vì hai xâu này có chứa từ số ONE.
ENCODE không phải là xâu số, vì dù có chứa các kí tự O, N và E, nhưng vị trí các kí tự O,
N và E trong xâu này không đúng thứ tự.
Yêu cầu:
Viết chương trình kiểm tra một xâu kí tự chữ cái in hoa được nhập vào từ bàn phím xem
có phải là xâu số hay không. Nếu xâu được nhập vào là xâu số thì xuất ra màn hình một số
nguyên tương ứng với từ số chứa trong xâu này. Nếu xâu được nhập vào không phải là xâu số thì
xuất ra màn hình “KHONG”.
Ví dụ:
D
ữ liệu nhập v
à
o t
ừ b
àn phím
D
àn hình
BOUNCE 1
ENCODE KHONG
Bài 2: (7 điểm)
Một dãy số nguyên A: a1, a2,..., aN được gọi là dãy chia hết hoàn toàn nếu A có ít nhất 2
phần tử và mọi phần tử aj đều chia hết cho tất cả các phần tử ai đứng trước nó (1 ≤ i < j ≤ N).
Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự.
Yêu cầu: Viết chương trình nhập vào một dãy số nguyên A: a1, a2,..., aN. Tìm dãy con chia hết
hoàn toàn của A có độ dài lớn nhất.
Ví dụ 1: Dãy A: 3, 5, 9, 7, 15, 18, 35, 54. Dãy con chia hết hoàn toàn dài nhất là: 3, 9, 18, 54.
Ví dụ 2: Dãy A: 6, 9, 15. Không tìm được dãy con chia hết hoàn toàn.
Dữ liệu vào: Cho trong file văn bản MULSEQ.IN gồm 2 dòng:
Dòng đầu tiên chứa số nguyên dương N (1 ≤ n ≤ 5000), là số lượng phần tử của dãy A.
Dòng thứ hai gồm N số nguyên a1, a2,..., aN ( -10000 ≤ ai ≤ 10000), các số được viết
cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra file văn bản MULSEQ.OU:
- Nếu tìm được dãy con chia hết hoàn toàn thì file MULSEQ.OU gồm 2 dòng:
o Dòng đầu ghi độ dài của dãy con chia hết hoàn toàn dài nhất tìm được.
o Dòng thứ hai ghi các phần tử được chọn vào dãy con này.
- Nếu không tìm được dãy con chia hết hoàn toàn thì file MULSEQ.OU ghi số -1.
Ví dụ 1 Ví dụ 2
MULSEQ.IN MULSEQ.OU
MULSEQ.IN MULSEQ.OU
8
3 5 9 7 15 18 35 54
4
3 9 18 54
3
6 9 15
-1
Trang 2 - đề thi gồm có 2 trang ..
Bài 3: (7 điểm)
Có M đoàn học sinh của các trường đến tham dự kì thi THT2013. Các trưởng đoàn đang
xếp hàng tại khu vực nhà chờ để chờ đến lượt làm thủ tục đăng kí dự thi cho đoàn của trường
mình. Có N bàn làm thủ tục đăng kí dự thi tại khu vực tiếp tân. Nhân viên tại bàn thứ k mất Tk
giây để hoàn thành thủ tục đăng kí cho một đoàn bất kì. Bắt đầu giờ làm việc (tại thời điểm 0),
tất cả các bàn đều có nhân viên trực sẵn sàng làm thủ tục và các trưởng đoàn đã xếp thành một
hàng dọc tại khu vực nhà chờ. Một người chỉ có thể đến một bàn đang rỗi để làm thủ tục khi tất
cả người phía trước mình trong hàng đợi đã rời khỏi hàng (có thể đang làm thủ tục ở một bàn nào
đó hoặc đã làm xong thủ tục). Người ở đầu hàng đợi có thể chọn đến làm thủ tục tại một trong
các bàn đang rỗi hoặc chờ một bàn đang bận cho đến khi nó rỗi.
Tổng thời gian hoàn thành việc đăng kí cho tất cả các đoàn chính là khoảng thời gian từ
thời điểm bắt đầu làm việc đến thời điểm trưởng đoàn cuối cùng làm xong thủ tục dự thi. Thật
tuyệt vời là tất cả các trưởng đoàn đều là những chuyên gia tin học, vì vậy họ đều chọn đến làm
thủ tục tại những bàn sao cho thời gian hoàn thành đăng kí dự thi cho tất cả các đoàn là ít nhất.
Nhiệm vụ của bạn là giúp ban tổ chức tìm ra tổng thời gian ít nhất này (có thể xem thời
gian di chuyển từ nhà chờ đến khu vực tiếp tân không đáng kể).
Ví dụ: Có 6 đoàn và 2 bàn đăng kí dự thi với thời gian xử lí công việc là 7 giây và 10 giây.
Tại thời điểm 0, hai trưởng đoàn đến đăng kí tại hai bàn.
Tại thời điểm 7, bàn thứ nhất rỗi và trưởng đoàn thứ 3 đến làm thủ tục tại bàn này.
Tại thời điểm 10, trưởng đoàn thứ 4 đến bàn thứ hai.
Tại thời điểm 14, trưởng đoàn thứ 5 đến làm thủ tục tại bàn thứ nhất.
Tại thời điểm 20, bàn thứ 2 rỗi, nhưng trưởng đoàn thứ 6 quyết định chờ đến thời điểm
21, đến bàn thứ nhất làm thủ tục.
Theo cách này, thời gian hoàn thành thủ tục đăng kí cho tất cả các đoàn là 28 giây (Nếu
trưởng đoàn thứ 6 không chờ mà quyết định đến bàn thứ nhất ở thời điểm 20 thì thời gian hoàn
thành thủ tục đăng kí cho tất cả các đoàn là 30 giây).
Dữ liệu vào: Cho trong file văn bản MOMENT.IN gồm N+1 dòng:
Dòng đầu tiên chứa 2 số nguyên dương N (1≤ N ≤ 100 000) – số bàn làm thủ tục đăng kí
và M (1≤M≤1 000 000 000)- số đoàn tham dự kì thi.
N dòng tiếp theo, mỗi dòng gồm một số nguyên dương Tk – thời gian hoàn thành thủ tục
đăng kí cho một đoàn học sinh của từng bàn (1 ≤ Tk ≤ 109, các số được viết cách nhau ít
nhất một dấu cách.)
Dữ liệu ra: Ghi ra màn hình một số nguyên duy nhất, là thời gian (tính bằng giây) ít nhất hoàn
thành việc đăng kí cho tất cả các đoàn.
Ví dụ 1: Ví dụ 2:
Dữ liệu vào
2 6
7
10
Dữ liệu vào
7 10
3
8
3
6
9
2
4
Dữ liệu ra
28
Dữ liệu ra
8
------------HẾT------------
(Giám thị coi thi không giải thích gì thêm)
.
Sở Giáo dục và Đào tạo
LONG AN
Bảng C – THPT
ĐỀ CHÍNH THỨC
Kỳ thi Tin học trẻ tỉnh Long An lần thứ 17
Ngày thi : 17/3/2013
Thời gian: 150 phút (không kể phát đề)
HƯỚNG DẪN CHẤM
Câu 1: (6 đ) Nhập được chuỗi cho 1 điểm
D
ữ
li
ệu v
ào
D
ữ liệu ra
Đi
ểm
EIGHT 8 1,0
EXERCISE KHONG 1,0
DRIFTWOOD 2 1,0
SERVICEMAN 7 1,0
INSIGNIFICANCE
9
1,0
Bài 2: (7 điểm) Nhập dữ liệu được 1.0 điểm
D
ữ liệu v
ào
D
ữ liệu ra
Đi
ểm
Dữ liệu cho trong tập tin MULSEQ.IN1 MULSEQ.OU1 1,0 + 0,5
D
ữ
li
ệ
u cho trong t
ậ
p tin MULSEQ.IN2
MULSEQ.OU2
1,0
+
0
,
5
Dữ liệu cho trong tập tin MULSEQ.IN3 MULSEQ.OU3 1,0 +0,5
Dữ liệu cho trong tập tin MULSEQ.IN4 -1 1,5
Bài 3: (7 điểm) Nhập dữ liệu được 1.0 điểm
D
ữ liệu v
ào
D
ữ liệu ra
Đi
ểm
Dữ liệu cho trong tập tin moment.in1 55 2,0
D
ữ liệu cho trong tập tin moment.in
2
1446
1,5
Dữ liệu cho trong tập tin moment.in4 77148156 1,5
D
ữ liệu cho trong tập tin moment.in
6
72115316
1,0
Lưu ý:
Giải quyết trường hợp đồng điểm: Giám khảo xem xét thuật giải của thí sinh để giải quyết
-----HẾT-----
Trang 1 - đề thi gồm có 2 trang ..
Sở Giáo dục và Đào tạo
LONG AN
Bảng C – THPT
ĐỀ CHÍNH THỨC
Kỳ thi Tin học trẻ tỉnh Long An lần thứ 17
Ngày thi : 17/3/2013
Thời gian: 150 phút (không kể phát đề)
Lưu ý: Thí sinh tạo thư mục là số báo danh của mình, làm bài và lưu với tên tập tin là
bai1.pas, bai2.pas, bai3.pas vào thư mục số báo danh vừa tạo. Ví dụ thí sinh có số báo danh
B52 thì tạo thư mục B52 rồi lưu bai1.pas, bai2.pas, bai3.pas vào thư mục B52.
Bài 1: (6 điểm)
Một xâu chữ cái được gọi là xâu số nếu sau khi xoá một vài kí tự ta thu được một trong
các xâu sau: ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT hoặc NINE.
Các xâu ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE được gọi
là các từ số (tương ứng với các số nguyên 1, 2, 3, 4, 5, 6, 7, 8, 9).
Ví dụ:
BOUNCE và ANNOUNCE là hai xâu số vì hai xâu này có chứa từ số ONE.
ENCODE không phải là xâu số, vì dù có chứa các kí tự O, N và E, nhưng vị trí các kí tự O,
N và E trong xâu này không đúng thứ tự.
Yêu cầu:
Viết chương trình kiểm tra một xâu kí tự chữ cái in hoa được nhập vào từ bàn phím xem
có phải là xâu số hay không. Nếu xâu được nhập vào là xâu số thì xuất ra màn hình một số
nguyên tương ứng với từ số chứa trong xâu này. Nếu xâu được nhập vào không phải là xâu số thì
xuất ra màn hình “KHONG”.
Ví dụ:
D
ữ liệu nhập v
à
o t
ừ b
àn phím
D
àn hình
BOUNCE 1
ENCODE KHONG
Bài 2: (7 điểm)
Một dãy số nguyên A: a1, a2,..., aN được gọi là dãy chia hết hoàn toàn nếu A có ít nhất 2
phần tử và mọi phần tử aj đều chia hết cho tất cả các phần tử ai đứng trước nó (1 ≤ i < j ≤ N).
Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự.
Yêu cầu: Viết chương trình nhập vào một dãy số nguyên A: a1, a2,..., aN. Tìm dãy con chia hết
hoàn toàn của A có độ dài lớn nhất.
Ví dụ 1: Dãy A: 3, 5, 9, 7, 15, 18, 35, 54. Dãy con chia hết hoàn toàn dài nhất là: 3, 9, 18, 54.
Ví dụ 2: Dãy A: 6, 9, 15. Không tìm được dãy con chia hết hoàn toàn.
Dữ liệu vào: Cho trong file văn bản MULSEQ.IN gồm 2 dòng:
Dòng đầu tiên chứa số nguyên dương N (1 ≤ n ≤ 5000), là số lượng phần tử của dãy A.
Dòng thứ hai gồm N số nguyên a1, a2,..., aN ( -10000 ≤ ai ≤ 10000), các số được viết
cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra file văn bản MULSEQ.OU:
- Nếu tìm được dãy con chia hết hoàn toàn thì file MULSEQ.OU gồm 2 dòng:
o Dòng đầu ghi độ dài của dãy con chia hết hoàn toàn dài nhất tìm được.
o Dòng thứ hai ghi các phần tử được chọn vào dãy con này.
- Nếu không tìm được dãy con chia hết hoàn toàn thì file MULSEQ.OU ghi số -1.
Ví dụ 1 Ví dụ 2
MULSEQ.IN MULSEQ.OU
MULSEQ.IN MULSEQ.OU
8
3 5 9 7 15 18 35 54
4
3 9 18 54
3
6 9 15
-1
Trang 2 - đề thi gồm có 2 trang ..
Bài 3: (7 điểm)
Có M đoàn học sinh của các trường đến tham dự kì thi THT2013. Các trưởng đoàn đang
xếp hàng tại khu vực nhà chờ để chờ đến lượt làm thủ tục đăng kí dự thi cho đoàn của trường
mình. Có N bàn làm thủ tục đăng kí dự thi tại khu vực tiếp tân. Nhân viên tại bàn thứ k mất Tk
giây để hoàn thành thủ tục đăng kí cho một đoàn bất kì. Bắt đầu giờ làm việc (tại thời điểm 0),
tất cả các bàn đều có nhân viên trực sẵn sàng làm thủ tục và các trưởng đoàn đã xếp thành một
hàng dọc tại khu vực nhà chờ. Một người chỉ có thể đến một bàn đang rỗi để làm thủ tục khi tất
cả người phía trước mình trong hàng đợi đã rời khỏi hàng (có thể đang làm thủ tục ở một bàn nào
đó hoặc đã làm xong thủ tục). Người ở đầu hàng đợi có thể chọn đến làm thủ tục tại một trong
các bàn đang rỗi hoặc chờ một bàn đang bận cho đến khi nó rỗi.
Tổng thời gian hoàn thành việc đăng kí cho tất cả các đoàn chính là khoảng thời gian từ
thời điểm bắt đầu làm việc đến thời điểm trưởng đoàn cuối cùng làm xong thủ tục dự thi. Thật
tuyệt vời là tất cả các trưởng đoàn đều là những chuyên gia tin học, vì vậy họ đều chọn đến làm
thủ tục tại những bàn sao cho thời gian hoàn thành đăng kí dự thi cho tất cả các đoàn là ít nhất.
Nhiệm vụ của bạn là giúp ban tổ chức tìm ra tổng thời gian ít nhất này (có thể xem thời
gian di chuyển từ nhà chờ đến khu vực tiếp tân không đáng kể).
Ví dụ: Có 6 đoàn và 2 bàn đăng kí dự thi với thời gian xử lí công việc là 7 giây và 10 giây.
Tại thời điểm 0, hai trưởng đoàn đến đăng kí tại hai bàn.
Tại thời điểm 7, bàn thứ nhất rỗi và trưởng đoàn thứ 3 đến làm thủ tục tại bàn này.
Tại thời điểm 10, trưởng đoàn thứ 4 đến bàn thứ hai.
Tại thời điểm 14, trưởng đoàn thứ 5 đến làm thủ tục tại bàn thứ nhất.
Tại thời điểm 20, bàn thứ 2 rỗi, nhưng trưởng đoàn thứ 6 quyết định chờ đến thời điểm
21, đến bàn thứ nhất làm thủ tục.
Theo cách này, thời gian hoàn thành thủ tục đăng kí cho tất cả các đoàn là 28 giây (Nếu
trưởng đoàn thứ 6 không chờ mà quyết định đến bàn thứ nhất ở thời điểm 20 thì thời gian hoàn
thành thủ tục đăng kí cho tất cả các đoàn là 30 giây).
Dữ liệu vào: Cho trong file văn bản MOMENT.IN gồm N+1 dòng:
Dòng đầu tiên chứa 2 số nguyên dương N (1≤ N ≤ 100 000) – số bàn làm thủ tục đăng kí
và M (1≤M≤1 000 000 000)- số đoàn tham dự kì thi.
N dòng tiếp theo, mỗi dòng gồm một số nguyên dương Tk – thời gian hoàn thành thủ tục
đăng kí cho một đoàn học sinh của từng bàn (1 ≤ Tk ≤ 109, các số được viết cách nhau ít
nhất một dấu cách.)
Dữ liệu ra: Ghi ra màn hình một số nguyên duy nhất, là thời gian (tính bằng giây) ít nhất hoàn
thành việc đăng kí cho tất cả các đoàn.
Ví dụ 1: Ví dụ 2:
Dữ liệu vào
2 6
7
10
Dữ liệu vào
7 10
3
8
3
6
9
2
4
Dữ liệu ra
28
Dữ liệu ra
8
------------HẾT------------
(Giám thị coi thi không giải thích gì thêm)