Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Dãy con dài nhất có tổng chia hết cho K

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Dãy con dài nhất có tổng chia hết cho K   Tue 27 Jul 2010, 13:18

Cho một dãy gồm n ( n <= 1000) số nguyên dương A1, A2, ..., An và số nguyên dương k (k <= 50). Hãy tìm dãy con gồm nhiều phần tử nhất của dãy đã cho sao cho tổng các phần tử của dãy con này chia hết cho k.
Input

Dòng đầu tiên chứa hai số n, k ghi cách nhau bởi ít nhất 1 dấu trống.

Các dòng tiếp theo chứa các số A1, A2, ..., An được ghi theo đúng thứ tự cách nhau ít nhất một dấu trống hoặc xuống dòng
Output

Gồm 1 dòng duy nhất ghi số lượng phần tử của dãy con dài nhất thoả mãn
Example

Input:
10 3
2 3 5 7
9 6 12 7
11 15

Output:
9
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Wed 28 Jul 2010, 08:54

Nhập theo modun k.

f[i,j] là số phần tử lớn nhất của dãy a[1]..a[j] khi chia cho k dư i. f[0,n] là kết quả của bài toán.

f[i,j]=max(f[i-a[j],j-1],f[i,j-1]);

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Thu 29 Jul 2010, 22:19

mình làm bài này rồi và đã thử nhiều test thấy đúng nhưng nộp lên trên VNOI lại sai.
Code:

Const          MaxN=1000;
                MaxK=50;
Var
                A:Array[1..MaxN] of integer;
                F:Array[0..MaxN+1,0..MaxK-1] of integer;
                N,K:integer;

Procedure      Input;
Var            i:integer;
Begin
                Readln(N,K);
                For i:=1 to N do Read(A[i]);
End;

Function        Sodu(X,Y:integer):integer;
Var            Du:integer;
Begin
                Du:=(X-Y) mod K;
                If Du>=0 then Sodu:=Du
                Else          Sodu:=Du+K;
End;

Procedure      Xuli;
Var            i,j:integer;
Begin
                F[0,0]:=0;
                For j:=1 to K-1 do F[0,j]:=MaxK;
                For i:=1 to N do
                For j:=0 to K-1 do
                Begin
                If F[i-1,j]>F[i-1,Sodu(A[i],j)]+1 then F[i,j]:=F[i-1,Sodu(A[i],j)]+1
                Else                                    F[i,j]:=F[i-1,j];
                End;
End;

Procedure      Output;
Var            i,S:integer;
Begin
                S:=0;
                For i:=1 to N do S:=S+A[i];
                Writeln(N-F[N,S mod K]);
End;

BEGIN
                Input;
                Xuli;
                Output;
END.

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Fri 30 Jul 2010, 10:27

^^ đâu phải lúc nào người ra đề cũng cho test đúng. Với lại có thể cần thêm yêu càu gì đó mà anh ko để ý ^^

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Fri 30 Jul 2010, 14:41

Em có cách gì khác không?

_________________
P.T.H.T
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Fri 30 Jul 2010, 17:20

Em đâu có học chuyên tin. Với lại em trước giờ tự học là chủ yếu. Ngoài mấy cái liên quan đến toán học đại số hoặc hình học bình thường, thì mấy pp đặc biệt em sao biết.

_________________
Đời là cây đinh, mình là cây búa.
Về Đầu Trang Go down
danlamson_pro
Gà mờ


Tổng số bài gửi : 1
Join date : 04/12/2010

Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Sat 11 Dec 2010, 14:49


Const MaxN=1000;
MaxK=50;
Var
A:Array[1..MaxN] of integer;
F:Array[0..MaxN+1,0..MaxK-1] of integer;
N,K:integer;

Procedure Input;
Var i:integer;
Begin
Readln(N,K);
For i:=1 to N do Read(A[i]);
End;

Function Sodu(X,Y:integer):integer;
Var Du:integer;
Begin
Du:=(X-Y) mod K;
If Du>=0 then Sodu:=Du
Else Sodu:=Du+K;
End;

Procedure Xuli;
Var i,j:integer;
Begin
F[0,0]:=0;
For j:=1 to K-1 do F[0,j]:=MaxK;
For i:=1 to N do
For j:=0 to K-1 do
Begin
If F[i-1,j]>F[i-1,Sodu(A[i],j)]+1 then F[i,j]:=F[i-1,Sodu(A[i],j)]+1
Else F[i,j]:=F[i-1,j];
End;
End;

Procedure Output;
Var i,S:integer;
Begin
S:=0;
For i:=1 to N do S:=S+A[i];
Writeln(N-F[N,S mod K]);
End;

BEGIN
Input;
Xuli;
Output;
END.
Về Đầu Trang Go down
Sponsored content




Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Today at 18:51

Về Đầu Trang Go down
 
Dãy con dài nhất có tổng chia hết cho K
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» NI CÔ DIỆU THIỆN - Ái Hoa
» TRANG THƠ CHẾ LAN VIÊN
» Một tách trà cho nỗi buồn
» Em muốn anh phải hối hận ...
» Loi chia tay som muon !

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến