Đây là cuộc thi Olympiad Quốc tế môn
Tin học đầu tiên được tổ chức tại thành
phố Pravetz, Bulgaria từ ngày 16 đến
ngày 19 tháng 5 năm 1989

Bài toán 1
Cho trước 2*N hộp nằm cạnh nhau trên cùng một hàng với N <= 5. Trong đó có hai hộp
liền nhau trống rỗng, các hộp còn lại chứa N-1 vật "A" và N-1 vật "B".
Ví dụ, với N = 5 ta có như sau: Quy tắc trao đổi: Chuyển các vật trong hai hộp liền nhau chứa đồ vật sang hai hộp rỗng,
giữ nguyên vị trí các hộp.
Yêu cầu
Tìm cách hoán chuyển sao cho tất cả các hộp chứa vật A nằm bên trái các hộp chứa vật
B, không cần biết các hộp rỗng nằm ở đâu.
Bài toán đặt ra
Hãy viết chương trình:
1. Xây dựng mô hình hoán chuyển các hộp với số hộp và trạng thái ban đầu của các hộp
được nhập từ bàn phím. Mỗi hoán chuyển được nhập bằng số (thuộc từ 1 đến N-1) của
hai hộp liền nhau đầu tiên sẽ được đổi chỗ cho các hộp rỗng. Chương trình phải tìm và
báo cáo trạng thái các hộp sau khi hoán chuyển.
2. Cho trước hiện trạng các hộp, tìm ít nhất một cách hoán chuyển đạt mục tiêu cuối cùng
của bài toán. Chương trình phải báo cáo cả trạng thái ban đầu và trạng thái hiện tại sau
mỗi bước hoán chuyển.
3. Tìm những cách hoán chuyển để số hộp bị di chuyển ít nhất và vẫn đạt được mục đích.

Bài toán 2
Các tầng trong một tòa nhà được đánh số tuần tự từ 0, 1, 2, , N (N<=15). Trong tòa


Bài toán 3
Cho trước một nhóm N người. Mỗi người là bạn của hơn [N/2] người còn lại và là kẻ thù
của không quá K người. Một người có một cuốn sách mà tất cả mọi người đều muốn đọc
và thảo luận với một số người khác.
Hãy viết chương trình:
1. Tìm cách truyền tay nhau cuốn sách sao cho tất cả mọi người đều được đọc nó một
lần và chuyển nó cho bạn mình và cuối cùng cuốn sách về tay người chủ.
2. Chia nhóm người thành S tổ để thảo luận về cuốn sách. Mỗi người phải có không
quá P kẻ thù trong cùng tổ.
Giả sử S*P >= K.

Bài toán 4
Xét đoạn văn bản được soạn thảo bằng các ký tự viết hoa /A-Z/ và 8 ký tự . , + - : / ? !
Đoạn văn bản đó được gửi qua kênh giao tiếp dưới dạng chuỗi byte. Số ký tự 1 trong
mỗi byte phải là số chẵn.
1. Đưa ra cách mã hóa các ký tự trên bằng các chuỗi nhị phân sao cho cách mã hóa rõ
ràng và số bit được gửi qua kênh giao tiếp là ít nhất.
2. Hãy viết chương trình:
2.1. Cho trước đoạn văn bản, hãy in ra đoạn văn bản dưới dạng một chuỗi các số thập
lục phân.
2.2. Cho trước đoạn văn bản đã mã hóa nhận được, hãy giải mã và hiển thị đoạn văn
bản lên màn hình.

Bài toán 5
Xét một hình phẳng gồm n đỉnh, mỗi đỉnh đều bậc 3.
Ví dụ: Để các đỉnh X,Y và Z liền kề đỉnh T. Ta nói Y là đỉnh lân cận trái và Z là đỉnh lân cận

Vì tính phức tạp về thời gian và không gian của thuật toán nên bạn không cần tìm kết
quả chính xác mà chỉ cần đưa ra một kết quả tương đối.

Cuộc thi Olympiad Tin học Quốc tế
lần thứ hai được tổ chức tại
MINSK,BYELLORUSSIA năm 1990

Ngày thứ nhất

