Đề thi HSG QG tin học 2008


Bài 1: SEQGAME - Trò chơi dãy số Cho 2 dãy số b1, b2, ..., bn và c1, c2, ..., cn. Tìm giá trị bé nhất của |bi + cj| (giá trị tuyệt đối của bi+cj) Giới hạn: n <= 10^5. Có 60% test với n <= 1000. Các số có trị tuyệt đối bé hơn 10^9. Input: ------ - Dòng đầu là n - Dòng thứ 2 là dãy b - Dòng thứ 3 là dãy c Output -------- - Ghi ra 1 số duy nhất là giá trị bé nhất tìm được VD: Input 2 -5 3 2 4 Output 1
__________________ ------------------------- │ TRẦN HỮU NAM │ │THPT Nguyễn Du│ --------------------------
Bài 2: JUMP - Lò cò Cho n vòng tròn, trên vòng i ghi 1 số nguyên dương ai (<= 10^9). Nếu ak = ai + aj thì có đường nối 1 chiều từ vòng i -> vòng k và vòng j -> vòng k. Hãy tìm đường đi qua nhiều vòng tròn nhất. Giới hạn: n <= 1000. 60% test n <= 100. --------- Input ------ - Dòng đầu là số n - Dòng sau là dãy a Output ------- Ghi duy nhất số nguyên dương d tương ứng với số vòng đi qua của đường đi dài nhất VD Inp 5 1 2 3 5 8 Out 4 (1 -> 3 -> 5 -> 8) Bài 3: GIFTS - Quà tết Một miếng sôcôla hình vuông chia thành 2^k * 2^k ô vuông nhỏ đều nhau. Các hàng đánh số từ 0 -> 2^k - 1 từ trên xuống. Các cột đánh số từ 0 -> 2^k - 1 từ trái sang phải. Người ta cắt miếng bánh theo cách sau: - Đầu tiên cắt ngang ở giữa miếng bánh, chia thành 2 phần đều nhau rồi gấp phần dưới lên phần trên sao cho các mép trùng nhau. - Sau đó cắt dọc chia miếng bánh thành 2 phần đều nhau, gấp phần bên trái sang phải sao cho các mép trùng nhau. Cứ cắt như vậy đến khi miếng bánh là 1 ô vuông. Sau đó người ta sẽ chia miếng bánh cho mọi người, người thứ m nhận đựơc miếng bánh thứ m từ trên xuống (sau khi cắt các miếng bánh xếp thành 1 chồng) Nhưng trước khi cắt bánh nhà sản xuất có nhét 2 đồng xu vào miếng bánh tại ô (p, q) và (u, v). Nhà sản xuất muốn biết 2 người nào sẽ là 2 ng` may mắn nhận đựơc 2 đồng xu đó. Hãy tìm thứ tự của 2 người này. Giới hạn: k <= 40. 60% test k <= 5. ------- Input: ------ 1 dòng gồm 5 số k p q u v. Output: ------- Ghi ra 2 số là số hiệu của 2 người may mắn VD Inp 1 0 0 1 1 Out 1 3