Problemi 026

Kërkesa

Për një varg shkronjash \(S\) shënojmë me \(C\) bashkësinë e shkronjave që shfaqen në të të paktën 1 herë. Një përkëmbim (radhitje) të elementeve të bashkësisë \(C\) e shënojmë \((c_1, c_2, c_3...)\). Le të jetë \(f(c)\) numri i herëve që përsëritet shkronja \(c\) në vargun \(S\).

Nëse ndonjë përkëmbim i elementeve të bashkësisë \(C\) kënaq kushtin \(f(c_i) = f(c_{i-1}) + f(c_{i-2})\) për çdo \(i \geq 3\) vargu \(S\) quhet varg dinamik.

Bëni një program që gjen nëse një varg i dhënë është dinamik.

Vini re që nëse numri i shkronjave të veçanta që shfaqen në varg është më pak se 3, p.sh. nëse \(|C| < 3\), atere vargu është gjithmonë dinamik.

Referenca: https://www.codechef.com/problems/CLFIBD

Shembull

$ cat input.txt
3
aaaabccc
aabbcc
ppppmmnnoooopp

$ python3 prog.py < input.txt
Dynamic
Not
Dynamic

Detyra

Një drejtkëndësh me përmasa A dhe B duam ta ndajmë në copa katrore (jo detyrimisht të barabarta). Sa është numri më i vogël i katrorëve në të cilët mund të ndahet ky drejtkëndësh?

Shembull

$ cat input.txt
2
10 15
4 7

$ python3 prog.py < input.txt
3
5