Lớp 10 - Năm 2016 - Đề Thi

Đề thi Olympic Tin học 30/4 Năm học 2015-2016 Lớp 10

Hãy để lại mail ở phần Comment để nhận file Word

XẾP PHÒNG

Có n cuộc hội thảo (đánh số từ 1 tới n) đăng ký sử dụng phòng của khu nhà do bạn quản lý. Cuộc hội thảo thứ i bắt đầu ngay sau thời điểm s_i và kết thúc tại thời điểm f_i. Có thể hiểu thời gian cuộc hội thảo tứ i diễn ra là một khoảng (s_i, f_i] trên trục thời gian. Hãy bố trí các phòng phục vụ toàn bộ các cuộc hội thảo thỏa mãn các yêu cầu sau:

+ Tại mỗi thời điểm, mỗi phòng chỉ dùng cho một cuộc hội thảo. Hay nói cách khác, hai cuộc hội thảo chỉ có thể bố trí trong cùng một phòng nếu khoảng thời gian làm việc của chúng không giao nhau.

+ Số phòng cần huy động để phục vụ cho toàn bộ n cuộc hội thảo là ít nhất có thể.

Dữ liệu vào: Từ tệp văn bản ROOMS.INP

+ Dòng 1 chứa số nguyên dương n ≤10⁵

+ n dòng tiếp theo, dòng thứ i chứa hai số tự nhiên s_i, f_i. (s_ii

≤10⁵)

Kết quả: ghi ra tệp văn bản ROOMS.OUT

+ Dòng 1 ghi số lượng phòng cần huy động (k)

+ K dòng tiếp theo, dòng thứ j ghi chỉ số các cuộc hội thảo sẽ được tổ chức tại phòng thứ j trong k dãy phòng đã huy động

Ví dụ:

ROOMS.INP	ROOMS.OUT
4 0 2 2 4 1 3 3 5	2 1 2 3 4

KHUNG HÌNH CHỮ NHẬT

 Một tấm gỗ hình chữ nhật kích thước n x m được chia thành bảng gồm n x m  ô vuông đơn vị, các dòng của bảng được đánh số từ 1 tới n từ trên xuống dưới, các cột đánh số từ 1 tới m từ trái qua phải. Ô nằm trên dòng i, cột j gọi là ô (i,j). Tấm gỗ có vân hoa, tuy nhiên không được đều lắm. Tại ô (i,j) người ta đánh giá mức độ đẹp của ô này bởi số nguyên A_ij. Giá trị ô  càng lớn thì ô đó càng đẹp. Một số ô quá xấu giá trị tương ứng của ô này có âm.

       Anh Hữu là người rất mê đồ gỗ và đang cần một khung hình chữ nhật để có thể treo các Bằng khen và Huy chương mà mình đã nhận được trong suốt quá trình học và thi đấu cờ vua. Anh Hữu cần cắt ra một tấm gỗ hình chữ nhật với các cạnh song song với tấm gỗ ban đầu và chứa trọn một số ô đồng thời độ dài mỗi cạnh không nhỏ hơn 2. Các ô nằm trên cạnh của hình chữ nhật tạo thành phần khung của tấm bảng mà anh Hữu muốn treo những thành tích của mình (nếu còn chỗ). Bởi vậy anh Hữu còn mong muốn tổng độ đẹp  của các ô nằm trên cạnh của hình chữ nhật được chọn là lớn nhất.

Yêu cầu: Cho bảng A gồm n x m số nguyên, hãy giúp anh Hữu tìm giá trị  của hình chữ nhật có tổng các ô ở biên là lớn nhất.

Dữ liệu: Vào từ file văn bản MAXFRAME.INP trong đó:

·    Dòng đầu chứa hai số n và m

·    Dòng thứ n  trong  dòng tiếp theo chứa các số a_i1, a_i2, a_i3,…,a_im .

Kết quả: Ghi vào file văn bản MAXFRAME.OUT một số nguyên duy nhất

Ví dụ:

