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 ...
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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | 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. |
