Đề thi chọn đội tuyển dự thi học sinh giỏi Quốc gia năm 2019 môn Tin học - Sở GD&ĐT tỉnh Bắc Ninh

Nội dung text: Đề thi chọn đội tuyển dự thi học sinh giỏi Quốc gia năm 2019 môn Tin học - Sở GD&ĐT tỉnh Bắc Ninh

1. UBND TỈNH BẮC NINH ĐỀ THI CHỌN ĐỘI TUYỂN SỞ GIÁO DỤC VÀ ĐÀO TẠO DỰ THI HỌC SINH GIỎI QUỐC GIA THPT NĂM 2019 Môn thi: Tin học ĐỀ CHÍNH THỨC Thời gian làm bài: 180 phút (không kể thời gian giao đề) Ngày thi thứ hai: 05 tháng 10 năm 2018 (Đề thi gồm 03 trang) Stt Tên bài Tên file INPUT OUTPUT Điểm 1 Chơi chữ WORDS.* WORDS.INP WORDS.OUT 7 2 Xóa số REMOVE.* REMOVE.INP REMOVE.OUT 7 3 Giao thông thành phố CITY.* CITY.INP CITY.OUT 6 Chú ý: * tương ứng với phần mở rộng phần mềm thí sinh sử dụng Bài 1. CHƠI CHỮ Tú và Trà chơi một trò chơi trên các từ. Họ chỉ nói các từ được tạo thành từ các nguyên âm với qui tắc chữ cái đầu tiên của từ được nói tiếp theo phải trùng với chữ cái cuối cùng của từ được nói trước đó. Mỗi từ chỉ được dùng 1 lần và chỉ được dùng các từ có trong từ điển cho trước. Điểm của trò chơi là tổng độ dài của các từ được nói ra. Viết chương trình xác định điểm lớn nhất của trò chơi nếu như chỉ sử dụng các từ có trong từ điển cho trước. Dữ liệu: Vào từ file văn bản WORDS.INP Dòng đầu tiên chứa số tự nhiên N (1≤N≤16), xác định số lượng các từ có trong từ điển. N dòng tiếp theo mỗi dòng chứa 1 từ có trong từ điển. Mỗi từ là một dãy chỉ gồm các ký tự 'A', 'E', 'I', 'O', 'U. Độ dài của mỗi từ không vượt quá 100. Tất cả các từ là khác nhau. Kết quả: Ghi ra file văn bản WORDS.OUT Chứa một số nguyên duy nhất là điểm lớn nhất nhận được của trò chơi Ví dụ: WORDS.INP WORDS.OUT WORDS.INP WORDS.OUT 3 8 4 13 AEIOU AEEEO UIU OEOAEEE EO AO O Bài 2. XÓA SỐ Trong quyển vở ghi chép Toán của Thiệp có hai dãy số có cùng độ dài N. Anh ta định nghĩa Giá trị của hai dãy là tổng các tích ghép cặp dãy thứ nhất với dãy thứ hai đảo ngược. Ví dụ với hai dãy sau: 3 −4 −3 −2 2 0 −3 0 5 −1 3 2 1
2. Thì giá trị của hai dãy này là 3.2 + (−4).3 + (−3).(−1) + (−2).5 + 2.0 + 0.(−3) = −13 Thiệp rất thích cặp dãy có giá trị lớn. Anh ta quyết định xóa B phần tử đầu tiên (có thể là 0) và xóa E phần tử cuối cùng (có thể là 0) của hai dãy sao cho giá trị hai dãy còn lại là lớn nhất. Viết chương trình xác định giá trị lớn nhất tìm được, B và E. Dữ liệu: Vào từ file văn bản REMOVE.INP Dòng đầu tiên ghi số nguyên N (1≤N≤2000) là độ dài của hai dãy ban đầu. Hai dòng tiếp theo, mỗi dòng có N số nguyên mô tả hai dãy ban đầu. Tất cả các số trong hai dãy có giá trị nằm trong khoảng từ -1000 đến 1000. Kết quả: Ghi ra file văn bản REMOVE.OUT Hai số B và E được ghi trên dòng đầu (0≤B, E≤N, B+E<N) Dòng thứ hai ghi giá trị lớn nhất tìm được. Nếu có nhiều cách chọn B, E thì chỉ cần đưa ra một trong số chúng. Ví dụ: REMOVE.INP REMOVE.OUT 6 0 3 3 -4 -3 -2 2 0 24 -3 0 5 -1 3 2 Bài 3. Giao thông thành phố Năm 2018, để chuẩn bị cho dự án nâng cấp lên thành phố loại 1, thành phố Bắc Ninh đã thử lập lại mô hình giao thông thành phố. Khi mô hình được chuyển lên Internet, có rất nhiều ý kiến phàn nàn về tính hợp lý của nó, đặc biệt tất cả các ý kiến đều cho rằng hệ thống đường phố như vậy là quá nhiều, làm tăng chi phí xây dựng cũng như bảo trì. UBND thành phố đã yêu cầu bỏ đi một số đường trong dự án xây dựng thành phố thỏa mãn: - Nếu giữa hai địa điểm bất kỳ trong dự án ban đầu có ít nhất một đường đi thì việc sửa đổi này không làm ảnh hưởng tới độ dài đường đi ngắn nhất giữa hai địa điểm đó. - Tổng độ dài của những đường phố được giữ lại là ngắn nhất có thể Dữ liệu: Vào từ file văn bản CITY.INP, chứa bản đồ dự án Dòng thứ nhất ghi số địa điểm N và số đường phố M (giữa hai địa điểm bất kỳ có nhiều nhất là một đường phố nối chúng, N 200; 0 M N*(N-1)/2. M dòng tiếp theo mỗi dòng ghi ba số nguyên dương u, v, c cho biết có đường hai chiều nối giữa hai địa điểm u, v và độ dài của con đường đó là c (c 10000) Kết quả: Ghi ra file văn bản CITY.OUT, chứa kết quả sau khi sửa đổi Dòng thứ nhất ghi hai số K, D. Trong đó K là số đường phố còn lại, còn D là tổng độ dài của các con đường phố còn lại. 2
3. K dòng tiếp theo, mỗi dòng ghi hai số nguyên dương p, q cho biết cần phải giữ lại con đường nối địa điểm p với địa điểm q. Ví dụ: CITY.INP CITY.OUT 10 12 9 21 1 2 1 1 2 1 5 2 1 5 2 6 7 3 4 3 4 1 3 7 3 7 2 5 6 4 8 8 6 7 5 6 3 6 9 6 7 1 7 8 6 9 2 9 10 7 8 5 7 10 8 9 10 4 Hết (Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm) Họ và tên thí sinh : .Số báo danh : 3