MAXFRAME.INP	MAXFRAME.OUT
2 3 1  2 1 3 -2 1	6
4 5  2  3  1 -10  1  2  0 -1  -5 -2 -1  0  2   1 -1  2 -1 -2  -4  3	8

Giới hạn:  N, m <= 400; |a_ij| <=10⁴

test - solution - code - đề (word)

back

XỔ SỐ ĐIỆN TOÁN

Có N người (đánh số từ 1 đến N) tham gia một đợt xổ số điện toán. Mỗi người nhận được một thẻ gồm M ô (đánh số từ 1 đến M). Người chơi được chọn K ô trong số các ô đã cho bằng cách đánh dấu các ô được chọn. Sau đó các thẻ này được đưa vào máy tính để xử lý.

Máy tính chọn ra K ô ngẫu nhiên (gọi là các ô kết quả) và chấm điểm từng thẻ dựa vào kết quả đã sinh. Cứ mỗi ô chọn đúng với ô kết quả thì thẻ chơi được tính 1 điểm. Giả thiết biết các ô chọn cũng như các điểm tương ứng của từng thẻ chơi, hãy xác định tất cả các kết quả có thể có mà máy sinh ra.

Dữ liệu vào: đọc từ file vănbản XOSO.INP gồm:

- Dòng đầu ghi các số N, M, K

- Dòng thứ i trongN dòng tiếp ghi thẻ chơi của người i gồm K+1 số: K số đầu là các số hiệu của các ô chọn, cuối cùng là điểm tương ứng.

Kết quả ra: ghi vào tệp văn bản XOSO.OUT, mỗi dòng là một kết quả gồm K số ghi số hiệu các ô mà máy đã sinh.

Ghi chú:

- Các số trên cùng mộtdòng trong các file vào/ ra, được ghi cách nhau ít nhất một dấu trắng.

- Giới hạn kích thước:N ≤ 100, M ≤50, K ≤10.

- Dữ liệu vào trong các test là hợp lệ và đảm bảo có ít nhất một đáp án. 

Ví dụ: 

XOSO.INP	XOSO.OUT
5 9 4 2 4 6 8 2 5 6 8 9 0 2 4 5 6 2 1 2 3 7 3 3 5 6 9 1	1 2 3 4 2 3 4 7

CUNG ĐIỆN

Nguồn: Olympic miền Nam-2011

Ở một vương quốc nọ có 1 vị vua và ông có N quý phi. Trên miếng đất hình vuông có kích thước NxN, nhà vua muốn xây dựng cho mỗi quý phi, mỗi người một cung điện (giả sử mỗi cung điện đều nằm trên một mảnh đất kích thước 1x1). Vấn đề là các quý phi này có tính ghen ghét nhau nên nhà vua không muốn các cung điện nhìn thấy nhau từ các hướng (ngang, dọc, chéo).Chi phí xây dựng các cung điện trên mỗi ô đất có thể có giá thành khác nhau. Nhà vua muốn xây dựng N cung điện với tổng chi phí thấp nhất.

Yêu cầu: Bạn hãy giúp nhà vua thực hiện công việc đó

Dữ liệu vào: Từ file văn bản CUNGDIEN.INP gồm N+1 dòng

- Dòng đầu chứa số N (1≤N≤16)

- N dòng sau, mỗi dòng chứa N số là chi phí xây dựng tại ô đất tương ứng (Chi phí xây dựng cung điện trong một ô có giá trị nguyên từ 1 đến 100). Mỗi số cách nhau ít nhất một khoảng trắng
Dữ liệu ra: Ghi ra file văn bản CUNGDIEN.OUT gồm một số duy nhất cho biết tổng chỉ phí thấp nhất cho việc xây dựng. Giả sử dữ liệu luôn có lời giải

Ví dụ:

CUNGDIEN.INP	CUNGDIEN.OUT
4 3 4 12 3 6 1 7 1 2 4 1 5 12 3 8 7	15

Giải thích: các ô được chọn là (1,2), (2,4), (3,1), (4,3)

GHÉP SỐ

Cho hai số tự nhiên A có N chữ số và B có M chữ số (2<=N,M<=100). Xét các số nguyên dương có các tính chất sau:

