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

QBBUILD

Nguồn: http://www.vn.spoj.com/problems/QBBUILD

Vua Peaceful vừa khai hoang một vùng đất để lập ra nước Peace, lúc đầu chỉ có N thành phố được đánh số từ 1 đến N và không có con đường nào

Vua Peace chọn ra 4 thành phố đặc biệt để làm trung tâm kinh tế và 4 thành phố này phải được liên thông với nhau. Chi phí xây dựng các con đường không phải nhỏ vì thế mà nhà cua muốn sử dụng chi phí ít nhất để xây dựng các con đường sao cho 4 thành phố đặc biệt đó vẫn liên thông

Bạn chỉ biết chi phí ước tính để xây dựng một số con đường và bạn hãy chọn ra một số con đường để xây dựng theo ý muốn của nhà vua biết rằng luôn luôn tồn tại ít nhất một phương án xây dựng sao cho 4 thành phố đặc biệt liên thông

Dữ liệu vào: từ file QBBUILD.INP

+ Dòng đầu tiên ghi số nguyên dương N là số lượng các thành phố (4≤N≤100)

+ Dòng thứ hai ghi 4 số nguyên là số hiệu của 4 thành phố đặc biệt

+ Trong các dòng tiếp theo mỗi dòng ghi 3 số nguyên dương u, v và c với ý nghĩa muốn xây dựng một con đường hai chiều nối trực tiếp hai thành phố u và v thì chi phí là c (1≤c≤5000);

Dữ liệu ra: ghi vào file QBBUILD.OUT gồm 1 dòng duy nhất là tổng chi phí nhỏ nhất để xây dựng hệ thống đường

Ví dụ:

QBBUILD.INP	QBBUILD.OUT
5 2 3 4 1 1 2 10 1 5 1 5 2 1 1 4 1 4 3 3 3 2 2	5

 TEST - CODE - SOLUTION

ÔNG NGÂU BÀ NGÂU

Hẳn các bạn đã biết ngày "ông Ngâu bà Ngâu" hàng năm, đó là một ngày đầy mưa và nước mắt. Tuy nhiên, một ngày trước đó, nhà Trời cho phép 2 "ông bà" được đoàn tụ. Trong vũ trụ vùng thiên hà nơi ông Ngâu bà Ngâu ngự trị có N hành tinh đánh số từ 1 đến N, ông ở hành tinh Adam (có số hiệu là S) và bà ở hành tinh Eva (có số hiệu là T). Họ cần tìm đến gặp nhau.

N hành tinh được nối với nhau bởi một hệ thống cầu vồng. Hai hành tinh bất kỳ chỉ có thể không có hoặc duy nhất một cầu vồng (hai chiều) nối giữa chúng. Họ luôn đi tới mục tiêu theo con đường ngắn nhất. Họ đi với tốc độ không đổi và nhanh hơn tốc độ ánh sáng. Điểm gặp mặt của họ chỉ có thể là tại một hành tinh thứ 3 nào đó.

Yêu cầu: Hãy tìm một hành tinh sao cho ông Ngâu và bà Ngâu cùng đến đó một lúc và thời gian đến là sớm nhất. Biết rằng, hai người có thể cùng đi qua một hành tinh nếu như họ đến hành tinh đó vào những thời điểm khác nhau.

Dữ liệu vào: từ tệp văn bản NGAU.INP gồm

Dòng đầu là 4 số N M S T (N ≤ 1000, 1 ≤ S ≠ T ≤ N), M là số cầu vồng. M dòng tiếp, mỗi dòng gồm ba số I J L thể hiện có cầu vồng nối giữa hai hành tinh I, J và cầu vồng có độ dài là L (1 ≤ I ≠ J ≤ N, 0 < L ≤ 200).

Dữ liệu ra: ghi vào tệp văn bản NGAU.OUT, nếu như không tồn tại hành tinh nào thoả mãn yêu cầu thì ghi ra một dòng chữ CRY. Nếu có nhiều hành tinh thoả mãn thì ghi ra hành tinh có chỉ số nhỏ nhất.

Ví dụ:

NGAU.INP	NGAU.OUT
4 4 1 4 1 2 1 2 4 1 1 3 2 3 4 2	2

 TEST

CHUỖI ỐC

Nguồn: PreVOI

Biển Đà Nẵng được nhiều du khách biết đến như một trong những điểm nghỉ ngơi lý tưởng và được tạp chí Forbes (Mỹ) bình chọn là một trong những bãi biển đẹp nhất thế giới. Các bãi tắm có độ dốc lớn, nước trong xanh thích hợp cho những du khách muốn thưởng thức những loại hình dịch vụ giải trí nghỉ dưỡng câu cá, lướt ván, lặn, ngắm san hô…

Trong một đợt đi du lịch ở Đà Nẵng, sáng sớm DONG3D thường đi dạo dọc bờ biển và nhặt những vỏ ốc rồi xâu chúng lại thành một chuỗi. Nguyên tắc tạo chuỗi ốc của DONG3D như sau: ban đầu chuỗi ốc rỗng, không có vỏ ốc, khi gặp một vỏ ốc mới có thể lấy để xâu vào 1 trong hai đầu của chuỗi hoặc bỏ đi không lấy, cuối cùng nhận được một chuỗi vỏ ốc mà tính từ đầu đến cuối chuỗi các vỏ ốc có kích thước tăng dần và gồm càng nhiều vỏ ốc càng tốt.

Yêu cầu: cho trước dãy a₁, a₂,…,a_N là kích thước các vỏ ốc mà DONG3D lần lượt gặp khi đi dọc bờ biển, hãy tìm cách nhặt và xâu chuỗi để được nhiều vỏ ốc nhất.

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

+ Dòng đầu tiên ghi số nguyên dương N≤10⁵

+ Dòng thứ 2 chứa N số nguyen dương a₁, a₂,…,a_N ("i:a_i≤10⁹)

Dữ liệu ra: ghi vào tệp văn bản BEADS.OUT một số nguyên duy nhất là số lượng vỏ ốc trong chuỗi tạo được.

Ví dụ:

BEADS.INP	BEADS.OUT
5 4 4 5 3 1	4

TEST - SOLUTION

QUAN HỆ HỌ HÀNG

DÂY DẪN

TÌM CHỮ SỐ

Xét biểu diễn thập phân của phân số a/b. Biểu diễn này có thể là một số thập phân hữu hạn hoặc một số thập phân vô hạn tuần hoàn. Nếu phân số có thể biểu diễn bởi một số thập phân hữu hạn, ta có thể viết thêm một dãy vô hạn các chữ số 0 vào sau chữ số cuối cùng sau dấu chấm thập phân và coi đó cũng là một số thập phân vô hạn tuần hoàn. Ví dụ:

Yêu cầu: Sau khi đánh số từ 1 trở đi, từ trái qua phải các chữ số đứng sau dấu “,” trong biểu diễn thập phân của a/b, hãy xác định chữ số thứ k.

Ví dụ:

+ Với a=100, b=8, k=2, chữ số đứng thứ 2 sau dấu thập phân của giá trị 100/8  là chữ số 0

+ Với a=99, b=140, k=12, chữ số đứng thứ 12 sau dấu chấm thập phân giá trị 99/140 là chữ số 2

Dữ liệu: Vào từ tệp văn bản DIGIT.INP gồm 1 dòng chứa 3 số nguyên dương a, b, k<= 10^18 cách nhau ít nhất một ký tự trắng.

Kết quả: Ghi ra tệp văn bản DIGIT.OUT một số nguyên duy nhất là giá trị chữ số tìm được

Ví dụ:

DIGIT.INP	DIGIT.OUT
100 8 1	5
17 3 10	6
99 140 12	2