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

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ụ:

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ư S_i 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ẽ bắt đầu đếm từ ngôi nhà đánh số 1,
• Dừng lại ở ngôi nhà tương ứng với số chứng minh thư của mình,
• Nếu đếm đến ngôi nhà đánh số M thì lại tiếp tục đế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ứ nhất 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ố S_i (1£ S_i £ 1000000) (i=1..N) cách nhau bởi dấu cách, tương ứng là số chứng minh thư của 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ụ:

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ứ nhất ghi số nguyên dương N, là số phản ứng kết hợp có thể sử dụng.
  • Dòng thứ i trong N dòng tiếp theo mô tả phản ứng thứ i gồm bốn chữ cái, 2 chữ cái đầu là tên 2 chất tham gia phản ứng, 2 chữ cái sau là tên 2 chất được tạo ra sau phản ứng đó. Các chữ cái ghi cách nhau bởi dấu cách.
  • Dòng cuối cùng ghi bốn chữ cái, là tên của bốn chất 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ụ:

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 [D_i, C_i] (với D_i và C_i 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ứ nhất 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 D_i và C_i (0£ D_i < C_i £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ụ: