Đề tài: Bản Vanxơ Fibonaci

Bản vanxơ Fibonacci là một bản nhạc mà giai điệu của nó bắt nguồn từ một trong những dãy số nổi tiếng nhất trong Lý thuyết số - dãy số Fibonacci. Hai số đầu tiên của dãy là số 1 và số 2, các số tiếp theo được xác định bằng tổng của 2 số liên tiếp ngay trước nó trong dãy.

Bản vanxơ Fibonacci thu được bằng việc chuyển dãy số Fibonacci thành dãy các nốt nhạc theo qui tắc chuyển một số nguyên dương thành nốt nhạc sau đây:


Số 1 tương ứng với nốt Đô (C).
Số 2 tương ứng với nốt Rê (D).
Số 3 tương ứng với nốt Mi (E).
Số 4 tương ứng với nốt Fa (F).
Số 5 tương ứng với nốt Sol (G).
Số 6 tương ứng với nốt La (A).
Số 7 tương ứng với nốt Si (B).
Số 8 tương ứng với nốt Đô (C).
Số 9 tương ứng với nốt Rê (D).

và cứ tiếp tục như vậy. Ví dụ, dãy gồm 6 số Fibonacci đầu tiên 1, 2, 3, 5, 8 và 13 tương ứng với dãy các nốt nhạc C, D, E, G, C và A.

Để xây dựng nhịp điệu vanxơ người ta đi tìm các đoạn nhạc có tính chu kỳ trong bản vanxơ Fibonacci. Đoạn nhạc được gọi là có tính chu kỳ nếu như có thể chia nó ra thành k ≥ 2 đoạn giống hệt nhau. Ví dụ, đoạn nhạc GCAGCA là đoạn có tính chu kỳ, vì nó gồm 2 đoạn giống nhau GCA.

Yêu cầu: Cho trước hai số nguyên dương u, v (u < v), hãy xác định độ dài đoạn nhạc dài nhất có tính chu kỳ của bản nhạc gồm dãy các nốt nhạc của bản vanxơ Fibonacci bắt đầu từ vị trí u kết thúc ở vị trí v.

Input
Dòng thứ nhất chứa số nguyên dương k (k ≤ 100) là số lượng test.
Dòng thứ i trong số k dòng tiếp theo chứa 2 số nguyên dương ui, vi được ghi cách nhau bởi dấu cách (ui < vi ≤ 109) là vị trí bắt đầu và kết thúc của 1 bản nhạc.
Output
Ghi ra k dòng, dòng thứ i chứa 1 số nguyên là độ dài đoạn nhạc tìm được tương ứng với test thứ i. Nếu không tìm được đoạn nào có tính chu kỳ thì ghi ra số -1.

Example
Input:
2
1 3
4 10

Output:
-1
2
làm thế nào để mình xác định đc đoạn nhạc GCAGCA là đoạn có tính chu kỳ

Example
Input:
2
1 3
4 10

Output:
-1
2

Ở test 2:
Dãy số là
1 2 3 5 8 13 21 34 55 89

5 8 13 21 34 55 89
G C CE DC EF GG CD.
Test có vấn đè. Còn kiểm tra tính chu kỳ mình nghĩ là duyệt

mikelhpdatke

ở test 2:
Dãy số là
1 2 3 5 8 13 21 34 55 89

5 8 13 21 34 55 89
g c ce dc ef gg cd.
Test có vấn đè. Còn kiểm tra tính chu kỳ mình nghĩ là duyệt

số 1 tương ứng với nốt đô (c).
Số 2 tương ứng với nốt rê (d).
Số 3 tương ứng với nốt mi (e).
Số 4 tương ứng với nốt fa (f).
Số 5 tương ứng với nốt sol (g).
Số 6 tương ứng với nốt la (a).
Số 7 tương ứng với nốt si (b).
Số 8 tương ứng với nốt đô (c).
Số 9 tương ứng với nốt rê (d).

