Tài liệu bồi dưỡng HSG môn Tin học 9 - Dãy con tăng dài nhất - Vũ Thị Thêm

Nội dung text: Tài liệu bồi dưỡng HSG môn Tin học 9 - Dãy con tăng dài nhất - Vũ Thị Thêm

1. b) ij<ij+1 c) k lớn nhất. Dữ liệu vào: file daycontang.inp có cấu trúc như sau: - Dòng thứ nhất ghi số n - Các dòng tiếp theo chứa dãy A1, A2, A3, , An mỗi dòng 10 số ( trừ dòng cuối cùng), các số cách nhau ít nhất một dấu cách. Dữ liệu ra có cấu trúc như sau: - Dòng thứ nhất ghi số k - Các dòng tiếp theo ghi k số Ai1, Ai2, , Aik các số cách nhau ít nhất một dấu cách. INP OUT 12 5 6 12 8 11 3 4 1 7 5 9 10 2 3 4 7 9 10 Hướng dẫn : Học sinh làm bài theo hướng dẫn của giáo viên - Xây dựng mảng T và D với ý nghĩa:
2. Sau đây là kết quả học sinh học sinh tự viết Bài viết của học sinh đội tuyển BÀI TẬP TƯƠNG TỰ CHO HỌC SINH TỰ LUYỆN Học sinh làm bài tương tự, nâng cao, phát triển
3. 2 3 1 2 8 3 10 Bài 3: Làm việc tập thể: Trong công ti X có N nhân viên rất xuất sắc. Tuy nhiên do tất cả đều quá giỏi và quá tự tin. Cứ khi nào hai nhân viên cùng làm việc với nhau thì hiệu suất gần như bằng không. Họ tốn thời gian vào việc tranh cãi và không quyết định được công việc gì. Mỗi nhân viên có giờ làm việc là một khoảng thời gian liên tiếp từ thời điểm ai đến thời điểm bi. Giờ làm việc của mỗi nhân viên là không thể thay đổi do đặc điểm công việc mà họ đảm trách và tính kì quặc của họ. Do các khoảng thời gian này không giống nhau hoàn toàn, có thể có những lúc chỉ có một nhân viên làm việc. Lúc này thì họ làm việc rất hiệu quả. Giám đốc muốn giữ lại một số nhân viên sao cho tổng thời gian làm việc hiệu quả là lớn nhất có thể. Dữ liệu: Vào từ tệp văn bản WORK.INP - Dòng đầu tiên ghi N là số nhân viên (1<=n<=104) - N dòng tiếp theo mỗi dòng ghi hai số ai và bi là thời điểm bắt đầu và kết thúc 9 làm việc của nhân viên I (0<=ai<=bi<=10 ) Kết quả: Ghi ra tệp văn bản WORK.OUT là một số nguyên duy nhất là tổng thời gian làm việc hiệu quả lớn nhất có thể. Ví dụ: WORK.INP WORK.OUT 7 1900 100 150 0 1000 900 1000 1800 2000 900 1800 272 314
4. Học sinh hào hứng luyện bài Bài 5: Supernumber.pas Cho dãy số nguyên A[1], A[2], , A[N] khác nhau đôi một (N <105, 1<=A[i]<=N). Số A[i] được gọi là một số đặc biệt đối với dãy số trên nếu A[i] thuộc ít nhất một dãy con tăng dài nhất của A. Yêu cầu tìm một số dặc biệt của dãy A. Dữ liệ vào từ file SPECIAN.INP : Dòng đầu là số T(1<=T<=10) là số bộ test; T nhóm dòng sau mỗi nhóm 2 dòng, dòng thứ nhất là số N, dòng thứ hai chứa N số nguyên từ số có thứ tự 1 đến số có thứ tự N. Kết quả ghi ra file SPECIAN.OUT Gồm T dòng, mỗi dòng ghi các số đặc biệt của bộ test tương ứng, theo giá trị tăng dần. Ví dụ SPECIAN.INP SPECIAN.OUT 2 6 7 1 2 3 4 5 6 1 2 3 7 4 5 6 5 5 1 2 3 4 5 1 4 3 2 5 Bài 6: Dãy con lồi :
5. - Dòng đầu là số thứ tự của ngày có giá vàng thấp nhất tìm được - Dòng thứ hai là giá vàng tại ngày đó. Ví dụ : ONDINH.INP ONDINH.OUT 10 6 9 3 6 4 5 8 3 4 6 1 6 Bài 8:Renting Tại thời điểm 0 ông chủ cho thuê máy tính nhận được đơn đặt hàng thuê sử dụng máy tính của N khách hàng. Các khách hàng được đánh số từ 1 đến N. Khách hàng thứ i cần sử dụng máy từ thời điểm di đến thời điểm ci (di và ci là các số nguyên và 0 < di < ci <= 1000000000) và sẽ trả tiền sử dụng máy tính là pi (pi nguyên, 0 < pi<=10000000). Bạn cần xác định xem ông chủ cần nhận phục vụ những khách hàng nào sao cho khoảng thời gian sử dụng máy tính của hai khách hàng được nhận phục vụ bất kì không được giao nhau và tổng tiền thu được từ phục vụ là lớn nhất. Dữ liệu vào: từ file văn bản RENTING.INP - Dòng đầu ghi số N ( 0 < N <= 1000) - Dòng thứ i trong N dòng tiếp theo ghi ba số di, ci, pi cách nhau bởi dấu trống, i=1,2, ,N. Kết quả ghi ra file văn bản RENTING.OUT - Dòng đầu tiên ghi hai số nguyên dương theo thứ tự là số lượng khách hàng nhận phục vụ và tổng số tiền thu được. - Dòng tiếp theo ghi chỉ số của các khách hàng được phục vụ.