02/10/2018, 14:47
BCACM11G spoj PTIT – Dãy con tăng dần tự nhiên bậc K
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCACM11G/ 1. Đề bài BCACM11G spoj Cho dãy gồm N số phân biệt A N = { a 1 , a 2 , .., a N } và số tự nhiên K ( K<= N<= 100 ). Ta gọi một dãy con tăng dần bậc K của dãy số A N là một dãy các số gồm K phần tử ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCACM11G/
1. Đề bài BCACM11G spoj
Cho dãy gồm N số phân biệt AN = {a1, a2, .., aN } và số tự nhiên K (K<=N<=100). Ta gọi một dãy con tăng dần bậc K của dãy số AN là một dãy các số gồm K phần tử trong dãy đó thỏa mãn tính chất tăng dần. Bài toán được đặt ra là hãy tìm số cácdãy con tăng dần bậc K của dãy số AN.
Input
Dòng đầu tiên ghi số bộ test, không lớn hơn 100. Mỗi bộ test được xây dựng theo khuôn dạng sau:
- Dòng đầu tiên ghi lại hai số N và K tương ứng với số phần tử của dãy số và bậc của dãy con.
- Dòng kế tiếp ghi lại N số của dãy số AN, các số trong dãy không lớn hơn 100.
Output
Với mỗi bộ test, in ra màn hình số các dãy con tăng dần tự nhiên bậc K của dãy số AN.
Example
Input:
2
5 3
2 5 15 10 20
5 3
2 20 10 15 5
Output:
7
1
2. Gợi ý bài BCACM11G spoj PTIT – Dãy con tăng dần tự nhiên bậc K
– Quay lui chọn k số theo thứ tự, sau đó duyệt kiểm tra k số số có tạo dãy con tăng hay không
3. Code BCACM11G spoj PTIT – Dãy con tăng dần tự nhiên bậc K
const fi=';
nmax=140;
type data=longint;
var
f:text;
A,B,luu:array[0..nmax+1] of data;
n,test,k,sl,res:data;
function check:data;
var i,j:data;
begin
for i:=2 to sl do
if A[luu[i-1]]>a[luu[i]] then
exit(0);
exit(1);
end;
procedure try(i:data); //da chon so co vi tri i
var j:data;
begin
if sl=k then
begin
res:=res+check;
exit;
end;
for j:=i+1 to n do
begin
inc(sl);
luu[sl]:=j;
try(j);
dec(sl);
end;
end;
procedure xuli;
var i,j:data;
begin
sl:=0;
res:=0;
try(0);
writeln(res);
end;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,test);
for i:=1 to test do
begin
read(f,n,k);
for j:=1 to n do
read(f,a[j]);
xuli;
end;
close(f);
end;
begin
docfile;
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | const fi='; nmax=140; type data=longint; var f:text; A,B,luu:array[0..nmax+1] of data; n,test,k,sl,res:data; function check:data; var i,j:data; begin for i:=2 to sl do if A[luu[i-1]]>a[luu[i]] then exit(0); exit(1); end; procedure try(i:data); //da chon so co vi tri i var j:data; begin if sl=k then begin res:=res+check; exit; end; for j:=i+1 to n do begin inc(sl); luu[sl]:=j; try(j); dec(sl); end; end; procedure xuli; var i,j:data; begin sl:=0; res:=0; try(0); writeln(res); end; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,test); for i:=1 to test do begin read(f,n,k); for j:=1 to n do read(f,a[j]); xuli; end; close(f); end; begin docfile; end. |