và cứ tiếp tục như vậy.

vậy thì bản nhạc của test 2 sẽ là: GCABAAG

số 1 tương ứng với nốt đô (c).
Số 2 tương ứng với nốt rê (d).
Số 3 tương ứng với nốt mi (e).
Số 4 tương ứng với nốt fa (f).
Số 5 tương ứng với nốt sol (g).
Số 6 tương ứng với nốt la (a).
Số 7 tương ứng với nốt si (b).
Số 8 tương ứng với nốt đô (c).
Số 9 tương ứng với nốt rê (d).

và cứ tiếp tục như vậy.
5 8 13 21 34 55 89
g c a b a a g

Mình ko hiểu. Số 1 ở đây là số. Ko phải chữ số. Mà bạn làm cái này chả hiểu j` cả

5 8 13 21 34 55 89
g c a b a a g

nghĩa là chu kỳ đấy bạn, mỗi số Fibo đều tương ứng với 1 trong 7 nốt nhạc. số 13 thì là A (13 mod 7=6), 21 thì là B (21 mod 7=0).

. Thế sao đọc đầu bài ko thấy chỗ Mod 7

mikelhpdatke

. Thế sao đọc đầu bài ko thấy chỗ Mod 7

Mod 7 là cái mình suy ra từ đề bài thôi

Dãy vanxơ này có chu kỳ 16 đấy

Thuật thế này:
Hàm test(s) để kiểm tra đoạn này có chu trình ko bằng cách so sánh s(1..length(s) div 2) với s(length(s) div 2 + 1.. length(s))
Chương trình xử lí

Code:

for i:=1 to length(vf) div 2 do
         for j:=length(vf) downto  length(vf) div 2+1 do 
              if  Test(s(từ i đến j)) then begin Xuất kq, break; end;

Englandhuynh

Thuật thế này:
Hàm test(s) để kiểm tra đoạn này có chu trình ko bằng cách so sánh s(1..length(s) div 2) với s(length(s) div 2 + 1.. length(s))
Chương trình xử lí

Code:

for i:=1 to length(vf) div 2 do
         for j:=length(vf) downto  length(vf) div 2+1 do 
              if  Test(s(từ i đến j)) then begin Xuất kq, break; end;

Thuật toán này hình như không đúng lắm, vd nếu vs bản nhạc có đoạn nhạc có tính chu kỳ ở phần sau (tức là i > length(vf) div 2) thì sao?

Với cả duyệt trâu thế này thì ko AC nổi đâu em:
u[i], v[i] <= 10^9
k <= 100
bài này thuật chuẩn của nó chỉ có O(k)

E cũng nghĩ vấn đề như anh HGM, thế a nghĩ ra cách nào hay ko

pha96

sao dãy này có chu kỳ 16 dậy Minh

Bạn viết vài chục số hạng đầu tiên của dãy ra thì biết thôi

HGMinh95

Bạn viết vài chục số hạng đầu tiên của dãy ra thì biết thôi

uh, mới làm thử cho cỡ khoảng 4 chục số là nó tràn rồi, khiếp.

Đây là 50 phần tử đầu tiên:
CDEGCABAAGFDACBCCDEGCABAAGFDACBCCDEGCABAAGFDACBCCD
Để ý rằng đoạn in đậm được lặp lại trong dãy

Ơ mọi người cho mình thuật toán bài này với, mới bàn có mỗi test thui hà.

pha96

Ơ mọi người cho mình thuật toán bài này với, mới bàn có mỗi test thui hà.

Nó lặp lại với chu kỳ 16, có thể xét trong khoảng từ u -> v có bao nhiêu đoạn lặp lại như vậy (gọi số đoạn là n). Nếu n >= 2 thì in ra 16*n, ngược lại nếu đoạn [u, v] có chứa 2 ký tự AA thì in ra 2, còn lại in ra 0