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ố 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.

Nếu bạn cần code cải tiến vui lòng đề nghị, mình sẽ viết.

6 thoughts on “PTIT135G spoj PTIT – Blackjack

    • Chào bạn, hiện tại vì lý do mình còn bận nhiều việc nên chưa thể thực hiện yêu cầu của bạn được. Mong bạn thông cảm. Và với bài như trên thì độ phức tạp khá tuy là O(n^3) nhưng N chỉ 100 nên bạn không cần lo lắng mấy. chỉ khi nào N quá lớn cỡ 10^3->10^4 thì bạn mới cải tiến.
      Mình gợi ý bạn cách làm N^2 log2 N như sau:
      – Đầu tiên bạn sắp xếp mảng nhập vào
      – Viết function chặt nhị phân tìm số <=M và gần M nhất: tknp(l,r,x:longint):longint; với l, r là giới hạn đoạn đầu cuối cần tìm, x là giá trị mốc mà số tìm dc phải <=X và gần X nhất. sau đó trả về số đó - duyệt 2 dòng for for i:=1 to n-2 do for j:=i+1 to n-1 do IF A[i]+a[j]0 thì
      res:=max(res,a[i]+a[j]+k);
      end;

    • Thân chào bạn,
      Hiện tại mình do còn bận nhiều việc nên chưa thể hỗ trợ bạn viết code cải tiến, tuy nhiên bạn có thể tham khảo phần bình luận mình đã gửi ở trên, hi vọng sẽ giúp ích được cho bạn.
      🙂

  1. Bài này áp dụng tìm kiếm nhị phân ngay thì N^2logN. Sử dụng two-pointer giảm được đến N^2. Nếu sinh tổng 2 số áp dụng tknp có thể giảm tối đa NlogN tùy nhiên phải kiểm tra trùng nên phức tạp hơn chút. N^2 đủ AC bài này rồi.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *