Đề HSG tin học 9

Gà mờ Tổng số bài gửi : 7 Join date : 08/06/2010

CÂU 1:

Dữ liệu vào gồm nhiều dòng là các số tự nhiên N
-Phân tích các N ra dãy nhị phân
-Vị trí của các số 1 trong dãy vừa phân tích

Dữ liệu ra gồm vị trí của các số 1

ví dụ :

INPUT.INP
13
14

OUTPUT.INP
5 2 1 { giải thích 10011 }
5 3 { Nhị phân 10100}

laughing

$at wits\' end$

CÂU 2:

Dữ liệu vào gồm nhiều dòng số tự nhiên N

-Số N có bao nhiu cách tính tổng
ví dụ :
số 5
=0+1+4 ; 1
=0+2+3; 2
=0+5; 3
=1+4; 4
=2+3; 5
=5 6

6 cách

dữ liệu ra là số cách ứng với mỗi dòng file vào
big grin

dùng quy hoạch động , đệ quy :)

CÂU 3 :

không nhớ , hình như là bài làm vườn :)

Gà mờ Tổng số bài gửi : 7 Join date : 08/06/2010

đề thành phố hcm đó

Tiêu đề: Re: Đề HSG tin học 9 Tue 08 Jun 2010, 18:04

Bạn đăng lên để hỏi hay để thảo luận vậy thôi nhỉ.

Gà mờ Tổng số bài gửi : 7 Join date : 08/06/2010

giai gium :)

Tiêu đề: Re: Đề HSG tin học 9 Wed 09 Jun 2010, 21:01

Bộ ko giải được bài 1 à. straight face

Bài 2: trong phân tích ko có hai số giống nhau đúng hok.

Tiêu đề: Re: Đề HSG tin học 9 Thu 10 Jun 2010, 20:35

Bài 1 thì quá dễ.
Bài 2 theo mình những cách phân tích giống nhau dc xem là 1 cách đó. Lit rảnh thì viết code cho bạn ấy lun đi. Mai mình đi thi rùi nên tối nay ngủ sớm ko viết code dc. Thông cảm!!

Tiêu đề: Re: Đề HSG tin học 9 Mon 26 Jul 2010, 22:07

Bài 1:

Code:: Var N,i:longint;
S,S1:String;
BEGIN
Readln(N);
S:='';
While N>0 do
Begin
i:=N mod 2;
N:=N div 2;
Str(i,S1);
S:=S+S1;
End;
For i:=length(S) downto 1 do Write(S[i]);
END.

Tiêu đề: Re: Đề HSG tin học 9 Mon 26 Jul 2010, 22:10

Bài 2:

Code:: Const Maxn=100000;
Var n,i,j:longint;
a:array[0..Maxn] of longint;
BEGIN
Readln(n);
Fillchar(a,sizeof(a),0);
a[0]:=1;
For i:=1 to n do
for j:=i to n do
a[j]:=(a[j]+a[j-i]);
Write(a[j]);
END.

Tiêu đề: Re: Đề HSG tin học 9 Mon 26 Jul 2010, 22:13

Bài 2:

Code:: Const Maxn=10000;
Var n:longint;
a:array[0..Maxn,0..Maxn] of longint;
Function Xuli(i,j:longint):longint;
BEGIN
If a[i,j]=-1 then
Begin
If i=0 then
If j=0 then a[i,j]:=1
Else a[i,j]:=0
Else
If i>j then a[i,j]:=Xuli(i-1,j)
ELse a[i,j]:=Xuli(i-1,j)+Xuli(i,j-i);

End;
Xuli:=a[i,j];
END;
BEGIN
Readln(n);
Fillchar(a,sizeof(a),-1);
Write(Xuli(n,n));
END.

Tiêu đề: Re: Đề HSG tin học 9 Mon 26 Jul 2010, 22:15

Cách thứ 2 của mình còn có thể cải tiến được nữa bằng cách sinh ra các hệ số trước rồi mới (các số có dạng k*(3k +/- 1)/2 thì sẽ chạy rất nhanh!
Ai có thể giải hộ giúp mình được không?

Tiêu đề: Re: Đề HSG tin học 9 Mon 26 Jul 2010, 22:18

Đề bài 3 hình như thế này:

Nông dân John muốn xây một cái hàng rào có 4 mặt vây lấy đàn bò. Ông ta có một thanh gỗ có độ dài là 1 số nguyên N (4 <= N <= 2,500), ông ta muốn cắt thanh gỗ này tại 3 điểm để chia thành 4 miếng nhỏ hơn, mỗi miếng có độ dài là 1 số nguyên.

4 miếng này dài ngắn thế nào cũng được miễn là có thể giúp nông dân John đóng được 1 cái hàng rào hình tứ giác là được. Hỏi có bao nhiêu cách khác nhau cắt thanh gỗ ban đầu để tạo thành được hàng rào ?
CHÚ Ý

* Hai cách cắt gọi là khác nhau nếu một cách có 1 nhát cắt tại 1 điểm mà cách kia không có.
* Đảm bảo rằng hàng rào này xây dựng có diện tích lớn hơn 0.
* Chú ý đáp án luôn nằm trong phạm vi 1 số nguyên 32 bit có dấu.

Dữ liệu

* Dòng 1: 1 số nguyên duy nhất: N

Kết quả

* Dòng 1: Một số nguyên duy nhất là số cách mà nông dân John có thể cắt thanh gỗ thành 4 miếng nhỏ hơn mà có thể tạo được 1 tứ giác.

Ví dụ

Dữ liệu
6

Kết quả
6

Tiêu đề: Re: Đề HSG tin học 9 Mon 26 Jul 2010, 22:19

Giải bài 3:

Code:: Var N,N1,N2,i:integer;
Kq:longint;

Function Xuli(A,B:integer):longint;
Var A1,A2:integer;
Dem,Dem1:longint;
Begin
Dem:=0;
Dem1:=0;
For A1:=1 to A-1 do
Begin
A2:=A-A1;
If (Abs(A1-A2)<B) then Inc(Dem);
End;
For A1:=1 to B-1 do
Begin
A2:=B-A1;
If Abs(A1-A2)<A then Inc(Dem1);
End;
Xuli:=Dem*Dem1;
End;

BEGIN
Readln(N);
Kq:=0;
For i:=1 to N-1 do
Begin
N1:=i;
N2:=N-N1;
Kq:=Kq+Xuli(N1,N2);
End;
Write(Kq);

END.