Bài toán 1. Hãy lập chương trình biến đổi bảng số trong hình A thành bảng số trong hình
B. Mỗi số trong một ô vuông có thể di chuyển đến một trong các ô trống khác; lúc này ô
vuông chứa số đó sẽ trở thành trống. Bài toán 2
Trò chơi với các hộp, yêu cầu người chơi nối các chấm trên lưới. Người chơi hoàn thành
một hộp sẽ ghi được 1 điểm và chuyển đến lượt người kia. Trò chơi kết thúc khi lưới
được hoàn thành và người thắng cuộc là người nhiều điểm hơn. Chỉ cho phép nối khoảng
cách giữa hai điểm theo hàng ngang và hàng dọc. Ví dụ dưới minh họa trò chơi giữa Red
và Blue mới được hoàn thành một nửa: Lưới trong trò chơi được minh họa bằng ký tự R và B chỉ các dòng tương ứng Red và
Blue điền được, còn số 0 chỉ dòng trống: Trò chơi được thu gọn lại dưới dạng một ma trận như sau:
ROBR
BRBBB
BBRR

< ENTER N > >
< ENTER K > >
< ENTER: >
< A[1] > > < B[1] > >
< A[2] > > < B[2] > >

< A[N] > > < B[N] > >
2. Hãy tìm thời gian T lớn nhất sao cho trước thời gian đó cả hai người đọc chưa đọc hết
tất cả các cuốn sách; dữ liệu ra t ính giá trị T.
3. Hãy xây dựng lịch trình đọc sách cho mỗi người thỏa mãn tất cả các ràng buộc trên và
quá trình đọc sách kết thúc ở thời gian T. Lịch trình đọc sách được định dạng như sau:
< Book > < Start > < Finish > Bảng trên chứa tất cả các thời gian trong khi người A (hoặc B) đọc sách và số cuốn sách
được đọc.
4. Đưa ra số lần giành quyền đọc sách của mỗi người. Hãy cố gắng giảm số lần giành
quyền đọc.

Bài toán 4
Cho trước số nguyên K. Một mảnh giấy được chia thành N ô (K<=N<=40). Hai người
chơi chọn và lấy đi lần lượt K ô giấy trống liền nhau. Người chiến thắng là người lấy đi ô
giấy cuối cùng.

1. Nhập giá trị N và xác định xem người chơi thứ nhất có chiến thắng được không. Đưa
ra thông báo "Player 1 has winning strategy" hoặc "Player 1 doesn't have winning
strategy". ('Người chơi thứ nhất có thể chiến thắng' hoặc 'Người chơi thứ nhất không thể
chiến thắng').
2. Với N cho trước, hãy xác định xem người chơi thứ nhất có thể chiến thắng không nếu
lần chọn đầu tiên của anh ta được nhập từ bàn phím.

<'PROLAN/M'-program> ::= <substitut.sequence>(,)
<substitut.sequence> ::= <substitution>:
::= <substitut.sequence><substitution>
<substitution> ::= (<left part>,<right part>)
<left-hand part> ::= <string>
<right-hand part> ::= <string>:<empty>
<string> ::= <string symbol>:<string><string symbol>
<empty string> ::=
<string symbol> ::= <any ASCII character except ',' , ')' >

Sau khi chuỗi dữ liệu được nhập vào R, chương trình được thực hiện như sau: bộ vi xử
lý tìm kiếm <substitution> đầu tiên trong <substitut.sequence> trong đó <left-hand part>
là chuỗi con của chuỗi trong R. Nếu tìm kiếm thành công, <right-hand part> của cùng
<substitution> sẽ thay thế chuỗi con tương ứng trong R (chuỗi tận cùng bên trái nếu kết
quả tìm kiếm không là duy nhất). Thủ tục này được lặp lại từ đầu với giá trị R mới đến
khi <left-hand part> trong <'PROLAN/M'-program> được tìm thấy là một chuỗi con với
giá trị R hiện tại, đây là kết quả cuối cùng và quá trình xử lý kết thúc.

Câu 1.
Hãy viết và sửa lỗi một chương trình PROLAN/M chuyển một chuỗi kiểu
<nat.nr1>+<nat.nr2>=?
(trong đó <nat.nr1> và <nat.nr2> là các chuỗi số thập phân hiện thân là các số tự nhiên)
thành một chuỗi kiểu <nat.nr1>+<nat.nr2>=<nat.nr3> chứa đựng phát biểu toán học đúng
(<nat.nr1> và <nat.nr2> như nhau). Ví dụ, chuỗi 1990+123=? được chuyển thành
1990+123=2113 sau quá trình xử lý. Lưu chương trình của bạn vào tệp SUM.PRM.

