Đề thi HSG quảng Ngaic 2004 -2005
Chia sẻ bởi Trần Quang Diệu |
Ngày 26/04/2019 |
52
Chia sẻ tài liệu: Đề thi HSG quảng Ngaic 2004 -2005 thuộc Tin học 11
Nội dung tài liệu:
SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI TỈNH – THPT
QUẢNG NGÃI Năm học 2004-2005
Tên bài
Tên chương trình
Dữ liệu vào
Kết quả
BÀI 1
Hoán vị thuận thế
PERMUTE.PAS
Bàn phím
Màn hình
BÀI 2
Các ký tự
LETTERS.PAS
LETTERS.INP
LETTERS.OUT
Bài 1: hoán vị thuận thế Tên chương trình: PERMUTE.PAS
Cho a = (a1, a2, ...., aN) là một hoán vị của dãy số tự nhiên 1...N. Ta xây dựng dãy b=(b1,b2,...,bN) và gọi là thuận thế của hoán vị a như sau:
Với mọi i =1..N, bi là số lượng các phần tử nhỏ thua ai và đứng trước ai
Ví dụ: N =7 ; a=(6,1,3,5,7,4,2) ta có thuận thế của a là b=(0,0,1,2,4,2,1)
Cho N và một hoán vị a. Hãy tìm thuận thế của a.
Cho N và một thuận thế b. Hãy tìm hoán vị sinh ra thuận thế b.
Dữ liệu : vào từ bàn phím
Đối với câu a: Nhập vào từ bàn phím: số N và một hoán vị a
Đối với câu b: Nhập vào từ bàn phím: số N và một thuận thế b.
Kết quả: in ra màn hình
Đối với câu a: in ra màn hình thuận thế của a
Đối với câu b: in ra màn hình hoán vị sinh ra thuận thế b.
Ví dụ:
Nhập N = 9 a = 2 1 7 6 5 4 3 8 9
Thuận thế của a là : 0 0 2 2 2 2 2 7 8
Nhập N = 9 b = 0 1 1 2 4 1 5 5 8
Hoán vị sinh ra thuận thế b: 1 5 3 4 8 2 7 6 9
Bài 2: Các ký tự Tên chương trình: LETTERS.PAS
Trò chơi được mô tả như sau: trên một bảng hình chữ nhật chia R hàng và C cột có các ký tự chữ hoa (A-Z) được viết trên mỗi ô của bảng. Trước khi bắt đầu trò chơi có một hình ở góc trên bên trái của bảng(hàng 1, cột 1). Trong mỗi bước di chuyển, một người chơi có thể di chuyển hình đến vị trí các ô liền kề ( lên trên, xuống dưới, sang trái, sang phải) với ràng buộc rằng hình không thể di chuyển đến vị trí kế tiếp nếu ô này chứa ký tự đã xuất hiện mà hình đã di chuyển qua. Mục đích của trò chơi là chơi để có nhiều bước di chuyển nhất có thể được.
Viết chương trình xác định số vị trí tối đa trong bảng mà hình có thể viếng thăm trong trò chơi.
Dữ liệu: Vào từ tập tin văn bản LETTERS.INP
Dòng thứ nhất chứa hai số nguyên R và C, được viết cách nhau bởi một dấu cách,
(1 ≤ R, C ≤ 20 )
R dòng tiếp theo chứa, mỗi dòng chứa 1 xâu ký tự. Mỗi dòng biểu diễn một hàng của bảng.
Kết quả : Ghi vào tập tin văn bản LETTERS.OUT một số nguyên là giá trị lớn nhất các vị trí mà hình có thể di chuyển trên bảng.
Ví dụ:
letters.inp
letters.inp
2 4
CAAB
ADCB
3 6
HFDFFB
AJHGDH
DGAGEH
letters.out
letters.out
3
6
Bài 1
ses crt;
const MN=100; n=9;
esc=#27;
type mang=array[0..mn] of byte;
var a, b : mang;
procedure xemmang;
var i:word;
begin
for i:=1 to n do write(a[i]:3);
end;
procedure sinhhoanvi;
var i,j, t : word;
begin
for i:=1 to n do a[i]:=i;
for i:=1 to n do
begin
j:=random(n)+1;
t:=a[1];
a[1]:=a[j];
a[j]:=t;
end;
end;
procedure hvtt;
var i,j:word;
begin
for i:=n downto 1 do
for j:=1 to i do
if a[j]>=a[i] then dec(a[j]);
end;
procedure run;
const bg=13;
begin
clrscr
QUẢNG NGÃI Năm học 2004-2005
Tên bài
Tên chương trình
Dữ liệu vào
Kết quả
BÀI 1
Hoán vị thuận thế
PERMUTE.PAS
Bàn phím
Màn hình
BÀI 2
Các ký tự
LETTERS.PAS
LETTERS.INP
LETTERS.OUT
Bài 1: hoán vị thuận thế Tên chương trình: PERMUTE.PAS
Cho a = (a1, a2, ...., aN) là một hoán vị của dãy số tự nhiên 1...N. Ta xây dựng dãy b=(b1,b2,...,bN) và gọi là thuận thế của hoán vị a như sau:
Với mọi i =1..N, bi là số lượng các phần tử nhỏ thua ai và đứng trước ai
Ví dụ: N =7 ; a=(6,1,3,5,7,4,2) ta có thuận thế của a là b=(0,0,1,2,4,2,1)
Cho N và một hoán vị a. Hãy tìm thuận thế của a.
Cho N và một thuận thế b. Hãy tìm hoán vị sinh ra thuận thế b.
Dữ liệu : vào từ bàn phím
Đối với câu a: Nhập vào từ bàn phím: số N và một hoán vị a
Đối với câu b: Nhập vào từ bàn phím: số N và một thuận thế b.
Kết quả: in ra màn hình
Đối với câu a: in ra màn hình thuận thế của a
Đối với câu b: in ra màn hình hoán vị sinh ra thuận thế b.
Ví dụ:
Nhập N = 9 a = 2 1 7 6 5 4 3 8 9
Thuận thế của a là : 0 0 2 2 2 2 2 7 8
Nhập N = 9 b = 0 1 1 2 4 1 5 5 8
Hoán vị sinh ra thuận thế b: 1 5 3 4 8 2 7 6 9
Bài 2: Các ký tự Tên chương trình: LETTERS.PAS
Trò chơi được mô tả như sau: trên một bảng hình chữ nhật chia R hàng và C cột có các ký tự chữ hoa (A-Z) được viết trên mỗi ô của bảng. Trước khi bắt đầu trò chơi có một hình ở góc trên bên trái của bảng(hàng 1, cột 1). Trong mỗi bước di chuyển, một người chơi có thể di chuyển hình đến vị trí các ô liền kề ( lên trên, xuống dưới, sang trái, sang phải) với ràng buộc rằng hình không thể di chuyển đến vị trí kế tiếp nếu ô này chứa ký tự đã xuất hiện mà hình đã di chuyển qua. Mục đích của trò chơi là chơi để có nhiều bước di chuyển nhất có thể được.
Viết chương trình xác định số vị trí tối đa trong bảng mà hình có thể viếng thăm trong trò chơi.
Dữ liệu: Vào từ tập tin văn bản LETTERS.INP
Dòng thứ nhất chứa hai số nguyên R và C, được viết cách nhau bởi một dấu cách,
(1 ≤ R, C ≤ 20 )
R dòng tiếp theo chứa, mỗi dòng chứa 1 xâu ký tự. Mỗi dòng biểu diễn một hàng của bảng.
Kết quả : Ghi vào tập tin văn bản LETTERS.OUT một số nguyên là giá trị lớn nhất các vị trí mà hình có thể di chuyển trên bảng.
Ví dụ:
letters.inp
letters.inp
2 4
CAAB
ADCB
3 6
HFDFFB
AJHGDH
DGAGEH
letters.out
letters.out
3
6
Bài 1
ses crt;
const MN=100; n=9;
esc=#27;
type mang=array[0..mn] of byte;
var a, b : mang;
procedure xemmang;
var i:word;
begin
for i:=1 to n do write(a[i]:3);
end;
procedure sinhhoanvi;
var i,j, t : word;
begin
for i:=1 to n do a[i]:=i;
for i:=1 to n do
begin
j:=random(n)+1;
t:=a[1];
a[1]:=a[j];
a[j]:=t;
end;
end;
procedure hvtt;
var i,j:word;
begin
for i:=n downto 1 do
for j:=1 to i do
if a[j]>=a[i] then dec(a[j]);
end;
procedure run;
const bg=13;
begin
clrscr
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Trần Quang Diệu
Dung lượng: |
Lượt tài: 0
Loại file:
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)