Đề thi chọn HSG môn Tin học lớp 12 Vĩnh Phúc năm học 2013 - 2014  (Bấm vào liên kết phía dưới để tải xuống)

Đề thi chọn HSG môn Tin học lớp 12 Vĩnh Phúc năm học 2013 - 2014. Gồm có 3 bài, bài 1: Xây dựng hoán vị, bài 2: Giá trị thứ i, bài 3: Đường đi ngắn nhất. Đề này sử dụng các kiến thức về dãy số, thuật toán quy hoạch động và đồ thị để giải.

ĐỀ CHÍNH THỨC
Tổng quan về đề thi:
Lập chương trình giải các bài toán sau:

Bài 1. Xây dựng hoán vị
Hoán vị P là một dãy có thứ tự xác định gồm N số nguyên phân biệt P1, P2, ..., Pn. Gọi phần tử thứ i của hoán vị P là PiPi (1<=i<=N), không vượt quá N, N gọi là độ dài của hoán vị P.
Cho dãy số nguyên a1, a2, ..., aN Người ta xây dựng dãy đã cho thành một hoán vị P qua một số bước, tại mỗi bước chỉ được phép tăng hoặc giảm một đơn vị của phần tử ai (1 <= i <= N) bất kỳ.
Tính số bước ít nhất để xây dựng được một hoán vị từ dãy đã cho.
Dữ liệu: 
- Dòng đầu ghi số nguyên N (1<=N<=3.105) là độ dài của hoán vị cần tìm.
- Dòng thứ 2 ghi N số nguyên a1, a2, ..., aN (-109<=ai<=109). các số viết trên cùng một dòngvà cách nhau bởi ít nhất một dấu cách
Kết quả: 
- Một dỏng duy nhất ghi kết quả cần tìm

Bài 2. Giá trị thứ i
Bờm viết liên tiếp một chuỗi số nguyên dương có dạng S1S2S3...Sk trong đó Si là một dãy số nguyên được viết liên tiếp từ 1 tới i.
Bờm yêu cầu Cuội nhập vào số i, in ra giá trị của vị trí thứ i trong chuỗi.
Dữ liệu
-Một dòng duy nhất ghi số i (1i2 147 483 647)
Kết quả
- Ghi một số nguyên duy nhất là giá trị của phần tửtại vị trí thứ i

Tải xuống để xem tài liệu hoàn chỉnh - Chia sẻ cho bạn bè nếu trang web có ích với bạn!
Nguồn tài liệu:

Bạn cũng có thể quan tâm:

Bài tập môn Tin học lớp Lớp 12
Mời bạn tham gia hỏi - đáp
Thư viện bài tập © 2014 -2017 - Liên hệ - Giới thiệu - Bản quyền - Chính sách bảo mật - Sitemap