Category Archives: SOLUTIONS
ACMNB SPOJ – PREVNOI 2013-2014
ĐỀ BÀI: ACMNB
SOLUTION:
Thuật toán có thể suy ra từ cách làm thực tế. Nếu Tí làm tất cả 2n bài sẽ mất tổng thời gian là
Tuy nhiên Tí phải nhường lại n bài cho Tèo. Mỗi khi Tí nhường bài i cho Tèo, thời gian S sẽ giảm đi một lượng ci = ai – bi. Ta cần chọn n bài để Tí nhường cho Tèo sao cho thời gian S giảm đi nhiều nhất, tức là phải chọn n chỉ số i có c lớn nhất.
CODE: ACMNB
FIBVAL SPOJ – VOI 2012 Bản vanxơ Fibonacci
ĐỀ BÀI: FIBVAL
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.
Ràng buộc: 50% số tests ứng với 50% số điểm có ui < vi ≤ 100.
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
HƯỚNG DẪN GIẢI:
Để giải được bài này, ta cần áp dụng 1 tính chất đặc biệt của dãy Fibonacci, đó là chu kỳ Pisano
Dãy Fibonacci có dạng:
f(0)=0 f(1)=1 f(i)=f(i-1)+f(i-2)
Đối với 1 số nguyên n bất kì thì dãy g(i)=f(i) mod n có tính chu kì.
Ví dụ: Với n=3 ta có:
f | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 15 | 28 | 43 | … |
g | 0 | 1 | 1 | 2 | 0 | 2 | 2 | 1 | 0 | 1 | 1 | … |
Ở bài này, ta có chu kì gồm 7 nốt nhạc vì vậy ta xét tính chu kì trên dãy g(i)=f(i) mod 7.
Chu kì Peisano của 7 trong bài này gồm 16 số:
1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1
Như vậy, độ dài đoạn nhạc dài nhất có tính chu kì chỉ có thể là 2 hoặc có dạng 16*k.
CODE:
CONST tfi = ''; tfo = ''; VAR fi,fo : text; Function pro(l,r: longint): longint; Var len,res: longint; Begin len:=r-l+1; l:=l mod 16; r:=r mod 16; If l=0 then l:=16; If r=0 then r:=16; res:=len div 16; If len>=32 then exit(res*16) else If len>=9 then exit(2) else If ((l=9)) or ((l>9) and (r0 do begin read(fi,l,r); writeln(fo,pro(l,r)); dec(test); end; End; BEGIN assign(fi,tfi); reset(fi); assign(fo,tfo); rewrite(fo); process; close(fi); close(fo); END.