BÀI TẬP 64: MẬT KHẨU (TÍCH BA SỐ)

Để đảm bảo an ninh dữ liệu tại sân bay, nhà chức trách đã xác lập mật khẩu từ bảng số liệu có n hàng (n ≤ 10) h₁, h₂, …, h_n tương ứng với hàng thứ 1, 2, …, n tính từ trên xuống, mỗi hàng h_i (i=1,…,n) có ít nhất từ 3 đến không quá 100 số tự nhiên được phân biệt bởi dấu cách. Mật khẩu được xác định bằng cách viết liên tiếp n số x₁, x₂, …, x_n theo thứ tự từ trái sang phải, với x_i (i=1,2 ,…n) là số cách chọn bao số tuỳ ý trên hàng h_i, sao cho tích ba số đó chia hết cho tổng của chúng.

Yêu cầu: Lập trình giúp nhà chức trách sân bay xác lập mật khẩu.

- Dữ liệu vào: Đọc từ file văn bản MATKHAU.INP chứa n hàng như phần mô tả trong bảng số liệu đã nêu trên.

- Dữ liệu ra: Kết quả ghi ra file văn bản MATKHAU.OUT là số mật khẩu tìm được.

Ví dụ:

MATKHAU.INP	MATKHAU.OUT
0 1 3 5 3 4 1 3 1 3 2 3 3 1 2 1 1 3 0 1 3 1	271303

 

Ý tưởng:

+ Đọc hết 1 dòng vào mảng A (N phần tử)

+ Dùng 3 vòng For (mỗi dòng nhiều nhất 10^2 vậy 3 vòng For 10^6 và nhiều nhất là 10 vòng, vậy O(10^1 * 10^6 = 10^7)).

+ Kiểm tra tích 3 số có chia hết cho tổng hay không?

 Nếu (a[i]*a[j]*a[k]) mod (a[i]+a[j]+a[k]) = 0 thì d:=d+1;

+ In ra D.

CODE THAM KHẢO:

program Mat_Khau;

var A:array[1..101] of integer;

    fi,fo:text;

    M:byte;

procedure XuLy(N:byte);

var i,j,k: byte; d: longint;

begin

        d:=0;

        for i:=1 to n-1 do

           for j:=i+1 to n-1 do

              for k:=j+1 to n do

              if (a[i]*a[j]*a[k]) mod (a[i]+a[j]+a[k]) = 0 then inc(d);

        write(fo,d);

end;

begin

        assign(fi,'MATKHAU.INP'); reset(fi);

        assign(fo,'MATKHAU.OUT'); rewrite(fo);

        while not eof(fi) do

        begin

                M:=0;

                while not eoln(fi) do

                begin

                        M:=M+1;

                        read(fi,A[M]);

                end;

        readln(fi);

        XuLy(M);

        end;

        close(fi);  close(fo);

end.