Tin học PASCAL

[nhsit1062@gmail.com]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

BT: THẮP SÁNG THÀNH PHỐ THÔNG MINH
Trung tâm quản lí giao thông vận tải Thành phố thông minh đang chuẩn bị cho một dự án “Thắp sáng thành phố thông minh”. Sau khi khảo sát và tính toán chính xác sô bóng đèn để lắp đặt cho thành phố. Họ đã xác định được K bóng đèn để có thể thực hiện được dự án này. Có N công ty sản xuất bóng đèn có thể được chọn để thực hiện dự án này. Và được biết rằng các công ty này chỉ bán bóng đèn theo bộ và số lượng mỗi bộ tùy thuộc vào các công ty. Do thiếu kinh phí và để có thể thực hiện được dự án nên trung tâm này chỉ có thể mua được chính xác số bóng đèn yêu cầu. hỏi trung tâm quản lí có thể thực hiện được dự án hay không?
Dữ liệu vào:
Dòng đầu tiên là sô nguyên T (1<=T<=10) biểu thị số trường hợp thử nghiệm
T bộ dữ liệu tiếp theo mỗi bộ chứa 3 dòng:
Dòng đầu tiên của bộ là số nguyên N (1<=N<=1000) là sô công ty sản xuất bóng đèn có thể hợp tác và K (0<=K<=10000) biểu thị số bóng đèn mà công ty đang cần để lắp cho thành phố
Dòng thứ 2 của bộ dữ liệu gồm N phần tử mỗi phần tử cách nhau một khoảng trắng biểu thị số lượng bóng đèn mà công ty thứ I bán theo bộ (1<=ai<=109)
Dữ liệu ra:
Gồm T dòng mỗi dòng ghi “YES” (không có nháy kép) biểu thị cho công ty có thể thực hiện được dự án và ghi “NO” trong trường hợp ngược lại.
Ví dụ:

Input	Output
3 5 16 1 5 5 1 2 5 3 1 2 1 3 3 5 2 4 4 3 4 1	NO YES NO

[TBODY] [/TBODY]

Giải thích:
Test case 1: không có cách nào mua đủ số bóng đèn yêu cầu
Test case 2: với số bóng đèn yêu cầu là 3, ta có thể mua bộ 1 và bộ 2 (2+1=3) hoặc bộ 2 và bộ 3 (2+1=3) hoặc chỉ bộ 4 (3) hoặc bộ 5 (3).
Test case 3: Không có cách nào mua đủ số bóng đèn.

 

[nguyen tran thanh nha]

var n,k,t ,i,j :longint; f,g:text; kt:boolean;
    a:array[1..100000] of longint;
procedure quyhoachdong;
var t,d:array[0..100000] of longint; i,j:longint;
begin
     t[0]:=1; d[0]:=1;
     for i:=1 to n do
     begin
           for j:=0 to k- a[i] do
              if t[j]<>0 then d[j+a[i]]:=1 ;
            t:=d;
     end;
     if t[k]<>0 then kt:= true else kt:= false;
     for i:=0 to k do begin t[i]:=0;d[i]:=0;end;
end;
begin
     assign(f,'input.inp');reset(f);
     assign(g,'output.out');rewrite(g);
     readln(f,t);
     for i:= 1 to t do
     begin
           readln(f,n,k);
           for j:= 1 to n do read(f,a[j]);readln(f);
           quyhoachdong;
           if kt then writeln(g,'YES')
           else writeln(g,'NO');
      end;
      close(f);
      close(g);
end.