Bài viết mới
Video mới
Đề thi olimpic tin học sinh viên lần thứ XV khối Đồng đội không chuyên

image

OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XV, 2006 Khối thi: Đồng đội không chuyên

Thời gian làm bài: 180 phút

Ngày thi: 07-05-2006

Nơi thi:  TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

Tên bài

Tên file

chương trình

Tên file

dữ  liệu

Tên file

kết quả

Hạn chế  thời gian cho mỗi test

Tổng điểm

cho bài

Tính điểm

SCORE.EXE

SCORE.INP

SCORE.OUT

2 giây

20

Phân phòng ở

ROOM.EXE

ROOM.INP

ROOM.OUT

5 giây

30

Nhà  hóa học

GOLD.EXE

GOLD.INP

GOLD.OUT

2 giây

30

Sơn hàng rào

PAINT.EXE

PAINT.INP

PAINT.OUT

2 giây

20

Hãy lập trình giải các bài sau đây: Bài 1. Tính điểm

Trong kỳ thi vấn  đáp học sinh phải trả lời các câu hỏi của thầy giáo. Nếu trả lời đúng, thầy giáo đánh dấu bằng ký tự ‘C’ (Correct), nếu sai thì đánh dấu ‘N’ (No Correct). Khi học sinh trả lời đúng, thầy sẽ đưa ra câu hỏi tiếp theo khó hơn câu trước, còn khi trả lời sai thầy sẽ cho câu hỏi mới dễ hơn. Sau khi thi xong, kết quả của mỗi học sinh là một xâu các ký tự ‘C’ và ‘N’. Điểm số của học sinh sẽ được tính như sau: Với các câu trả lời sai học sinh không được điểm, với mỗi câu trả lời đúng học sinh nhận được điểm bằng số lần trả lời đúng liên tiếp từ câu trả lời này trở về trước. Ví dụ, nếu kết quả là ‘CCNNCNNCCC’, thì điểm số sẽ là 1+2+0+1+0+0+1+2+3 = 10.

Yêu cầu: Cho xâu kết quả độ dài không quá 1000, hãy tính điểm của học sinh.

Dữ liệu: Vào từ file văn bản SCORE.INP chứa một xâu kết quả thi.

Kết quả: Đưa ra file văn bản SCORE.OUT điểm số của kết quả thi.

Ví dụ:

SCORE.INP

 

SCORE.OUT

CCNNCNNCCC

  10

Bài 2. Phân phòng ở Một nhóm N nhà tỷ phú tổ chức đi đánh golf. Tại địa điểm đánh golf có một dãy các ngôi nhà nghỉ nằm trên một địa thế sông núi rất hùng vĩ, có ngôi nhà thì cạnh sông, có ngôi nhà thì cạnh núi ... Mỗi ngôi nhà chỉ ở được một người. Đây cũng chính là lý do khiến các nhà tỷ phú không sao thỏa thuận được người nào sẽ ở ngôi nhà nào. Để giải quyết bế tắc và chiều lòng các tỷ phú, giám đốc khu nghỉ mát quyết định sử dụng M ngôi nhà liền nhau, đánh số từ 1 đến M, để các nhà tỷ phú lấy ra N phòng trong đó. Nhà tỷ phú thứ i trong nhóm sẽ sử dụng số chứng minh thư Si của mình (không có hai nhà tỷ phú nào có cùng số chứng minh thư) để chọn ra được ngôi nhà mình sẽ ở. Thao tác chọn sẽ như sau:

  • Nhà t phú đó s bt đu đếm t ngôi nhà đánh s 1,
  • Dng li ngôi nhà tương ng vi s chng minh thư ca mình,
  • Nếu đếm đến ngôi nhà đánh s M thì li tiếp tc đếm t ngôi nhà đánh s 1.

Yêu cầu: Hãy giúp giám đốc khu nghỉ mát tìm ra số M bé nhất để không có hai nhà tỷ phú nào chọn cùng một ngôi nhà theo các thao tác vừa nêu ở trên.

Dữ liệu: Vào từ file văn bản ROOM.INP theo qui cách như sau:

    • Dòng th nht ghi s nguyên dương N (1£ N £300) là s các nhà t phú đi đánh golf.
    • Dòng th hai ghi N s Si (1£ Si £ 1000000) (i=1..N) cách nhau bi du cách, tương ng là s chng minh thư ca N nhà t phú.