+ Có N + M chữ số

+ Có thể đánh dấu N chữ số trong C để các chữ số được đánh dấu (giữ nguyên trình tự xuất hiện trong C) tạo thành A và các chữ số không được đánh dấu (giữ nguyên trình tự) tạo thành B.

Yêu cầu: Hãy tìm số lớn nhất Cmax và số nhỏ nhất Cmin thoả mãn các điều kiện trên.

Dữ liệu vào: từ file văn bản NUM.INP, gồm 2 dòng:

+ Dòng đầu chứa số nguyên A.

+ Dòng thứ 2 chứa số nguyên B.

Kết quả: đưa ra file văn bản NUM.OUT 2 dòng:

+ Dòng đầu: chứa số nhỏ nhất Cmin tìm được

+ Dòng thứ 2: chứa số lớn nhất Cmax tìm được

Ví dụ:

NUM.INP	NUM.OUT
20 4181	204181 421810

HƯỚNG DẪN VIÊN DU LỊCH

Ông G là một hướng dẫn viên du lịch. Công việc của ông ta là hướng dẫn một vài “tua” du lịch từ thành phố này đến thành phố khác. Trên các thành phố này, có một vài con đường hai chiều được nối giữa chúng. Mỗi cặp thành phố có đường kết nối đều có dịch vụ xe buýt chỉ chạy giữa hai thành phố này và chạy theo đường nối trực tiếp giữa chúng. Mỗi dịch vụ xe buýt đều có một giới hạn lớn nhất lượng khách mà xe buýt có thể trở được. Ông G có một tấm bản đồ chỉ các thành phố và những con đường nối giữa chúng. Ngoài ra, ông ta cũng có thông tin về mỗi dịch vụ xe buýt giữa các thành phố. Ông hiểu rằng ông không thể đưa tất cả các khách du lịch đến thành phố thăm quan trong cùng một chuyến đi. Lấy ví dụ: Về bản đồ gồm 7 thành phố, mỗi cạnh được nối giữa các thành phố biểu thị những con đường và các số viết trên mỗi cạnh cho biết cho biết giới hạn hành khách của dịch vụ xe buýt chạy trên tuyến đường đó.

Bây giờ, nếu ông G muốn đưa 99 khách du lịch từ thành phố 1 đến thành phố 7. Ông ta sẽ phải yêu cầu ít nhất là 5 chuyến đi, và lộ trình ông ta nên đi là 1 – 2 – 4 – 7.

Nhưng, Ông G. nhận thấy là thật khó để tìm ra tất cả lộ trình tốt nhất để sao cho ông ta có thể đưa tất cả khách du lịch đến thành phố thăm quan với số chuyến đi là nhỏ nhất. Do vậy mà ông ta cần sự trợ giúp của các bạn.

Dữ liệu vào: từ tệp văn bản TOURIST.INP

- Dòng đầu tiên chứa hai số nguyên N (N ≤ 1000) và R mô tả lần lượt số thành phố và số đường đi giữa các thành phố.

- R dòng tiếp theo, mỗi dòng chứa 3 số nguyên: C1, C2, P. Trong đó C1, C2 mô tả lộ trình đường đi từ thành phố C1 đến thành phố C2 và P (P > 1) là giới hạn lớn nhất có thể phục vụ của dịch vụ xe buýt giữa hai thành phố.

Các thành phố được đánh dấu bằng một số nguyên từ 1 đến N. Dòng thứ (R+1) chứa ba số nguyên S, D, T mô tả lần lượt thành phố khởi hành, thành phố cần đến và số khách du lịch được phục vụ.

Kết quả ra: ghi vào tệp văn bản TOURIST.OUT

Ghi ra số lộ trình nhỏ nhất cần phải đi qua các thành phố thỏa mãn yêu cầu đề bài.

Ví dụ:

TOURIST.INP	TOURIST.OUT
7 10 1 2 30 1 3 15 1 4 10 2 4 25 2 5 60 3 4 40 3 6 20 4 7 35 5 7 20 6 7 30 1 7 99	5

TEST - CODE