Câu 2.
Viết chương trình sửa lỗi theo ngôn ngữ PROLAN/M thực hiện nhiệm vụ sau:
(a) Lưu tên tệp văn bản theo ngôn ngữ PROLAN/M;
(b) Tìm nội dung ban đầu của R;

(b) Xác định tất cả các khoảng thời gian thiếu nhân viên bảo vệ (ít hơn 2 người đang làm
nhiệm vụ).
(c) Xác định số nhân viên bảo vệ cần bổ sung ít nhất làm nhiệm vụ trong một khoảng thời
gian bắt buộc theo chương trình bảo vệ, ví dụ, bổ xung nhân viên thỏa mãn điều kiện (a).

INPUT
(Tất cả thời gian đều là số nguyên tính bằng phút)
EndTime - thời điểm kết thúc nhiệm vụ canh gác, triển lãm cần canh gác trong khoảng
thời gian [0, EndTime].
N - số nhân viên bảo vệ.
T1[i]. T2[i], i=1, , N - thời gian bắt đầu và kết thúc ca trực của nhân viên thứ i.
Length - thời gian làm việc bắt buộc đối với một nhân viên bổ sung.

OUTPUT
(1) Câu trả lời cho yêu cầu (a) theo định dạng "Yes/No".
(2) Nếu câu trả lời trước là "no", hãy kiệt kê các cặp số (k,1) - chỉ thời gian bắt đầu và kết
thúc của tất cả các khoản thời gian thiếu nhân viên bảo vệ và số số nhân viên thiếu trong
mỗi khoảng thời gian đó (0 hoặc 1 người).
(3) Số nhân viên bổ sung và danh sách các thời gian bắt đầu và kết thúc trong khoảng
thời gian bắt buộc của mỗi nhân viên bổ sung. Bài toán 2
N đoạn được đặt trên mặt phẳng theo tọa độ các điểm cuối, N>0. Các điểm cuối của một
đoạn được biểu diễn bằng hai cặp (x1[i], y1[i]) và (x2[i], y2[i]), 1<=i<=N. Điểm cuối của
một đoạn bất kỳ đều thuộc đoạn đó. Hãy viết chương trình để:
1. Biểu diễn dữ liệu vào theo mẫu


<Vận tốc của robot 1:>
<Vị trí ban đầu của robot 1:>

<Vị trí ban đầu của robot 1:>
(Tất cả các số trên đều là số nguyên không âm)
Định dạng dữ liệu ra như sau:
<Thời gian = >
Bài toán 4
Tất cả các con phố của một thành phố dạng hình chữ nhật nằm trên một vùng không bằng
phẳng. Các con phố được ký hiệu từ Nam ngược lên Bắc (các phố N) hoặc từ Tây sang
Đông (các phố M), do đó thành phố được chia thành các ô vuông với kích thước đều
bằng 1. Các đoạn phố nằm giữa hai điểm giao liền nhau chỉ chạy theo xuống hoặc lên
hoặc có thể nằm ngang. Ma trận K[y,x] (kích thước M x N) chứa độ cao của các điểm
giao cắt so với mực nước biển.

Hãy viết chương trình thực hiện:
1. Nhập kích thước ma trận M và N.
2. Nhập các phần tử của ma trận H[i,j]; (i=1,M , j=1,N).
3. Nhập tọa độ của hai điểm giao A và B.
4. Trả lời câu hỏi: Có thể đi từ A sang B hoặc từ B sang A mà chỉ đi theo hướng xuống?
Nếu câu trả lời với dữ liệu câu 3 là luôn khẳng định, chương trình còn phải:
5. Xác định ít nhất một đường đi như vậy và hiển thị tọa độ của điểm giao lên màn hình.
6. Xác định tất cả các đường đi như vậy.

