Tuyển tập đề thi tin học

e văn bản SEAWEED.INP gồm: 
• Dòng đầu tiên chứa số nguyên dương n cho biết số đỉnh của đường gấp khúc, 
• Mỗi dòng trong các dòng tiếp theo chứa một xâu chỉ chứa các ký tự số thập phân ứng với một 
dòng thông tin về các đỉnh của đường gấp khúc mà công ty đã nhận được. Thông tin về các 
đỉnh được liệt kê theo một chiều nào đó (theo chiều kim đồng hồ hoặc ngược lại). 
Dữ liệu cho đảm bảo tồn tại duy nhất một đường gấp khúc thoả mãn điều kiện bài toán. 
Kết quả: Ghi ra file văn bản SEAWEED.OUT, gồm một dòng chứa 2 số nguyên d và S, ghi cách nhau 
một dấu cách. 
Ví dụ: 
SEAWEED.INP SEAWEED.OUT 
10 
1215 
3537 
6764 
8481 
3132 
26 30 
 Olympic tin học Việt Nam 
Bài 3. Nhân của biểu thức 
Biểu thức ngoặc là xâu chỉ gồm các ký tự ‘(’ và ‘)’. Biểu thức ngoặc đúng được định nghĩa một cách 
đệ qui như sau: 
• Biểu thức rỗng là biểu thức ngoặc đúng, 
• Nếu A là biểu thức ngoặc đúng thì (A) cũng là một biểu thức ngoặc đúng, 
• Nếu A và B là hai biểu thức ngoặc đúng thì AB cũng là một biểu thức ngoặc đúng. 
Số lượng ký tự trong biểu thức ngoặc đúng gọi là độ dài của biểu thức. 
Cho S là một biểu thức ngoặc đúng độ dài 2n (n > 0). Nhân của S ký hiệu là Ker(S) và được xác định 
như sau. Gọi U là xâu thu được từ S bằng cách bỏ đi m ký tự cuối và m ký tự đầu của S, trong đó m = n 
div 2. Khi đó: 
• Ker(S) = U, nếu U là biểu thức ngoặc đúng và U≠S, 
• Ker(S) = ∅ (biểu thức rỗng), trong trường hợp ngược lại, 
Qui ước Ker(∅) = ∅. 
Ví dụ, S = ‘()(())()’, ta có Ker(S) = ‘(())’. Nếu S = ‘()(())’, có Ker(S) = ∅, vì U = ‘)(()’ – không phải là 
biểu thức ngoặc đúng. Dễ dàng nhận thấy, với n = 1, Ker(S) = ∅. 
Với biểu thức ngoặc đúng S cho trước ta có thể thực hiện đệ qui nhiều lần phép xác định nhân 
Ker(Ker(…(Ker(S))…)) cho đến khi nhận được biểu thức rỗng. Ta gọi bậc của biểu thức S là số lần 
thực hiện đệ qui việc xác định nhân của S cho đến khi nhận được biểu thức rỗng. 
Ví dụ, biểu thức S = ‘()(())()’ có bậc 3 vì: 
()(())() → (()) → ()→ ∅. 
Biểu thức S = ‘()(())’ có bậc 1 vì nhân của nó Ker(S) = ∅. 
Yêu cầu: Xét các biểu thức ngoặc đúng độ dài 2n và có bậc p. Các biểu thức này được sắp xếp theo 
thứ tự từ điển (‘(‘ < ‘)’) và đánh số bắt đầu từ 1 trở đi. Hãy tìm biểu thức thứ k. 
Dữ liệu: Vào từ file văn bản EKERNEL.INP gồm một dòng chứa 3 số nguyên n, p và k, các số cách 
nhau một dấu cách (1 ≤ n ≤ 40, 1 ≤ p ≤ 6, 1 ≤ k ≤ 3×1018). Dữ liệu đảm bảo tồn tại biểu thức cần tìm. 
Kết quả: Ghi ra file văn bản EKERNEL.OUT xâu ký tự xác định biểu thức tìm được. 
Ví dụ: 
EKERNEL.INP EKERNEL.OUT 
3 1 2 ()(()) 
 Olympic tin học Việt Nam 
Bài 4. LED 
Để tạo không khí sôi nổi và nhắc nhở học sinh cố gắng học tập, nhà trường lắp một đồng hồ đếm 
ngược, cho biết còn lại bao nhiêu ngày, bao nhiêu giờ, phút, giây sẽ tới một thời điểm quan trọng 
chẳng hạn như kiểm tra cuối kỳ của môn văn, thi học sinh giỏi Quốc gia, thi Tốt nghiệp v. v. . . Trên 
mặt đồng hồ có 4 cửa sổ: cửa sổ D chỉ ngày hiển thị 3 chữ số cho biết số ngày còn lại, cửa sổ H chỉ 
giờ, cửa sổ M chỉ phút và cửa sổ S chỉ giây. Mỗi cửa sổ H, M và S hiển thị 2 chữ số chỉ giờ, phút, giây 
còn lại. Mỗi chữ số được hiển thị bằng các Điốt phát sáng (LED) đặt dọc và ngang. Hình 2a cho biết 
cách hiển thị mỗi chữ số từ 0 đến 9. Ví dụ, để hiển thị số 0 cần 4 LED dọc và 2 LED ngang. Nếu thời 
gian còn lại là 18 ngày, 10 giờ, 20 phút và 10 giây thì bảng hiển thị của đồng hồ đếm ngược sẽ có dạng 
như ở hình 2b. 
 Hình 2a Hình 2b 
Như vậy, sau mỗi giây trạng thái của đồng hồ đếm ngược sẽ bị thay đổi và để hiển thị trạng thái này ta 
phải bật sáng một số lượng xác định các LED dọc và ngang. Để thuận tiện trong việc xử lý, người ta 
lưu lại tổng số lượng các LED dọc đã được bật sáng qua các lần hiển thị cho đến trạng thái hiện hành. 
Giả sử lần đầu tiên được bật, bảng đồng hồ đếm ngược chỉ 18 ngày, 10 giờ, 20 phút, 15 giây thì tổng 
số lượng LED dọc được bật sáng sẽ là 159. 
Yêu cầu: Biết trạng thái hiện tại của đồng hồ đếm ngược (các giá trị D, H, M, S) và tổng số lượng các 
LED dọc đã được bật sáng, hãy xác định trạng thái của đồng hồ đếm ngược khi lần đầu tiên được bật. 
Dữ liệu: Vào từ file văn bản LEDS.INP gồm một dòng chứa 5 số nguyên D, H, M, S, T (0 < T < 231) 
ghi cách nhau ít nhất một dấu cách cho biết thông tin về ngày, giờ, phút, giây của trạng thái hiện hành 
và tổng số lượng các LED dọc đã được bật sáng. 
Kết quả: Ghi ra file văn bản LEDS.OUT trên một dòng 4 số nguyên cho biết trạng thái của đồng hồ 
khi lần đầu tiên được bật theo thứ tự ngày, giờ, phút và giây. 
Ví dụ: 
LEDS.INP LEDS.OUT 
18 10 20 10 159 18 10 20 15 
 Olympic tin học Việt Nam 
Bài 5. Quay số trúng thưởng 
Trong trò chơi quay số trúng thưởng, có một bánh xe chỉ quay quanh trục ngược chiều kim đồng hồ, 
trên đó có n ô. Trên mỗi ô có ghi một số nguyên dương không vượt quá n và không có hai số nào 
giống nhau. Số ghi trên ô được gọi là giá trị của ô. Có một kim định vị gắn cố định bên ngoài bánh xe 
để khi quay, các ô của bánh xe sẽ lần lượt lướt qua kim định vị. Khi bánh xe dừng quay, kim định vị 
trỏ vào ô nào ta nói bánh xe dừng ở ô đó. 
Lượt chơi của một người được thực hiện như sau. Đầu tiên, người chơi được quyền xoay để bánh xe 
dừng lại ở một ô xuất phát tuỳ chọn. Hệ thống sẽ tự động đánh số các ô trên bánh xe từ 1 đến n theo 
chiều kim đồng hồ bắt đầu từ ô xuất phát này. Các số thứ tự này sẽ được giữ nguyên cho đến khi kết 
thúc lượt chơi. Sau khi chọn ô xuất phát, trả lời câu hỏi tương ứng với ô này và nhận phần thưởng nếu 
trả lời đúng, người chơi bấm nút cho bánh xe tự động quay. Hệ thống điều khiển được lập trình để 
bánh xe sẽ dừng lại ở ô có số thứ tự lớn hơn số thứ tự của ô ở lần dừng trước. Đồng thời, giá trị ở ô 
mới cũng phải lớn hơn giá trị ở ô cũ. Mỗi lần bánh xe dừng, người chơi sẽ có cơ hội trả lời câu hỏi để 
nhận phần thưởng. Sau khi trả lời đúng câu hỏi, người chơi lại bấm nút cho bánh xe tiếp tục quay. 
Lượt chơi kết thúc khi người chơi trả lời sai hoặc hệ thống điều khiển không tìm được ô dừng tiếp 
theo. 
Nếu chọn vị trí xuất phát hợp lý người chơi sẽ có nhiều cơ hội trả lời các câu hỏi để lĩnh thưởng. 
Ví dụ, giả sử bánh xe có 5 ô lần lượt mang giá trị 1, 3, 2, 5, 4. Nếu chọn ô xuất phát là ô có giá trị 2, 
bánh xe có thể dừng ở ô có giá trị 5, 4 hay 3. Dù dừng lại ở ô nào thì lượt chơi cũng kết thúc. Nếu 
chọn ô xuất phát là ô có giá trị 1, người chơi trong trường hợp may mắn nhất, có thể có tới ba cơ hội 
trả lời câu hỏi của trò chơi (xem ví dụ trong hình 3). 
2
0
%
2
0
% 2
0
%
2
0
%
2
0
%
1
3
5
1
2
4
3
24
2
3
5
20% 20%
20%
20%
20%
12 13
5
Hình 3- Nếu bắt đầu từ 1 ta có thể có tối đa 3 cơ hội trả lời 
Yêu cầu: Cho n và giá trị của các ô trong vòng tròn. Hãy cho biết số cơ hội nhiều nhất được trả lời câu 
hỏi của trò chơi mà người chơi có thể chờ đợi nếu chọn ô xuất phát hợp lý. 
Dữ liệu: Vào từ file văn bản LWEEL.INP: 
• Dòng đầu tiên chứa số nguyên n (1<n≤1000) là số ô trên bánh xe. 
• Dòng thứ hai chứa n số nguyên dương cho biết lần lượt giá trị của các ô trên bánh xe được liệt 
kê theo chiều kim đồng hồ bắt đầu từ một ô nào đó. Các số trên cùng một dòng cách nhau bởi ít 
nhất 1 dấu cách. 
Kết quả: Ghi ra file văn bản LWEEL.OUT một số nguyên dương duy nhất là số cơ hội nhiều nhất 
được trả lời câu hỏi. 
Ví dụ: 
LWEEL.INP LWEEL.OUT 
5 
1 3 2 5 4 
3 
 Olympic tin học Việt Nam 
Bài 6. Công nghệ Nano 
Công nghệ Nano mang lại nhiều thay đổi trong việc chế tạo các mạch điện tử. Ví dụ, các bảng mạch 
không có dạng hình chữ nhật mà là hình tam giác đều, từ đó tạo ra các con chíp hình kim tự tháp. Xét 
việc chế tạo một bảng mạch Nano. Bảng mạch có hình tam giác đều và được chia thành lưới các tam 
giác đều con bằng các đường song song với cạnh tam giác. Các tam giác con có độ dài cạnh bằng 1 và 
tạo thành các hàng đánh số từ 1 trở đi, từ trên xuống dưới, ở mỗi hàng các tam giác được đánh số từ 1 
trở đi từ trái sang phải. Một tam giác được xác định bởi hai tọa độ: hàng và vị trí trong hàng (Hình 4a). 
Các đường song song với hai cạnh bên bảng mạch tạo thành lưới tọa độ, xác định vị trí đỉnh các tam 
giác con (Hình 4b). 
x y x y
 Hình 4a Hình 4b Hình 4c 
Các linh kiện Nano có dạng hình tròn với kích thước đúng bằng hình tròn nội tiếp tam giác đều với độ 
dài cạnh là 1. Có 2 loại linh kiện T và P. Linh kiện loại T được cấy gọn vào một tam giác con trong 
lưới, còn linh kiện loại P được cấy sao cho tâm của linh kiện trùng với đỉnh của tam giác con. Mỗi linh 
kiện đều nằm gọn trong bảng. Sau khi đã cấy các linh kiện, trên bảng mạch xuất hiện những vùng 
được bao bọc bởi các linh kiện. Những vùng này là những vùng nhạy cảm, cần được làm sạch và phủ 
một lớp bảo vệ đặc biệt. Để tính chi phí làm sạch và phủ các vùng này, người ta cần biết tổng diện tích 
của chúng trên mạch đã thiết kế. 
Ví dụ, trên bảng mạch ở hình 4c có 7 linh kiện loại T được cấy vào các tam giác con (2,1), (2,2), (2,3), 
(3,2), (3, 3), (3,4) và (4, 6), có một linh kiện loại P cấy vào ví trí đỉnh (1,2) và xuất hiện 2 vùng nhạy 
cảm. 
Yêu cầu: Cho biết m – số linh kiện loại T, n – số linh kiện loại P, tọa độ của các linh kiện (tọa độ linh 
kiện loại T là tọa độ tam giác chứa linh kiện, tọa độ linh kiện loại P là tọa độ tâm của nó). Hãy xác 
định diện tích vùng khép kín với độ chính xác 5 chữ số sau dấu chấm thập phân. 
Dữ liệu: Vào từ file văn bản NANO.INP: 
• Dòng đầu tiên chứa 2 số nguyên không âm m và n ( 0 ≤ m+n ≤ 20000), 
• Mỗi dòng trong m dòng tiếp theo chứa 2 số nguyên dương xác định tọa độ một linh kiện loại T, 
• Mỗi dòng trong n dòng tiếp theo chứa 2 số nguyên dương xác định tọa độ một linh kiện loại P. 
Các số trên một dòng cách nhau một dấu cách. Giá trị mỗi tọa độ không vượt quá 105. 
Kết quả: Đưa ra file văn bản NANO.OUT dưới dạng số thực với 5 chữ số sau dấu chấm thập phân. 
Ví dụ: 
NANO.INP NANO.OUT 
7 1 
2 1 
2 2 
2 3 
3 2 
3 3 
3 4 
4 6 
1 2 
0.35586 
Ghi chú: pi = 3.14159265358979323846264338327950288419716939937510