tailieunhanh - Đề thi olympic tin học lần thứ 12

Hãy lập trình giải các bài sau đây: Bài 1. Tam giác Trên mặt phẳng cho N điểm có toạ độ nguyên Ai (xi, y1), i = 1, 2, , N. Mỗi một trong số N điểm được tô bởi một trong số K mầu. | CẦN THƠ Õ HỘI TIN HỌC VIỆT NAM ffl OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XII 2003 Khối thi chuyên tin Thời gian làm bài 180 phút Ngày thi 18 - 04 - 2003 Nơi thi Đại học Cần Thơ Tên bài Tên file chương trình Tên file dữ liệu Tên file kết quả Tam giác TAMGIAC. Hình xoắn ốc SPIRAL. Ba thành phố COUNTRY. Hãy lập trình giải các bài sau đây Bài 1. Tam giác Trên mặt phang cho N điểm có toạ độ nguyên Ai xi y1 i 1 2 . N. Mỗi một trong số N điểm được tô bởi một trong số K mầu. Các mầu được đánh từ 1 đến K. Một tam giác với ba đỉnh là ba điểm có cùng mầu trong số N điểm đã cho được gọi là tam giác cùng mầu. Yêu cầu Tìm một số lượng tam giác cân từng mầu. Dữ liệu Vào từ file văn bản Dòng đầu tiên chứa hai số nguyên N và K được ghi cách nhau bởi dấu cách 1 N 200 1 K 4 Dòng thứ i trong số N dòng tiếp theo chứa 3 số Xi yi ci được ghi cách nhau bởi dấu cách trong đó Xi yi là toạ độ của điểm Ai còn c là màu của Ai các số Xi yi có trị tuyệt đối không quá 32000 . Kết quả Ghi ra file văn bản số lượng tam giác cùng màu. Ví dụ Ly 8 2 2 1 2 2 1 -4 2 -2 2 1 3 -3 1 3 -1 2 4 -4 2 -3 -1 1 -1 -1 1 Minh hoạ Bài 2. Hình xoắn ốc Bằng cách viết liên tiếp các số tự nhiên từ 1 tới N ta nhận được một dãy các số. Ví dụ với N 18 ta có dãy các chữ số 123456789101112131415161718. Sau đó điền dãy chữ số này vào các điểm nguyên của mặt phẳng toạ độ theo chiều xoắn ốc bắt đầu từ điếm 0 0 như sơ đồ sau y ĩ k 1 5 4 3 1 4 6 1 2 0 1 7 8 9 1 X 5 1 6 1 7 Như vậy với một số N cho trước một số điểm nguyên của mặt phẳng toạ độ cho chứa một chữ số. Yêu cầu Cho hai số nguyên x và y hãy a. Tìm số tự nhiên N lớn nhất sao cho điểm x y chưa có chữ số. b. Giả sử điểm x y đã có chữ số. Hãy tìm chữ số K được điền tại điểm x y . Dữ liệu Vào từ file văn bản gồm một dòng chứa 3 số nguyên q x và y trong đó q 1 nếu là yêu cầu a và q 2 nếu là yêu cầu b còn x và y có giá trị tuyệt đối không vượt quá 20000. .