kỳ một thủ tục nào khác.
Quá trình được tiếp tục thực hiện đến khi toàn bộ mặt 12 quân bài đều là J, Q, K hoặc
không còn cặp nào có tổng giá trị bằng 10.
Hãy viết chương trình mô phỏng quá trình trên với những yêu cầu sau:
1. Số N - số lần lặp lại thủ tục trên phải được nhập từ bàn phím. Khi N = 1, một trong các
trường hợp 2,3 và 4 dưới đây xảy ra.
2. (a) Bộ bài phải được tạo mới, với mỗi lần lặp lại chương trình phải xáo lại bài.
(b) Bộ bài được hiển thị ra màn hình.
3. (a) 12 quân bài hiển thị trên màn hình theo quá trình mô tả trên.
(b) Các quân bài còn lại trong bộ bài phải được hiển thị trên màn hình.
4. (a) Các quân bài bị phủ lên trong quá trình trên phải được thay bằng các quân bài thay
chúng và phải được hiển thị trên màn hình.
(b) Sau mỗi lần thay thế, các quân bài còn lại trong bộ cũng được hiển thị trên màn
hình.
5. Sau 5 lần lặp lại, cần phải đưa ra một biểu đồ mà trong đó sẽ hiển thị số quân bài còn
lại trong bộ bài sau khi kết thúc mỗi thủ tục.

II. Bài toán rào cây
Một nông dân muốn bảo tồn một loại cây bách cổ quý hiếm. Để làm điều này, ông ta ghi
nhớ vị trí của mỗi cây và quyết định dùng dây kim loại rào quanh cây theo một hình đa
giác để cây nằm toàn bộ trong đó. Để giảm chi phí, ông ta cần tính chiều dài dây kim loại
tối thiểu nhất. Người nông dân muốn xây một ngôi nhà hình chữ nhật, một trong các cạnh
nhà song song với trục X và ông ta cần biết vị trí tương đối của ngôi nhà:
(1) Ngôi nhà nằm bên ngoài hàng rào hình đa giác.
(2) Ngôi nhà nằm trong hàng rào hình đa giác.
(3) Hàng rào chia ngôi nhà thành hai phần có diện tích khác 0.
Hãy viết chương trình thực hiện các công việc sau:
(A) Tìm các cây nằm ở đỉnh đa giác.
(B) Tính chiều dài của dây kim loại cần sử dụng.
(C) Chỉ ra vị trí của ngôi nhà trong ba trường hợp (1,2,3) trên.

Chú ý: Bài làm được đánh giá tốt nếu kết quả ra trông giống như trong hình 1.

IV. Ngôn ngữ
Cho trước một tệp văn bản ASCII chứa một đoạn văn bản mà ngôn ngữ dùng không được
biết đến mà chỉ nhận biết đặc điểm là các ký tự Latin.
Bài toán đặt ra
Phân tích nội dung của tệp văn bản để xác định ngôn ngữ được sử dụng (tiếng Anh, Pháp
hoặc Đức, ).
(A) Hãy viết chương trình đọc nội dung tệp và đếm số ký tự trong đó. In ra tổng số ký tự.
(B) Sửa chương trình trong yêu cầu (A) thành chương trình còn có thể đếm số lần xuất
hiện của mỗi ký tự (các dấu chấm câu coi như ký tự trống, không phân biệt chữ cái
thường, chữ cái hoa ). Các ký tự chỉ nằm trong tập [' ','A' 'Z'].
Sắp xếp các ký tự theo tần số xuất hiện giảm dần và in danh sách đó ra.
(C) Sửa chương trình trong yêu cầu (B) để có thể xác định tần số xuất hiện của các ký tự.
Tiêu chuẩn hóa việc đếm, ví dụ chia tần số xuất hiện của mỗi ký tự cho tổng số ký tự đã
đọc sẽ được tỷ lệ xuất hiện tương đối phụ thuộc vào tổng số ký tự trong văn bản. Viết tỷ
lệ này vào tệp dữ liệu.
(D) Mở rộng chương trình ở (C) sao cho nó có thể đọc tệp văn bản và so sánh nó với một
văn bản bằng một ngôn ngữ đã biết. Phương pháp so sánh do bạn tự nghĩ ra. Kết quả báo
cáo ra cần cho biết ngôn ngữ sử dụng để viết văn bản ban đầu.
V. S-TERMS
S-term là một chuỗi gồm các ký tự S và dấu ngoặc đơn được định nghĩa một cách đệ quy
như sau: S là một S-term, và nếu M và N là các s-term, thì (MN) cũng là một s-term.
Ví dụ:
((((SS)(SS))S)(SS))
Các dấu ngoặc đơn bên phải không chứa thông tin gì mới, do đó có thể bỏ chúng đi, ví dụ
(MN thay cho (MN), do đó chuỗi ban đầu trở thành:
((((SS(SSS(SS
1. Hãy viết một thủ tục "tạo chuỗi" để tạo ra các S-term: thủ tục của bạn phải sinh ra n (n
= độ dài = số ký tự S trong chuỗi) tệp văn bản chứa tất cả các S-term có độ dài lần lượt là

g) Báo cáo tỉ số giữa số lần không chuẩn hóa được trên tổng số của S-term với độ dài n
cho trước.
VI. Nhóm tội phạm đông nhất
Một cảnh sát trưởng biết rõ về số tội phạm trong thành phố mình quản lý cũng như tất cả
những người cộng tác với chúng. Hãy xác định tất cả các nhóm tội phạm có thể trong
thành phố.
Trong trường hợp này, nhóm tội phạm là một bộ phận của tất cả những kẻ phạm tội.
Nhóm tội phạm lớn nhất là không còn nhóm nào có số phần tử đông hơn nhóm này.
Hãy viết chương trình thực hiện các công việc sau:
(A) Nhập dữ liệu của cảnh sát trưởng với số tội phạm không quá 41 người. Dữ liệu ra là
một tệp văn bản ASCII có cấu trúc như sau:
a(1,1)
a(2,1)a(2,2)
a(3,1)a(3,2)a(3,3)

a(n,1)a(n,2)a(n,3) a(n,n)
Trong đó a(i,j) = 1, nếu người i cộng tác với người j hoặc i = j, và a(i,j) = 0 nếu ngược lại.
Ví dụ trong trường hợp có 6 người:
1
01
101
1011
01101
101111
Trong ví dụ này, kết quả ra sẽ là một trường hợp sau:
Nhóm tội phạm đông nhất là: 1 3 4 6 (tổng số phần tử trong nhóm là 4)
(B) Mở rộng phần dữ liệu vào của chương trình để tạo dữ liệu theo cách ngẫu nhiên với
số nhóm cộng tác 0 < d < 1.
(C) Dùng dữ liệu ngẫu nhiên hoặc tệp file dữ liệu vào, tìm nhóm tội phạm đông nhất
trong thành phố. Kết quả ra tương tự trong ví dụ trên (yêu cầu câu A).

Bob 16.00-17.25 Cross
John 09.30-11.50 Health
Charles 11.00-20.00 Chest
Don 08.00-13.20 Cross
Norman 22.00-23.05 Brain
Jerry 10.00-17.00 Health
Charles 09.20-10.40 Orthopedic
Evelyn 19.15-20.40 Orthopedic
Peter 09.35-11.55 Brain
Don 18.00-20.00 Eye
Kết quả ra: chứa một bảng liệt kê danh sách các cuộc gặp theo thứ tự thời gian. Bảng
gồm các dòng chứa điểm thời gian bắt đầu và kết thúc của các cuộc hẹn gặp, địa điểm
gặp (tên bệnh viện) và tên bác sỹ. Ví dụ, kết quả ra tương ứng với ví dụ trên có dạng sau:
08.00-09.10 Cross Don
09.40-10.50 Health John
11.20-12.30 Chest Charles
13.00-15.30 Health Jerry
16.00-17.25 Cross Bob
19.15-20.40 Orthopedic Evelyn
8. Giải bài toán trên với hai trình dược viên A và B theo đúng quy tắc trên và thêm giới
hạn sau: họ không cùng gặp một bác sỹ. Mỗi khi có sẵn cuộc gặp thì người gặp sẽ là trình
dược viên có khoảng thời gian rỗi dài hơn. Nếu cả hai trình dược viên đều có khoảng thời
gian rỗi như nhau, A sẽ thực hiện cuộc gặp đó. Kết quả ra gồm hai danh sách các cuộc
gặp.
Cuộc thi Olympiad Quốc tế môn Tin
học lần thứ tư tổ chức tại Bonn,
Germany, tháng 7 năm 1992
1. Khám phá bản đồ
Một bản đồ hình chữ nhật có kích thước theo hệ tọa độ là 48 x 16. Hai tọa độ được gọi là
nối với nhau nếu chúng liền nhau theo cả hướng Bắc-Nam và hướng Đông-Tây. Ban đầu,
mỗi tọa độ chỉ được biết là Mặt nước W (WATER) hoặc Đất liền G (GROUND).
Có bốn kiểu tọa độ Đất liền (GT): G, M, P và C. Và có bốn kiểu tọa độ Mặt nước (WT):
W, O, B và L. Giả sử bên ngoài bản đồ là Đại dương (O).
Các quy tắc địa lý cho việc chuyển kiểu tọa độ, có thể là một:
- Núi (M): Nếu 1 tọa độ GT được nối với 4 tọa độ GT khác.
- Bán đảo (P): Nếu 1 tọa độ GT được nối với 3 tọa độ WT; hoặc 2 tọa độ WT và ít nhất 1
tọa độ P; hoặc 1 tọa độ WT và ít nhất 2 tọa độ P.
- Bờ biển (C): Nếu 1 tọa độ GT không phải là tọa độ M hay P.
- Đại dương (O): Nếu 1 tọa độ WT nối với ít nhất một tọa độ O.
- Vịnh (B): Nếu 1 tọa độ O được nối với ít nhất 2 tọa độ B và nhiều nhất 1 tọa độ O, hoặc
với 1 tọa độ B và ít nhất 2 tọa độ GT, hoặc ít nhất 2 tọa độ GT và ít nhất 1 tọa độ O.
- Hồ (L): Nếu 1 tọa độ W không đổi đến khi không thực hiện được phép chuyển kiểu tọa
độ nào nữa.
Điều này có thể xảy ra sau khi một tọa độ cụ thể đã được chuyển kiểu thì nó có thể được
chuyển kiểu một lần nữa vì kiểu của một số tọa độ lân cận có thể thay đổi trong lúc đó.
Một bản đồ được khám phá nếu không thực hiện được phép chuyển tọa độ nào nữa.
Yêu cầu: Hãy viết chương trình thực hiện công việc sau:
1. Đọc bản đồ một lục địa chưa được biết đến từ tệp dữ liệu vào theo định dạng ASCII và
hiển thị nó lên màn hình cùng với kiểu tọa độ ban đầu như trong ví dụ 1.

Một Đường đi là một chuỗi các ô vuông liền nhau (nằm giữa hai bức tường), Đường đi
bắt đầu bằng Lối vào và kết thúc tại một Điểm cuối. Chiều dài của Đường đi là số ô
vuông nằm trong nó gồm cả điểm đầu và điểm cuối.
Mê cung gồm các con đường phân nhánh nhưng không nối với nhau do đó hai con đường
bất kỳ không có cùng điểm cuối. Lối vào nằm ở một nơi nào đó ở đỉnh mê cung. Vật quý
nằm ở Điểm cuối Đường đi có độ dài lớn nhất.
Vùng kích thước N x M chứa số Đường đi tối đa có thể. Vì thuật toán thực hiện rất nhanh
nên cần có Thời gian chờ sau mỗi lần qua một ô vuông.
Yêu cầu: Viết bộ công cụ thực hiện các công việc với mê cung. Các công cụ có thể thực
hiện theo thứ tự khác nhau:
Công cụ 1: Thiết lập các tham số chính N và M của mê cung.
Công cụ 2: Thiết lập Thời gian chờ.
Công cụ 3: Tạo ngẫu nhiên một mê cung mới và hiển thị trên màn hình khi đang được tạo
ra.
Công cụ 4: Lưu mê cung được tạo ra và đường dẫn kích thước vào một tệp văn bản
ASCII như trong hình 2.
Công cụ 5: Đọc một mê cung chưa biết đến từ tệp văn bản ASCII và nhấn mạnh đường
dẫn từ Lối vào đến Vật quý.
Yêu cầu kỹ thuật
Yêu cầu 1: Biểu diễn mỗi ô vuông bằng một chuỗi hai ký tự:
- Bức tường bằng 2 lần chuỗi ký tự ASCII #219 "[["
- Đường đi và Lối đi bằng hai ký tự trống " "
- Vật quý bằng ký tự T và ký tự trống "T "
- Đường đi được nhấn mạnh bằng dấu chấm câu và ký tự trống ". "
Yêu cầu 2: 2 < N và M < 20.
Yêu cầu 3: Lưu chương trình vào một tệp văn bản ASCII có tên
"C:\IOI\DAY-1\412-PROG.xxx". Phần mở rộng .xxx là:
- .BAS với chương trình BASIC, .C với chương trình C,
- .LCN với chương trình LOGO, .PAS với chương trình PASCAL.
Yêu cầu 4: Tên tệp văn bản ASCII để đọc và lưu các mê cung là

trống. Nếu không có bản đồ nào thảo mãn điều kiện, hãy in ra dòng "No map". Lời giải
cho mỗi khối dữ liệu khác nhau được ngăn cách bằng một dòng "next problem".
Yêu cầu kỹ thuật
Yêu cầu 1: 1 < N < 8.
Yêu cầu 2: Lưu lời giải vào tệp văn bản ASCII tên là
"C:\IOI\DAY-1\413-PROG.xxx". Phần mở rộng .xxx là:
- .BAS với chương trình BASIC, .C với chương trình C,
- .LCN với chương trình LOGO, .PAS với chương trình PASCAL
Yêu cầu 3: Tệp văn bản ASCII chứa các thông tin mã hóa được lưu trong
"C:\IOI\DAY-1\413-SEAS.IN".
Yêu cầu 4: Tệp kết quả ra chứa các bản đồ được lưu trong
"C:\IOI\DAY-1\413-SEAS.OU".
Ví dụ
6 Ví dụ 1: Kích thước lưới là 6.
1 2 0 < Bắt đầu dòng đầu tiên của ràng buộc
3 1 0
1 1 1 0
5 0
2 1 1 0
1 0
1 1 1 0 < Bắt đầu cột đầu tiên của ràng buộc
1 2 0
4 0
2 3 0
2 0
1 2 0
(*************************************************)
4 Ví dụ 2. Lời giải: các cột: 1 2 3 4
0 hàng 1:
1 0 hàng 2: *

1. "ORIENTATION Xk Yk": được dùng cho trạng thái đầu tiên. Robot quay sang hướng
đến vị trí Pk (k nằm giữa 2 và N).
2. "MOVE-TO Xj Yj": nếu robot có thể đến điểm Pj mà không cần thay đổi hướng đi
hiện tại, thì nó sẽ đi đến vị trí Pj (j nằm giữa 1 và N). Nếu không trạng thái này không
thực hiện được.
3. "TURN-LEFT": robot chuyển hướng đi sang trái một góc 90 độ.
4. "TURN-RIGHT": robot chuyển hướng đi sang phải một góc 90 độ.
5. "STOP": cho robot dừng lại. Đây là lệnh cuối cùng phải có trong một chương trình
hoạt động cho robot.
Yêu cầu: Hãy viết chương trình thực hiện các nhiệm vụ sau:
1. Đọc giá trị của N và tọa độ của N vị trí cho trước từ một tệp ASCII (xem ví dụ) và
hiển thị dữ liệu lên màn hình.
2. Phát triển chương trình điều khiển robot thực hiện một chuyến đi qua tất cả các vị trí
nếu có tồn tại.
3. Nếu không tồn tại chuyến đi đó, chương trình robot phải chứa lệnh "STOP".
4. Nếu có tồn tại chuyến đi qua được tất cả các vị trí, hãy hiển thị lên màn hình chiều dài
lộ trình đi (làm tròn đến 2 chữ số sau dấu thập phân). Chiều dài lộ trình đi là tổng chiều
dài của các đường thẳng robot đi qua.
5. Viết chương trình điều khiển robot vào một tệp kết quả theo bảng mã ASCII như trong
ví dụ dưới.
Yêu cầu kỹ thuật
Yêu cầu 1: Lưu chương trình kết quả vào một tệp văn bản ASCII với tên:
"C:\IOI\DAY-2\421-PROG.xxx". Phần mở rộng .xxx là:
- .BAS với chương trình BASIC, .C với chương trình C,
- .LCN với chương trình LOGO, .PAS với chương trình PASCAL
Yêu cầu 2: Tên tệp input là "C:\IOI\DAY-2\421-ROBO.IN".
Yêu cầu 3: Tên tệp output là "C:\IOI\DAY-2\421-ROBO.OU".
Yêu cầu 4: Chương trình loại bỏ các giá trị input N nhỏ hơn 4 hoặc lớn hơn 16.

Ví dụ

đến dỉnh núi và tất cả những người còn lại sẽ trở lại điểm khởi hành.
Yêu cầu
Hãy viết chương tình thực hiện các nhiệm vụ sau:
1. Nhập từ bàn phím số nguyên N chỉ số ngày cần thiết để lên đến đỉnh núi, số người leo
núi P của câu lạc bộ, số đồ dùng được cấp S(i) và số đồ dùng cần thiết C(i) của người thứ
i (i nằm từ 1 đến P). Giả sử dữ liệu vào đều là số nguyên.
2. Lập kế hoạch cho câu lạc bộ leo núi. Xác định các nhóm leo núi a(1), , a(k) và số đồ
dùng được cấp M(j) mà người leo núi (j) mang theo lúc khởi hành (j nằm từ 1 đến k).
Chú ý, có thể không tồn tại một kế hoạch cho cho sự kết hợp N, S(i) và C(i).
3. Báo cáo các thông tin sau ra màn hình:
a) số người leo núi thực tế k tham gia leo núi,
b) tổng số đồ dùng cần được cấp,
c) số người leo núi a(1), , a(k),
d) với mọi a(j), j nằm giữa 1 và k, tổng số đồ dùng được cấp M(j) được người a(j) mang
theo.
e) ngày D(j) khi số người leo núi a(j) xuống sức.
4. Kế hoạch là tối ưu nếu
a) số người tham leo núi là tối thiểu và
b) trong số tất cả các nhóm thỏa mãn điều kiện a), tổng số đồ dùng dùng hết là ít nhất.
Hãy cố tìm kế hoạch gần tối ưu.
Yêu cầu kỹ thuật
Yêu cầu 1: Lưu chương trình lập kế hoạch vào tệp văn bản ASCII với tên gọi
"C:\IOI\DAY-2\422-PROG.xxx". Phần mở rộng .xxx là:
- .BAS với chương trình BASIC, .C với chương trình C,
- .LCN với chương trình LOGO, .PAS với chương trình PASCAL
Yêu cầu 2: Chương trình loại bỏ dữ liệu vào với N nhỏ hơn 1 hoặc lớn hơn 100.
P phải lớn hơn 1 và nhỏ hơn 20.
Ví dụ
Có thể so sánh với chương trình của bạn:
Số ngày cần để lên đến đỉnh: 4

