Diễn đàn tin học Nguyễn Văn Linh
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

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

The second house for every one
 
Trang ChínhLatest imagesTìm kiếmĐăng kýĐăng Nhập

 

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

Go down 
3 posters
Tác giảThông điệp
Hovanthong
Admin
Admin
Hovanthong


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

Dãy con dài nhất có tổng chia hết cho K Empty
Bài gửiTiêu đề: Dãy con dài nhất có tổng chia hết cho K   Dãy con dài nhất có tổng chia hết cho K I_icon_minitimeTue 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
littlelee


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

Dãy con dài nhất có tổng chia hết cho K Empty
Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Dãy con dài nhất có tổng chia hết cho K I_icon_minitimeWed 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]);
Về Đầu Trang Go down
Hovanthong
Admin
Admin
Hovanthong


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

Dãy con dài nhất có tổng chia hết cho K Empty
Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Dãy con dài nhất có tổng chia hết cho K I_icon_minitimeThu 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.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin
littlelee


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

Dãy con dài nhất có tổng chia hết cho K Empty
Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Dãy con dài nhất có tổng chia hết cho K I_icon_minitimeFri 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 để ý ^^
Về Đầu Trang Go down
Hovanthong
Admin
Admin
Hovanthong


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

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

Em có cách gì khác không?
Về Đầu Trang Go down
http://thongtra.forum-viet.com
littlelee
Admin
Admin
littlelee


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

Dãy con dài nhất có tổng chia hết cho K Empty
Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Dãy con dài nhất có tổng chia hết cho K I_icon_minitimeFri 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.
Về Đầu Trang Go down
danlamson_pro
Gà mờ
danlamson_pro


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

Dãy con dài nhất có tổng chia hết cho K Empty
Bài gửiTiêu đề: Re: Dãy con dài nhất có tổng chia hết cho K   Dãy con dài nhất có tổng chia hết cho K I_icon_minitimeSat 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





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

Về Đầu Trang Go down
 
Dãy con dài nhất có tổng chia hết cho K
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Dãy chia hết hoàn toàn dài nhất
» Tổng các chữ số
» Xóa số để tạo thành số nhỏ nhất, lớn nhất.
» Chia nhóm từ dãy 1...n*n
» Chìa khóa

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