PTIT123B spoj PTIT - Đếm số lần lặp

Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT123B/

1. Đề bài PTIT123B spoj

Cho trước n số nguyên không âm a₁, a₂, …, a_n. Mỗi lần lặp, bạn thay đổi dãy này thành một dãy mới theo cách: phần tử thứ k trong dãy mới bằng trị tuyệt đối của a_k – a_k+1. Phần tử cuối cùng sẽ là a_n – a₁. Quá trình lặp sẽ dừng lại khi được một dãy bằng nhau.

Ví dụ với n=4 và bắt đầu với dãy 0 2 5 11 ta sẽ có các lần lặp là:

2 3 6 11

1 3 5 9

2 2 4 8

0 2 4 6

2 2 2 6

0 0 4 4

0 4 0 4

4 4 4 4

Như vậy trong ví dụ này ta sẽ có 8 lần lặp. Hãy viết chương trình các định số lần lặp của một dãy ban đầu

Input

Gồm nhiều bộ test, mỗi bộ test gồm 2 dòng:

Dòng 1 ghi số n (2<=n<=20)
Dòng 2 ghi n số của dãy ban đầu

Input kết thúc khi n=0

Output

Với mỗi bộ test ghi trên một dòng là số lần lặp theo mẫu dưới đây. Nếu dãy không bằng nhau được sau 1000 lần lặp thì ghi ra dòng “not attained”

Example

Input:
4
0 2 5 11
5
0 2 5 11 3
4
300 8600 9000 4000
16
12 20 3 7 8 10 44 50 12 200 300 7 8 10 44 50
3
1 1 1
4
0 4 0 4
0

Output:
Case 1: 8 iterations
Case 2: not attained
Case 3: 3 iterations
Case 4: 50 iterations
Case 5: 0 iterations
Case 6: 1 iterations

2. Gợi ý PTIT123B spoj PTIT

– Duyệt trâu bình thường

3. Code tham khảo PTIT123B spoj PTIT

const   fi='';
        nmax=20;
type    data=longint;
var
        A:array[0..nmax+1] of data;
        n,test:data;
        f:text;

function dem0:data;
var     i,s:data;
begin
        s:=0;
        for i:=1 to n do
                if a[i]=0 then
                        inc(s);
        exit(s);
end;

procedure xuli;
var     i,j:data;
        dem,tmp,k:data;
begin
        dem:=0;
        for i:=1 to 1000 do
                begin
                        inc(dem);
                        tmp:=a[1];
                        for j:=1 to n-1 do
                                a[j]:=abs(a[j]-a[j+1]);
                        a[n]:=abs(a[n]-tmp);
                        k:=dem0;
                        if k=n then
                                begin
                                        writeln('Case ',test,': ',(dem-1),' iterations');
                                        exit;
                                end
                        else
                                if k=n-1 then
                                        begin
                                                writeln('Case ',test,': not attained');
                                                exit;
                                        end;
                end;
        writeln('Case ',test,': not attained');
end;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        test:=0;
        repeat
                read(f,n);
                inc(test);
                if n=0 then break;
                for i:=1 to n do
                        read(f,a[i]);
                xuli;
        until 1=2;
        close(f);
end;

begin
        docfile;
end.

PTIT123B spoj PTIT – Đếm số lần lặp