Kết quả: Ghi ra file văn bản ROOM.OUT một số nguyên M, là số lượng phòng ít nhất giám đốc khu nghỉ mát phải sử dụng ứng với dữ liệu vào đã cho.

Ví dụ:

ROOM.INP

  ROOM.OUT
2 4 6   3

Bài 3. Nhà hóa học

Trên mảnh đất thần thoại của Alice, các chất hóa học có thể kết hợp với nhau để sinh ra các chất khác, ví dụ kết hợp sắt với nước để sinh ra vàng. Có 26 chất hóa học được ký hiệu từ A đến Z và N phản ứng hóa học có thể sử dụng được đánh số từ 1 đến N (1£ N £100). Mỗi phản ứng kết hợp đều có chung một dạng - có hai chất tham gia phản ứng và nhận được hai chất sau phản ứng, ví dụ:

A + B sinh ra C + B

Lưu ý, do các phản ứng từ 1 đến N được thực hiện dưới các N điều kiện khác nhau, có thể tồn tại 2 phản ứng với cùng hai chất tham gia phản ứng nhưng nhận được 2 chất sau phản ứng khác nhau. Ví dụ, phản ứng thứ i:

A + B sinh ra C + B,

phản ứng thứ j:

A + B sinh ra E + F

Một tên nhà giàu tham lam nhưng rất dốt hóa học muốn biến 4 chất hắn có thành vàng (ký hiệu là V). Hắn bắt cóc một nhà hóa học và bắt nhà hóa học này thực hiện lòng tham của hắn.

Yêu cầu: Hãy giúp nhà hóa học đưa ra các phản ứng kết hợp để tạo ra vàng. Nếu không thể tìm ra quá trình đó hãy thông báo là không thể tạo ra vàng.

Dữ liệu: Vào từ file văn bản GOLD.INP theo qui cách như sau:

    • Dòng th nht ghi s nguyên dương N, là s phn ng kết hp có th s dng.
    • Dòng th i trong N dòng tiếp theo mô t phn ng th i gm bn ch cái, 2 ch cái đu là tên 2 cht tham gia phn ng, 2 ch cái sau là tên 2 cht đưc to ra sau phn ng đó. Các ch cái ghi cách nhau bi du cách.
    • Dòng cui cùng ghi bn ch cái, là tên ca bn cht tên nhà giàu có ban đu.

Kết quả: Đưa ra trên file văn bản GOLD.OUT. Dòng đầu tiên ghi số lượng các phản ứng nhà hóa học sẽ sử dụng để tạo ra vàng. Dòng thứ hai ghi ra số hiệu các phản ứng theo thứ tự được sử dụng, cách nhau bởi dấu cách. Nếu không tồn tại một qui trình, hãy ghi ra một số nguyên duy nhất -1.

Ví dụ:

GOLD.INP

 

GOLD.OUT

2

A B C D

C D C V

A B X Y

 

2

1 2

GOLD.INP

 

GOLD.OUT

2

A B C D

C D E F

A B X Y

 

-1

Bài 4. Sơn hàng rào

Bạn Tôm Xôi-ơ trong truyện “những cuộc phiêu lưu của Tôm Xôi-ơ” dụ dỗ các bạn mình sơn hàng rào thay như một công việc rất thú vị. Hàng rào dài M mét và có N người bạn của Tôm Xôi-ơ tham gia sơn hàng rào, được đánh số từ 1 đến N. Người bạn thứ i của Tôm Xôi-ơ ngẫu nhiên sơn được một đoạn hàng rào [Di, Ci] (với Di và Ci là khoảng cách từ điểm đầu và điểm cuối của đoạn được sơn đến đầu của hàng rào.

Yêu cầu: Hãy kiểm tra xem các bạn của Tôm Xôi-ơ có sơn được hết cả hàng rào không.

Dữ liệu: Vào từ file văn bản PAINT.INP theo qui cách như sau:

    • Dòng th nht ghi hai s nguyên dương M (1£ M £1000000) và N (1£ N £10000).
    • Dòng th i trong N dòng tiếp theo ghi hai s nguyên Di và Ci (0£ Di < Ci £M).

Kết quả: Đưa ra file văn bản PAINT.OUT. Nếu các bạn của Tôm Xôi-ơ sơn được hết cả hàng rào in ra “co”, nếu không, in ra “khong”.

Ví dụ:

PAINT.INP

 

PAINT.OUT

10 2

0 5

5 10

 

Co

GOLD.INP

 

GOLD.OUT

10 2

0 5

6 10

 

Khong

Tin cùng chuyên mục