Thời gian: 150 phút (không kể thời gian giao đề)

Tổng quan bài thi

Bài 1. Trò chơi

            Nhân dịp lễ giáng sinh, công viên trung tâm tổ chức trò chơi "con số may mắn". Mỗi em nhỏ đến tham dự sẽ được phát một số nguyên dương. Công viên có một thiết bị quay số, mỗi lần quay sẽ tạo ngẫu nhiên một số nguyên dương có giá trị tuyệt đối không vượt quá 10⁴. Người dẫn chương trình sẽ thực hiện N lần quay số. Số nào xuất hiện nhiều nhất trong N lần quay được gọi là con số may mắn và em nhỏ nào có con số may mắn thì sẽ được phần thưởng.

Yêu cầu: Cho N con số xuất hiện trong N lần quay. Bạn hãy giúp người dẫn chương trình xác định số lần xuất hiện của con số may mắn.

Dữ liệu vào từ file văn bản Bai1.inp:

Kết quả ghi ra file văn bản Bai1.out: Là số lần xuất hiện của con số may mắn.

Ví dụ:

Bài 2. Xâu chung

            Xâu S được gọi là xâu con chung của xâu S1 và xâu S2 nếu xâu S là một dãy các ký tự liên tiếp trong S1 và cũng là dãy các ký tự liên tiếp trong S2.

Yêu cầu: Cho hai xâu kí tự S1 và S2 (có không quá 255 ký tự). Hãy tìm một xâu con chung S dài nhất của hai xâu S1 và S2. Ví dụ: S1 = ’Ky thi học sinh gioi Tinh môn Tin hoc’, S2 = ’hoc sinh gioi mon Tin hoc’ thì S = ‘hoc sinh gioi  '.

Dữ liệu vào từ file văn bản Bai2.inp:

Kết quả ghi ra file văn bản Bai2.out: Chỉ một số duy nhất là độ dài của xâu con chung dài nhất  S. (Nếu hai xâu S1, S2 không có kí tự nào chung thì ghi số 0).

Ví dụ:

Bài 3 . Dạng thập phân

Ngày nghỉ cuối tuần Nam rất muốn đi chơi công viên. Mẹ ra diều kiện nếu Nam biết cách chuyển một phân số sang dạng thập phân (hữu hạn hoặc vô hạn tuần hoàn) thì sẽ được đi chơi. Bạn hãy giúp bé Nam nhé.

Yêu cầu: Cho 2 số nguyên dương P và Q  (P, Q £ 10⁵). Hãy đưa ra dạng thập phân (hữu hạn hoặc vô hạn tuần hoàn) của phân số .

Dữ liệu vào từ file văn bản Bai3.inp: Chỉ một dòng duy nhất chứa 2 số nguyên dương P và Q. 

Kết quả ghi ra file văn bản Bai3.out: Là dạng thập phân của phân số  theo quy cách như các ví dụ dưới đây:

Task 5: Possible First Tiles (TILE) Bài4 : Lợp mái

You  are given a set of M (1 £ M £ 10) 5 ´ 5 square tiles.   They are  placed on an N ´ N (5 £ N £ 15) square table one at a time, with their edges parallel to the edges of the table.  Tiles placed later might partially cover tiles placed earlier.  After the last tile is placed on the table, the configuration can be represented by a top-view. For example, Top-view 1 denotes that tile A was placed after tile B on a 11 ´ 11 square table.            Cho M (1 £ M £ 10) viên ngói vuông 5 ´ 5, được lợp trên một mái nhà vuông nxn (5 £ N £ 15), lần lượt mỗi lần 1 viên, các cạnh của chúng song song với các cạnh của bảng. Viên ngói đặt sau có thể che một phần hoặc che cả viên ngói đặt trước đó. Sau khi viên ngói cuối cùng được đặt lên mái ta thu được một Mai_ngoi. Ví dụ, Mai_ngoi 1 biểu thị rằng viên ngói A được đặt sau viên ngói B trên một mái vuông 11 x 11.

The tiles are named with consecutive letters beginning from A.  For example, if there are 5 tiles, then they will be called A, B, C, D and E.  In a top-view, each position on the table is represented either by a “.” if that position is not covered or a letter which is the name of the tile that is top-most at that position.            Các viên ngói được đặt tên là chữ cái liên tiếp bắt đầu từ A (theo bảng chữ cái tiếng Anh). Ví dụ, nếu có 5 viên ngói thì chúng sẽ được gọi là A, B, C, D và E. Trong một Mai_ngoi, mỗi vị trí trên mái được ký hiệu bởi một dấu chấm "." nếu vị trí đó không bị phủ bởi một chữ cái là tên của viên ngói trên cùng tại vị trí đó.

If the given top-view is valid, it is possible to decide a set of tiles each of which might have been the very first tile that was placed on the table.  For example, consider Top-view 2.  It is possible that tile B or C or D is the first tile that was placed on the table. However, it is impossible that A is the first tile that was placed on the table.            Một Mai_ngoi là hợp lệ nếu có thể xác định được một tập các viên ngói mà một trong chúng có thể là viên đầu tiên đã được đặt lên mái. Ví dụ ở Mai_ngoi2, có thể viên ngói B hoặc C hoặc D là ngói đầu tiên đã được đặt lên mái, nhưng A không thể là viên ngói đầu tiên đã được đặt lên mái.

            There are two possible reasons that a top-view is invalid.  The first reason is that some tiles are not a 5 ´ 5 square.  For example, Top-view 3 is invalid: A is a 4 ´ 5 tile, the width of B exceeds 5, and C has a hole.  Any of these reasons is enough to conclude that this top-view is invalid. Một Mai_ngoi là không hợp lệ nếu xảy ra một trong hai điều sau:

            - Có viên ngói không phải là một hình vuông 5 x 5. Ví dụ  Mai_ngoi 3 là không hợp lệ vì có A là viên 4 x 5, hay chiều rộng của viên B vượt quá 5, hay viên C có một lỗ.

The second reason is that tiles could not have been placed one after another. It is impossible that the tiles in Top-view 4 were placed one at a time ¾ the four tiles are interlocking.  Hence, this top-view is invalid.            - Các viên ngói không được đặt theo lần lượt viên này sau viên kia. Ví dụ trong Mai_ngoi 4 được đặt một lúc 4 viên ngói lồng vào nhau. Do đó, Mai_ngoi4 là không hợp lệ.

5.1 RequirementsYêu cầu:Given a top-view, if it is invalid, you are to output the 2 letters “NO”.  Otherwise, you are to output the letters in ascending order of the tiles each of which might be the first tile. Cho một Mai_ngoi, nếu nó không hợp lệ thì đưa ra ‘NO’. Nếu hợp lệ thì đưa ra các chữ cái theo thứ tự tăng dần của các viên ngói mà mỗi một trong số đó có thể là  viên ngói đầu tiên.

5.2 Input File TILE.IN Dữ liệu vào từ file văn bản Bai4.inp:

5.3 Output File TILE.OUT Kết quả ghi ra file văn bản Bai4.out:

 Ví dụ:

--------------------------------------------------- Hết -----------------------------------------------------------

Lưu ý:

            - Các số trên cùng một dòng ghi cách nhau một dấu cách.

            - Ghi các bài với tên Bai1.pas, Bai2.pas, Bai3.pas, Bai4.pas.

            - Giám thị không giải thích gì thêm.