mặt của hình lập phương Rubik được sơn một màu khác nhau. Tất cả các mặt của hình
lập phương Rubik gồm 3 x 3 mặt của lớp 9 hình lập phương nhỏ hơn.
Hãy tưởng tượng, bạn đang nhìn vào một trong 6 mặt của hình lập phương Rubik. Lớp
gồm 3 x 3 hình lập phương nhỏ hơn bạn nhìn thấy có thể quay một góc là bội số của 90
độ, trong đó trục quay là đường trực giao của mặt đó và đi qua tâm của nó. Kết quả là
một mặt khác gồm 3 x 3 x 3 hình lập phương nhỏ với sơ đồ màu bị quay và màu trên bốn
mặt xung quanh thay đổi.
Trong bài toán này, các mặt hình lập phương được đặt tên thay vì sơn màu: U = Lên, R =
Phải, F = Trước, B = Sau, L = Trái và D = Dưới. Bất kỳ một chuỗi hành động quay mặt
lập phương nào đều có thể biểu diễn bằng một chuỗi ký tự {U, R, F, B, L, D} trong đó
mỗi ký tự thay thế một lần quay góc 90 độ theo chiều kim đồng hồ của một mặt tương
ứng.
Yêu cầu
Hãy viết chương trình cho phép người sử dụng giải lặp lại một trong ba bài toán nhỏ đưa
ra theo thứ tự bất k ỳ. Bạn có thể giả sử độ dài của mỗi chuỗi nhập vào không quá 35 ký
tự.
1. Bài toán nhỏ này là bản dịch từ của một chuỗi hành động quay cho trước sang một
chuỗi hành động quay mà không một hành động quay nào được lặp lại quá 3 lần trong
chuỗi. Thuật toán phải loại bỏ những chuỗi dữ liệu vào không đúng.
Ví dụ minh họa: