Đề thi học sinh giỏi tin 11 | Nghệ An năm 2015 -2016
- Thứ tư - 26/07/2023 23:36
- In ra
- Đóng cửa sổ này
Đề thi học sinh giỏi tin 11 | Nghệ An năm 2015 -2016
Tổng quan bài thi
Bài 1. (6 điểm) CENSOR
Cho một xâu S có độ dài tối đa là 106 ký tự. Trong xâu S người ta loại bỏ sự xuất hiện của một xâu con T có độ dài ≤ 100 ký tự. Để làm điều này, người ta tìm sự xuất hiện của T lần đầu tiên trong S và xóa nó. Sau đó cứ lặp đi lặp lại quá trình này cho đến khi không còn sự xuất hiện của T trong S. Lưu ý rằng việc xóa một lần xuất hiện có thể tạo ra một sự xuất hiện mới của T chưa từng tồn tại trước đó. Hãy xác định nội dung cuối cùng của xâu S.
Dữ liệu: Vào từ file văn bản CENSOR.INP:
Ví dụ
Bài 2. (6 điểm) BEAUTY
Một số được gọi là đẹp nếu tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố.
Ví dụ, 12 là một số đẹp vì 12 + 22 = 5 là số nguyên tố.
Các số đẹp được đánh số theo thứ tự tăng dần của giá trị, bắt đầu từ 1 trở đi.
Yêu cầu: Cho số nguyên N (1 ≤ N ≤ 106). Hãy tìm số đẹp thứ N.
Dữ liệu: Vào từ file BEAUTY.INP
Gồm nhiều tests, mỗi test cho trên một dòng chứa một số nguyên N.
Kết quả: Ghi ra file BEAUTY.OUT
Mỗi test đưa ra trên một dòng là kết quả số đẹp tìm được tương ứng của mỗi test từ file dữ liệu vào.
Ví dụ:
Bài 3. (4 điểm) RADIO
Một đài phát thanh cần phát một thông tin quan trọng tới người dân. Để chắc chắn mọi người đều nghe được thông tin nên đài sẽ phát đi phát lại thông tin đó nhiều lần. Cho một chuỗi các ký tự mà một người dân nghe được. Hãy xác định chuỗi ngắn nhất các ký tự mà có thể là thông tin cần phát. Chính xác hơn là hãy xác định chuỗi S’ từ chuỗi S đã cho sao cho S có trong chuỗi lặp lại S’+S’+…..+S’.
Dữ liệu: Vào từ file RADIO.INP
Dòng đầu chứa một số nguyên L là độ dài chuỗi S. (1 < L < 1000000)
Dòng thứ 2 chứa đúng L ký tự của chuỗi S. Chuỗi chỉ chứa các ký tự từ a..z.
Kết quả: Ghi ra file RADIO.OUT
Độ dài L’ của xâu S’. Lưu ý L’ phải nhỏ nhất có thể.
Ví dụ:
Giải thích test: Các thông tin có thể là abc, cab, abcabc, thông tin ngắn nhất là 3 ký tự.
Hạn chế: Có 60% test có L < 100.
Bài 4. (4 điểm) NORMA
Mirko có một dãy số và cậu ấy có thể bán nó cho cửa hàng đồ chơi. Giá trị của một dãy số là tích min.max.L, trong đó min là số có giá trị nhỏ nhất, max là số có giá trị lớn nhất và L là số các số trong dãy. Mirko dự định sẽ bán một dãy con các số liên tiếp từ dãy số cậu ta có. Hãy giúp Mirko tính tổng giá trị của tất cả các dãy con mà cậu ta có thể bán.
Dữ liệu: Vào từ file NORMA.INP
- Dòng đầu tiên chứa một số N (1 < N < 500 000).
- Mỗi dòng trong N dòng sau chứa một số nguyên tương ứng trong dãy số Mirko có. (các số trong dãy có giá trị thuộc [1, 108]).
Kết quả: Ghi ra file NORMA.OUT
Chỉ một số duy nhất là 9 chữ số cuối cùng của tổng tìm được.
Ví dụ:
Giải thích test:
Test 1: các dãy có thể bán (1); (3); (1, 3) giá trị tương ứng: 1, 9, 6 và tổng là 16.
Test 2: Các dãy (2), (4), (1), (4) (2,4), (4,1), (1,4), (2, 4, 1), (4,1,4), (2,4,1,4) và giá trị tương ứng là: 4, 16, 1, 16, 16, 8, 8, 12, 12, 16 và tổng là: 109
Hạn chế: Có 70% test có N < 5000.
---------Hết---------
| Tên bài | File Input | File Output | Thời gian chạy |
| CENSOR | CENSOR.INP | CENSOR.OUT | 1 giây |
| BEAUTY | BEAUTY.INP | BEAUTY.OUT | 1 giây |
| RADIO | RADIO.INP | RADIO.OUT | 1 giây |
| NORMA | NORMA.INP | NORMA.OUT | 3 giây |
Bài 1. (6 điểm) CENSOR
Cho một xâu S có độ dài tối đa là 106 ký tự. Trong xâu S người ta loại bỏ sự xuất hiện của một xâu con T có độ dài ≤ 100 ký tự. Để làm điều này, người ta tìm sự xuất hiện của T lần đầu tiên trong S và xóa nó. Sau đó cứ lặp đi lặp lại quá trình này cho đến khi không còn sự xuất hiện của T trong S. Lưu ý rằng việc xóa một lần xuất hiện có thể tạo ra một sự xuất hiện mới của T chưa từng tồn tại trước đó. Hãy xác định nội dung cuối cùng của xâu S.
Dữ liệu: Vào từ file văn bản CENSOR.INP:
- Dòng đầu tiên chứa xâu S.
- Dòng thứ hai chứa xâu T. Chiều dài của xâu T bé hơn chiều dài của S, và tất cả các kí tự của S và T đều là ký tự thường (trong phạm vi từ a..z).
Ví dụ
| CENSOR.INP | CENSOR.OUT |
| whatthemomooofun moo |
whatthefun |
Bài 2. (6 điểm) BEAUTY
Một số được gọi là đẹp nếu tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố.
Ví dụ, 12 là một số đẹp vì 12 + 22 = 5 là số nguyên tố.
Các số đẹp được đánh số theo thứ tự tăng dần của giá trị, bắt đầu từ 1 trở đi.
Yêu cầu: Cho số nguyên N (1 ≤ N ≤ 106). Hãy tìm số đẹp thứ N.
Dữ liệu: Vào từ file BEAUTY.INP
Gồm nhiều tests, mỗi test cho trên một dòng chứa một số nguyên N.
Kết quả: Ghi ra file BEAUTY.OUT
Mỗi test đưa ra trên một dòng là kết quả số đẹp tìm được tương ứng của mỗi test từ file dữ liệu vào.
Ví dụ:
| BEAUTY.INP | BEAUTY.OUT |
| 1 6 |
11 23 |
Một đài phát thanh cần phát một thông tin quan trọng tới người dân. Để chắc chắn mọi người đều nghe được thông tin nên đài sẽ phát đi phát lại thông tin đó nhiều lần. Cho một chuỗi các ký tự mà một người dân nghe được. Hãy xác định chuỗi ngắn nhất các ký tự mà có thể là thông tin cần phát. Chính xác hơn là hãy xác định chuỗi S’ từ chuỗi S đã cho sao cho S có trong chuỗi lặp lại S’+S’+…..+S’.
Dữ liệu: Vào từ file RADIO.INP
Dòng đầu chứa một số nguyên L là độ dài chuỗi S. (1 < L < 1000000)
Dòng thứ 2 chứa đúng L ký tự của chuỗi S. Chuỗi chỉ chứa các ký tự từ a..z.
Kết quả: Ghi ra file RADIO.OUT
Độ dài L’ của xâu S’. Lưu ý L’ phải nhỏ nhất có thể.
Ví dụ:
| RADIO.INP | RADIO.OUT |
| 8 cabcabca |
3 |
Hạn chế: Có 60% test có L < 100.
Bài 4. (4 điểm) NORMA
Mirko có một dãy số và cậu ấy có thể bán nó cho cửa hàng đồ chơi. Giá trị của một dãy số là tích min.max.L, trong đó min là số có giá trị nhỏ nhất, max là số có giá trị lớn nhất và L là số các số trong dãy. Mirko dự định sẽ bán một dãy con các số liên tiếp từ dãy số cậu ta có. Hãy giúp Mirko tính tổng giá trị của tất cả các dãy con mà cậu ta có thể bán.
Dữ liệu: Vào từ file NORMA.INP
- Dòng đầu tiên chứa một số N (1 < N < 500 000).
- Mỗi dòng trong N dòng sau chứa một số nguyên tương ứng trong dãy số Mirko có. (các số trong dãy có giá trị thuộc [1, 108]).
Kết quả: Ghi ra file NORMA.OUT
Chỉ một số duy nhất là 9 chữ số cuối cùng của tổng tìm được.
Ví dụ:
| NORMA.INP | NORMA.OUT | NORMA.INP | NORMA.OUT | NORMA.INP | NORMA.OUT |
| 2 1 3 |
16 | 4 2 4 1 4 |
109 | 6 8 1 3 9 7 4 |
1042 |
Giải thích test:
Test 1: các dãy có thể bán (1); (3); (1, 3) giá trị tương ứng: 1, 9, 6 và tổng là 16.
Test 2: Các dãy (2), (4), (1), (4) (2,4), (4,1), (1,4), (2, 4, 1), (4,1,4), (2,4,1,4) và giá trị tương ứng là: 4, 16, 1, 16, 16, 8, 8, 12, 12, 16 và tổng là: 109
Hạn chế: Có 70% test có N < 5000.
---------Hết---------