Luyện thi HSG Tin học THCS Đề số 5

PHÒNG GD & DT
QUẬN HOÀN KIẾM


LUYỆN THI HSG LỚP 9 THCS NĂM HỌC 2012-2013
ĐỀ THI MÔN: TIN HỌC
Thời gian làm bài: 150 phút, không kể thời gian giao đề



Tổng quan
TT
Tên bài
File
chương trình
File
dữ liệu
File
kết quả
Thời
gian

1
Hoán vị
HOANVI.PAS
HOANVI.INP
HOANVI.OUT
1s/test

2
Bảng nghịch thế
NGHICHTH.PAS
NGHICHTH.INP
NGHICHTH.OUT
1s/test

3
Số nguyên dài
SNDAI.PAS
SNDAI.INP
SNDAI.OUT
1s/test


Bài 1. (7,0 điểm) HOÁN VỊ 
Hoán vị của n số nguyên dương đầu tiên là một cách sắp xếp các số 1, 2, …, n theo một thứ tự nào đó.
Yêu cầu: Viết chương trình in ra tất cả các hoán vị của n số nguyên dương đầu tiên.
Dữ liệu: đọc từ file văn bản HOANVI.INP, gồm K dòng, mỗi dòng ghi một giá trị, là số nguyên dương n.
Kết quả: Ghi ra màn hình và file văn bản HOANVI.OUT gồm K dòng, mỗi dòng số hoán vị tìm được, sau đó là dãy các hoán vị tìm được, theo quy cách nêu trong ví dụ.
Ví dụ:
HOANVI.INP
HOANVI.OUT

2 3
2 [1 2] [2 1]
6 [1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]


Bài 2. (6 điểm) BẢNG NGHỊCH THẾ
Giả sử P = {P1, P2, …, Pn} là một hoán vị của 1, 2, …, n. Bảng nghịch thể của hoán vị P là dãy T = {T1, T2, …, Tn} trong đó Ti bằng số lượng các phần tử trong hoán vị P, đứng trước i và lớn hơn i.
Yêu cầu: Viết chương trình tìm lại hoán vị P khi biết bảng nghịch thế T.
Dữ liệu vào: cho trong File NGHICHTH.INP gồm K dòng, mỗi dòng chứa một bảng nghịch thế.
Kết quả: ghi ra màn hình và ra file NGHICHTH.OUT gồm K dòng, mỗi dòng ghi hoán vị tìm được.
Ví dụ:
NGHICHTH.INP
NGHICHTH.OUT

2 1 0 0 0
2 3 6 4 0 2 2 1 0
3 2 1 4 5
5 9 1 8 2 6 4 7 3






Bài 3. (7 điểm) SỐ NGUYÊN DÀI
Kiểu Longint của Pascal chỉ chứa được các số nguyên đến 10 chữ số. Số nguyên dài là những số nguyên có nhiều hơn 10 chữ số và do đó, để nhập các số nguyên dài, người ta thường dùng biến kiểu String, còn để tính toán, người ta thường dùng mảng mà mỗi phần tử là một biến kiểu Longint.
Yêu cầu: Viết chương trình tìm phần dư khi chia một số nguyên dài cho một số nguyên kiểu Longint.
Dữ liệu vào: cho trong file SNDAI.INP gồm K cặp dòng, cặp dòng thứ i chứa các dữ liệu sau:
Dòng đầu tiên chứa số nguyên Ni (2 ≤ N ≤30000)
Dòng tiếp theo ghi số nguyên dài Mi.
Kết quả: ghi ra màn hình và file SNDAI.OUT, gồm K dòng, dòng thứ i ghi phần dư của phép chia số nguyên dài Mi cho số nguyên Ni.
Ví dụ:
SNDAI.INP
SNDAI.OUT

32233
1282377303
32335
28336365374674
19631
7904




---Hết---
Cán bộ coi thi không giải thích gì thêm.
Họ và tên thí sinh:……………………………………………Số báo danh:…………………..


DỮ LIỆU ĐỂ KIỂM TRA (TEST):

HOANVI.INP
HOANVI.OUT

4
5
6



NGHICHTH.INP
NGHICHTH.OUT

2 4 5 5 0 2 2 1 0
2 1 6 6 5 3 2 1 0 0
2 2 6 0 5 3 2 1 0 0






SNDAI.INP
SNDAI.OUT

39357
73532826163834763
23579
4765068009607847467
12357
128237730373532826163