Đề thi chọn học sinh giỏi THPT cấp tỉnh môn Tin học - Năm học 2015-2016 - Sở GD&ĐT Ninh Bình (Đề 2) (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HỌC SINH GIỎI THPT 
Năm học 2015 – 2016
MÔN: TIN HỌC
Ngày thi 07/10/2015
(Thời gian 180 phút không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 03 trang
Tổng quan đề thi:
Câu
Chương trình
Dữ liệu vào
Dữ liệu ra
1- Máy bay
AIRPLANE.PAS
AIRPLANE.INP
AIRPLANE.OUT
2- Xếp bi 
BI.PAS
BI.INP
BI.OUT
3- Party
PARTY.PAS
PARTY.INP
PARTY.OUT
Câu 1 (7 điểm ): Máy bay.	
	Hôm nay Duy đang rất vui vì được đi cùng với các bạn của đội tuyển tin học Ninh Bình ra sân bay Nội Bài để bay vào Đà Nẵng tham gia kì thi chọn học sinh giỏi quốc gia. Sau một thời gian chờ đợi Duy thấy có lệnh thông báo lên máy bay. Duy nhận thấy rằng máy bay có một lối vào bằng một hành lang nằm ở chính giữa xuyên qua tất cả các hàng ghế của hành khách. Mọi người bước vào hành lang và tìm chỗ ngồi của họ. Mỗi người phải ngồi đúng hàng ghế của mình và lối vào máy bay bắt đầu từ hàng ghế đầu tiên phía trước. Hành khách bước vào máy bay lần lượt từng người, không có sự dừng lại không cần thiết. Khách đi bộ vào hành lang theo hướng ghế của mình và ở mỗi hàng ghế hành khách dừng lại đúng 1 giây (hoặc lâu hơn nếu phía trước họ là một hành khách khác) cho đến khi hành khách đến đúng hàng ghế của mình và hành khách dừng lại tại hàng ghế của mình được 5 giây (để cất, đặt hành lý). Trong mỗi giây trong hành lang, tại một hàng chỉ có thể có một hành khách. Duy tò mò muốn biết nếu mà xếp hàng như vậy thì liệu mọi người có kịp ổn định để máy bay cất cánh đúng giờ hay không?
	Yêu cầu: Em hãy viết chương trình tính thời gian cần thiết để tất cả hành khách ngồi vào ghế của họ. 
	Dữ liệu vào: File văn bản AIRPLANE.INP
Dòng đầu tiên ghi số nguyên N ( là số hành khách thỏa mãn 1 ≤ N ≤ 1000).
Dòng i+1 chứa số nguyên Ri là số hàng ghế mà ở đó hành khách thứ i phải ngồi 
(1≤ Ri ≤ 1000). Hành khách được đánh số từ 1 đến N và họ vào máy bay theo trật tự đó. Số lượng hành khách ngồi trên cùng một hàng là không có giới hạn. 
	Dữ liệu ra: File văn bản AIRPLANE.OUT là một số nguyên T (tính bằng giây), là thời gian cần thiết để tất cả hành khách ngồi vào ghế của họ. 
Ví dụ:
AIRPLANE.INP
AIRPLANE.OUT
4
4
4
1
5
19
Câu 2 (6 điểm): Xếp bi.
	Ninh đang rất vui vì hôm nay là ngày sinh nhật được bạn Bình tặng một thùng bi nhiều màu sắc. Ninh mang thùng bi ra để nghịch và phát hiện ra có thể dùng các viên bi này để xếp thành các khối có dạng hình tứ diện đều hoặc là hình tứ diện đều không có ngọn bằng cách xếp các viên bi thành một tam giác đều sau đó bỏ các viên bi khác vào các vị trí trũng xuống khi xếp các viên bi tạo thành lớp thứ 2 bên trênNinh đang loay hoay không biết rằng liệu có thể xếp được một khối như trên bằng toàn bộ số bi hiện có mà không thừa ra viên nào không? 
	Yêu cầu: Hãy giúp Ninh tìm ra câu trả lời là có thể xếp được hay không và nếu có thì có bao nhiêu cách xếp?
	Dữ liệu vào: File văn bản BI.INP chỉ chứa duy nhất một số nguyên N ( N< 2700000) là số lượng các viên bi trong thùng.
	Dữ liệu ra: File văn bản BI.OUT là số lượng các khối khác nhau có thể xếp được khi dùng đúng N viên bi hoặc ghi ra số 0 trong trường hợp không thể xếp được.
Ví dụ: 
BI.INP
BI.OUT
4
1
5
0
Câu 3 (7 điểm): Party.
	Một công ty có N nhân viên (kể cả giám đốc, 1 ≤ N ≤ 2000), công ty được tổ chức theo cấu trúc nhân sự như sau: Mỗi người đều có một người là cấp trên trực tiếp của mình và có thể có một số người là cấp dưới. Mỗi người lại có một khả năng nói chuyện hài hước khác nhau mà chúng ta gọi là độ vui vẻ (người thứ i có độ vui vẻ là hi , 0 ≤ hi ≤ 255 ). Ông giám đốc là người duy nhất không có cấp trên trực tiếp. Năm nay công ty ông được đón tiếp một đoàn khách nước ngoài đến thăm quan. Ông giám đốc muốn tổ chức một bữa tiệc đón tiếp có tổng độ vui vẻ của những người là nhân viên công ty ông đến dự lớn nhất nhưng nếu có một nhân viên nào đó đi dự thì sẽ không có cấp trên trực tiếp của anh ta (vì như vậy độ vui vẻ của anh ta sẽ không còn nữa). Đương nhiên là ông giám đốc phải có mặt. 
Yêu cầu: Hãy giúp ông giám đốc chọn ra những người đi dự tiệc để bữa tiệc diễn ra vui vẻ nhất mà vẫn thỏa mãn điều kiện trên.
Dữ liệu vào: File văn bản PARTY.INP.
Dòng đầu ghi số nguyên dương N.
Dòng thứ hai ghi N số h1, h2, , hn.
N-1 dòng tiếp theo mỗi dòng ghi 2 số L và K với ý nghĩa K là cấp trên trực tiếp của L.
Dữ liệu ra: File văn bản PARTY.OUT ghi số S là tổng độ vui vẻ lớn nhất có thể nhận được.
Ví dụ:
PARTY.INP
PARTY.OUT
7
1 1 1 1 1 1 1
2 1
3 1
4 2
6 2
5 3
7 3
5
HẾT
Họ và tên thí sinh :....................................................... Số báo danh .............................
Họ và tên, chữ ký: 	Giám thị 1:..........................................................................
Giám thị 2:..........................................................................