02/10/2018, 14:11
PTIT135G spoj PTIT – Blackjack
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT135G/ 1. Đề bài PTIT135G spoj PTIT Cho một tập N quân bài, mỗi quân chứa một số nguyên dương. Bạn cần phải chọn ra ba quân bài sao cho tổng các số trên 3 quân bài gần với số M nhất và không vượt quá M. Input Dòng 1 chứa 2 số ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT135G/
1. Đề bài PTIT135G spoj PTIT
Cho một tập N quân bài, mỗi quân chứa một số nguyên dương. Bạn cần phải chọn ra ba quân bài sao cho tổng các số trên 3 quân bài gần với số M nhất và không vượt quá M.
Input
Dòng 1 chứa 2 số N và M. (N <= 100, M <= 500 000)
Dòng 2 chứa N số nguyên dương, mỗi số không quá 100 000.
Output
In ra tổng 3 quân gần M nhất và không vượt quá M.
Input luôn đảm bảo tồn tại đáp số.
Example
Input:
5 21
5 6 7 8 9
Output:
21
2. Code tham khảo PTIT135G spoj PTIT
Bài này khá đơn giản, làm bằng cách bình thường nhất là o(n^3), có thể cải tiến bằng cách dùng chặt nhị phân, độ phức tạp n^2 log2 n
Code tham khảo N^3
const fi=';
nmax=100;
type data=longint;
var
f:text;
i,m,n:data;
A:array[1..nmax] of data;
procedure docfile;
var i,j:data;
begin
assign(f,fi); reset(f);
readln(f,n,m);
for i:=1 to n do
read(f,a[i]);
close(f);
end;
procedure xuli;
var i,j,k,res:data;
begin
res:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
if (a[i]+a[j]+a[k]<=M) and (a[i]+a[j]+a[k]>res) then
res:=a[i]+a[j]+a[k];
writeln(res);
end;
begin
docfile;
xuli;
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 | const fi='; nmax=100; type data=longint; var f:text; i,m,n:data; A:array[1..nmax] of data; procedure docfile; var i,j:data; begin assign(f,fi); reset(f); readln(f,n,m); for i:=1 to n do read(f,a[i]); close(f); end; procedure xuli; var i,j,k,res:data; begin res:=0; for i:=1 to n-2 do for j:=i+1 to n-1 do for k:=j+1 to n do if (a[i]+a[j]+a[k]<=M) and (a[i]+a[j]+a[k]>res) then res:=a[i]+a[j]+a[k]; writeln(res); end; begin docfile; xuli; end. |
Nếu bạn cần code cải tiến vui lòng đề nghị, mình sẽ viết.
