Đề thi Olimpic

KỲ THI OLYMPIC TRUYỀN THỐNG 30/4

LẦN THỨ XIII TAI THA ̣ ̀NH PHỐ

HUẾ

ĐỀ

THI MÔN TIN HỌC

Thờ

i gian làm bà

i 180’

Khối 11

Tổng quan đề thi:

Tên bài Phân công công việc Khu vui chơi Xe buýt

File bài làm Bl1.pas Bl2.pas Bl3.pas

Dữ liệu vào CV.INP VC.INP XB.INP

Dữ liệu ra CV.OUT VC.OUT XB.OUT

Giới hạn 2giây 2giây 2giây

Chú ý: Bài thi được làm trên ngôn ngữ lập trình Turbo Pascal

Đề thi gồm có 3 trang

BÀI 1: Phân công công việc

Có n công việc (n ≤ 100) lần lượt được thực hiện trên 1 máy tính, mỗi việc đòi hỏi

đúng 1 giờ chạy trên máy. Với mỗi việc ta biết thời hạn chậm nhất có thể để hoàn thành

và tiền thù lao thu được nếu thực hiện đúng thời hạn.

Yêu cầu: Chỉ có 1 máy tính, bạn hãy đưa ra một kế hoạch thực hiện trên máy sao

cho tổng số tiền thù lao thu được là lớn nhất.

Chú ý: Bạn không nhất thiết phải hoàn thành tất cả các công việc trên.

Dữ liệu vào: Được ghi trong file: CV.INP có cấu trúc:

• Dòng đầu tiên chứa số nguyên dương n ≤ 100.

• N dòng tiếp theo mỗi dòng chứa cặp số nguyên dương ai , bi (i chạy từ 1 đến n)

mỗi số cách nhau một khoảng trắng. Với ai (1 ≤ ai ≤ 24) là thời hạn chậm nhất

có thể để hoàn thành công việc thứ i, bi (1 ≤ bi ≤ 10000) là tiền thù lao mà bạn

nhận được nếu bạn hoàn thành công việc thứ i trong thời hạn qui định.

Dữ liệu ra: Kết quả ghi vào file văn bản CV.OUT chỉ có một số là tổng số tiền thu

được.

Ví dụ:

CV.INP CV.OUT

5

2 100

1 20

1 30

4 40

2 50

190