THEME spoj – Đoạn cao trào của bản nhạc

Nguồn đề bài: THEME

1. Đề bài THEME spoj

Trong một bản nhạc thường có những đoạn nhạc mà tác giả sử dụng nó nhiều lần ( ít nhất 2 lần ). Những đoạn đó gọi là “đoạn cao trào”. Do có thể sử dụng nhiều giọng khác nhau ( son, la, si…) nên nốt đầu tiên của các lần xuất hiện có thể khác nhau, nhưng chệnh lệnh độ cao giữa hai nốt liên tiếp thì chắc chắn giống.
VD: hai đoạn sau
1 2 5 4 10
và
4 5 8 7 13
được coi là một đoạn cao trào, vì chúng cùng sự chênh lệch độ cao : +1,+3,-1,+6
Cho một bản nhạc, yêu cầu tìm độ dài đoạn cao trào dài nhất.
+ Đoạn cao trào phải có từ 5 nốt nhạc trở lên.
+ Những lần xuất hiện của đoạn không được chồng lên nhau ( không có nốt nhạc chung ).

Input
Dòng 1 : n = số nốt nhạc <= 5000
Một số dòng sau là n nốt nhạc, mỗi nốt được quy ra số tự nhiên trong phạm vi 1..88.
Output
1 dòng chứa 1 số duy nhất là độ dài đoạn cao trào dài nhất. Nếu không tìm được đoạn nhạc nào, in ra 0.

Example
Input:
30
25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
82 78 74 70 66 67 64 60 65 80
Output:
5
(5 nốt cuối dòng 1 và 5 nốt đầu dòng hai cùng là một đoạn)

2. Code tham khảo THEME spoj

a. Code c++

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> a;

void Init()
{
    cin>>n;
    a.resize(n+2);
    for(int i=1;i<=n;i++) cin>>a[i];
}

void Solve()
{
    int res=0;
    for(int i=5;i<=n-5;i++)
    {
        int len=1;
        for(int j=n;j>i;j--)
            if(a[j]-a[j-1]==a[j-i]-a[j-i-1])
            {
                len++;
                if(len>res) res=len;
                if(len==i) break;
            }
            else
                len=1;
    }
    if (res < 5)
        cout << '0';
    else
        cout << res;
}

int main()
{
    Init();
    Solve();
}

b. Code pascal

const   fi='';
        nmax=5000;
type    data=longint;
var
        f:text;
        n:data;
        A,B:array[1..nmax] of data;
        C:array[0..nmax,0..nmax] of integer;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,n);
        for i:=1 to n do
                read(f,a[i]);
        for i:=1 to n-1 do
                for j:=i+1 to n do
                        c[i,j]:=1;
        for i:=2 to n do
                B[i]:=A[i]-a[i-1];
        close(f);
end;

function max(a,b:integer):integer;
begin
        if a>b then exit(a);
        exit(b);
end;

procedure QHD;
var     i,j:data;
        res:integer=1;
begin
        for i:=2 to n-1 do
                for j:=i+1 to n do
                        if b[i]=b[j] then
                                begin
                                        C[i,j]:=C[i-1,j-1]+1;
                                        if c[i,j]> j-i then
                                                c[i,j]:=j-i;
                                        res:=max(c[i,j],res);
                                end;
        if res<5 then
                writeln(0)
        else
                writeln(res);
end;

begin
        docfile;
        QHD;
end.