- Đề thi học sinh giỏi cấp THPT tỉnh Lâm Đồng môn Tin họcNăm học Tải về Bài viết đã được lưu (adsbygoogle=window.adsbygoogle||[]).push({})SỞ GIÁO DỤC & ĐÀO TẠOLÂM ĐỒNGKÌ THI CHỌN HỌC SINH GIỎI CẤP TỈNHNĂM HỌC 2010- 2011MÔN THI: TIN HỌC - THPTThời gian: 150 phút (Không kể thời gian giao đề)Ngày thi Cấu trúc đề thi: STT Tên bài Tên file bài làm Tên file INPUT Tên file OUTPUT1Tam giácTAMGIAC.*TAMGIAC.INPTAMGIAC.OUT2Gặp nhauGAPNHAU.*GAPNHAU.INPGAPNHAU.OUT2DominoDOMINO.*DOMINO.INPDOMINO.OUTDấu * được thay thế bởi PAS, PP hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++(adsbygoogle=window.adsbygoogle||[]).push({})(function(n,t,i,r){r=t.createElement("script");r.defer=!0;r.async=!0;r.src=n.location.protocol+i;t.head.appendChild(r)})(window,document,"//a.vdo.ai/core/v-vndoc-v1/vdo.ai.js")Hãy lập trình để giải các bài toán sau:Bài 1: Tam giác (6 điểm)Trong mặt phẳng toạ độ Oxy cho N điểm, mỗi điểm Ni được xác định bởi cặp toạ độ nguyên xi, yi. - Ghi diện tích các tam giác tìm được vào tệp TAMGIAC.OUT theo thứ tự tăng dần.Biết công thức tính diện tích tam giác: với a, b, c là độ dài của 3 cạnh của tam giác.Dữ liệu vào: được cho trong tệp TAMGIAC.INP gồm có các dòng:- Dòng đầu tiên có 1 số nguyên dương N (1 ≤ N ≤ 100) .(adsbygoogle=window.adsbygoogle||[]).push. - Nếu không tồn tại tam giác thì ghi là NULL.Bài 2: Gặp nhau (7 điểm)Hoà và Thân là bạn thân của nhau, hai người xa nhau đã lâu, nay mới liên lạc được với nhau qua Internet và họ hẹn gặp nhau tại thành phố Hồ Chí Minh. - Hoà và Thân sinh sống và làm việc tại hai thành phố khác nhau.(adsbygoogle=window.adsbygoogle||[]).push({})Hãy tìm cách giúp Hoà và Thân đến được thành phố Hồ Chí Minh bằng các chuyến bay có thể có nhưng để tiết kiệm chi phí, tại mỗi sân bay mỗi người chỉ được ghé lại 1 lần và mỗi người phải qua ít thành phố nhất.Các thành phố xem như là các đỉnh của một đồ thị vô hướng gồm N đỉnh được mã số từ 1 đến N (1 ≤ i ≤ 100). - Chỉ một số cặp thành phố mới có đường bay còn lại thì không. - Giả sử đỉnh xuất phát không trùng đỉnh đích.Dữ liệu vào: được cho trong tệp GAPNHAU.INP gồm có các dòng:- Dòng đầu tiên, được gọi là dòng 0, chứa 4 số tự nhiên N, H, T, D(1 ≤ H, T, D ≤ N), trong đó N là số thành phố có sân bay, H là nơi Hoà đang sinh sống và công tác còn T là thành phố mà Thân sống và làm việc, D là mã số của thành phố Hồ Chí Minh nơi mà Hoà và Thân hẹn gặp. - số 1 nghĩa là tồn tại đường bay giữa hai đỉnh i , j) các số cách nhau ít nhất 1 khoảng cách.(adsbygoogle=window.adsbygoogle||[]).push. - Dòng Có 9 đỉnh mã số từ 1 đến 9, cần tìm đường đi từ đỉnh 6 đến đỉnh 7 và từ đỉnh 2 đến đỉnh 7.- Dòng đỉnh 1 được nối với các đỉnh 2, 4, 5, và 6. - Không có cạnh nối đỉnh 1 với các đỉnh 3, 7, 8 và 9.- Dòng đỉnh 2 được nối với các đỉnh 3 và 4. - Không có cạnh nối đỉnh 2 với các đỉnh và 9. - thông tin về đỉnh N không cần hiển thị vì với mỗi đỉnh i ta chỉ liệt kê các đỉnh j>i tạo thành đường đi (i,j).Dữ liệu ra: được ghi trong tệp văn bản GAPNHAU.OUT:- Dòng đầu tiên ghi số tự nhiên k, l là số đỉnh trên đường đi từ H đến D và số đỉnh trên đường từ T tới D (nếu không có đường đi thì ghi số 0. - Dòng thứ 2 ghi lần lượt các đỉnh có trên đường đi từ H đến D. - (Nếu không có thì ghi 0)- Dòng thứ 3 ghi lần lượt các đỉnh có trên đường đi từ T đến D. - Trong ma trận, người ta đặt v vách ngăn giữa hai ô kề cạnh nhau.(adsbygoogle=window.adsbygoogle||[]).push({})Hãy tìm cách đặt nhiều nhất k quân domino, mỗi quân gồm hai ô kề cạnh nhau trên ma trận và không có vách ngăn ở giữa.Dữ liệu vào: được cho trong tệp DOMINO.INP.- Dòng đầu tiên gồm 3: số n là số dòng, số m là số cột và số v là số vách ngăn (các số cách nhau ít nhất 1 khoảng cách. - V dòng tiếp theo, mỗi dòng có 2 số a, b (các số cách nhau ít nhất 1 khoảng cách) cho biết vách ngăn đặt giữa hai ô này.Dữ liệu ra: được ghi vào tệp DOMINO.OUT.- Dòng đầu tiên ghi số k là số quân domino tối đa đặt được trên Ma trận.- K dòng tiếp theo, mỗi dòng 2 số x, y (các số cách nhau ít nhất 1 khoảng cách) cho biết số hiệu của 2 ô kề cạnh nhau tạo thành một quân domino.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt