Đề thi không chuyên toàn quốc

HỘI THI TIN HỌC TRẺ KHÔNG CHUYÊN TOÀN QUỐC LẦN THỨ X, 2004
Địa điểm thi: ĐẠI HỌC BÁCH KHOA HÀ NỘI

Đề thi lập trình bảng B: Trung Học Cơ Sở
Thời gian làm bài: 120 phút
Ngày thi: 16-08-2004



TỔNG QUAN VỀ ĐỀ THI
BÀI TOÁN
Card Mạng
Tiên thiêng

Tên file bài làm
NETCARD.???
HOLYNAME.???

Tên file dữ liệu
NETCARD.HOLYNAMEP
HOLYNAME.HOLYNAMEP

Tên file kết quả
NETCARD.OUT
HOLYNAME.OUT

Hạn chế thời gian cho một test
3 giây
5 giây

Số lượng test
10
10

Điểm của một test
4
4

Tổng điểm
40
40


Chú ý:
Dấu ??? trong tên file bài làm phải được thay thế bởi đuôi ngầm định của ngôn ngữ lập trình mà em lựa chọn thực hiện.
Tên file bài làm, file dữ liệu và file kết quả phải được đặt theo đúng yêu cầu của đề bài (không được đặt đường dẫn cho file dữ liệu và file kết quả)
Đề thi gồm ba trang. Giám thị không cần giải thích gì thêm. Thí sHOLYNAMEh không sử dụng tài liệu trong khi thi.
Bài 1. CARD MẠNG Tên file chương trình: NETCARD.???
Trung tâm máy tính NewAge dự trữ trong kho N card mạng được đánh số hiệu lần lượt từ 1 tới N (2≤N≤1500). Định kỳ, trung tâm tiến hành việc kiểm định chất lượng để xác định card hỏng bằng K phép thử. Mỗi phép thử được tiến hành trên một cặp card mạng bất kỳ bằng cách lắp chúng vào một thiết bị chuyên dụng cho phép xác định khả năng truyền thông của hai card mạng đó. Nếu hai card mạng đó liên lạc tốt với nhau thì cả hai card mạng được thử đều còn tốt, trong trường hợp ngược lại-ít nhất một trong hai card mạng bị hỏng. Tuy nhiên nhân viên kiểm định lại không phải là người chu đáo và cẩn thận, do vậy, anh ta chọn các cặp card mạng để tiến hành K phép thử không theo một trình tự nào, thậm chí có những card mạng được thử đi thử lại nhiều lần. Rất may là anh ta vẫn còn ghi lại kết quả cụ thể của từng phép thử.

Yêu cầu: Theo kết quả của K phép kiểm tra (0≤K≤15000) hãy cho biết từng card mạng được dự trữ trong kho là tốt, hỏng hay không xác định được trạng thái của nó.

Dữ liệu: Vào từ file văn bản NETCARD.INP:
Dòng đầu tiên chứa hai số nguyên N và K
K dòng tiếp theo: Trên mỗi dòng chứa 3 số nguyên I J V, trong đó I,J tương ứng là số hiệu hai card mạng được kiểm tra; V là kết quả kiểm tra: V=1 khi cả hai card đều tốt, ngược lại V=0
Kểt quả: Đưa ra file văn bản NETCARD.OUT đưa ra N số nguyên Q1Q2….Qn, trong đó Qi xác định chất lượng của card mạng thứ i: Qi=1-tốt, Qi=0-hỏng, Qi=2-chưa rõ trạng thái.
Các số trong file vào ra cách nhau ít nhất một dấu cách hoặc một tổ hợp phím xuống dòng.
Bài 2. TÊN THIÊNG Tên file chương trình: HOLYNAME.???
Thời xa xưa, do trình độ hiểu biết còn hạn chế, người ta rất dễ tin vào những điều mê tín. Ví dụ, bộ lạc vùng Flandhand cho rằng, để chống lại được bệnh tật và ngăn cản được bước đi của Thần Chết, tên của những người dân tộc thuộc bộ tộc này phải được chọn là một xâu con các ký tự liên tiếp nhau của một tên thiêng W nào đó. Ví dụ, nếu W là “baobaab” thì có thể chọn “ba”, ”oba”, “baab” để làm tên người, còn “bab” hay “bob” thì không thể được dùng làm điều đó.

Với mỗi tên thiêng W, tù trưởng bộ tộc vùng Fladhand muốn biết có thể có tối đa bao nhiêu tên người khác nhau.

Dữ liệu: Vào từ file văn bản HOLYNAME.INP chỉ gồm một dòng chứa tên thiêng W độ dài không quá 2000 ký tự, trong đó chỉ có các chữ cái latinh thường.

Kết quả: Đưa ra file văn bản HOLYNAME.OUT một số nguyên là số lượng tối đa các tên người có thể đặt khác nhau.

Ví dụ:

HOLYNAME.INP

HOLYNAME.OUT

Ví dụ 1
Ví dụ 2
Ví dụ 3
baobaab
meomeo
ooooooo

23
15
5