Problemi 151
Kërkesa
Viola nuk është shqiptare por ka edhe gjak shqiptar. Të paktën një nga stërgjyshërit e saj ka qenë puro shqiptar, por ajo nuk e di sa gjenerata më parë.
Ligjet e trashëgimisë gjenetike funksionojnë kështu: Nëse njëri nga prindërit është A/B shqiptar dhe tjetri është C/D shqiptar, atere fëmija do jetë (A/B + C/D) / 2 shqiptar. P.sh. nqs njëri nga prindërit nuk është fare shqiptar (0/1) kurse tjetri është gjysëm shqiptar (1/2), atere fëmija do jetë çerek shqiptar (1/4).
Viola pretendon se është P/Q shqiptare. Para sa gjeneratash ka pasur një stërgjysh puro shqiptar? Në nuk ka mundësi që të jetë P/Q shqiptare, atere duhet të thoni që kjo është e pamundur.
Referenca: https://code.google.com/codejam/contest/3004486/dashboard#s=p0&a=0
Shembull
$ cat input.txt
5
1/2
3/4
1/4
2/23
123/31488
$ python3 prog.py < input.txt
Case #1: 1
Case #2: 1
Case #3: 2
Case #4: impossible
Case #5: 8Thyesa e dhënë P/Q mund të mos jetë e thjeshtuar (siç është p.sh. rasti i fundit).
Në rastin e parë Viola mund ti ketë pasur prindërit 1/1 (puro shqiptar) dhe 0/1 (jo shqiptar).
Në rastin e dytë mund ti ketë pasur prindërit 1/1 (puro shqiptare) dhe 1/2.
Në rastin e tretë mund ti ketë pasur prindërit 0/1 dhe 1/2, dhe prindi 1/2 i ka pasur prindërit 0/1 dhe 1/1 (puro shqiptar).
Në rastin e katërt, sido që të ketë qenë kombinimi i prindërve, gjyshërve dhe stërgjyshërve, nuk ka mundësi që rezultati të dalë 2/23.
Zgjidhja 1
from itertools import combinations_with_replacement
from math import gcd
for t in range(int(input())):
P, Q = [int(i) for i in input().split('/')]
g = gcd(P, Q)
P = P // g
Q = Q // g
# kontrollo nëse Q është fuqi e dyshit
if Q & (Q - 1) != 0:
print('Case #{}: {}'.format(t+1, 'impossible'))
continue
generation = [(0, 1, None, None), (1, 1, None, None)]
found = False
while not found:
new_generation = []
for parent1, parent2 in combinations_with_replacement(generation, 2):
p = parent1[0] + parent2[0]
q = parent1[1] + parent2[1]
person = (p, q, parent1, parent2)
new_generation.append(person)
g = gcd(p, q)
p //= g
q //= g
if p == P and q == Q:
found = True
break
generation = new_generation
gen = 0
ancestors = [person]
found = False
while not found:
previous_ancestors = []
for p, q, parent1, parent2 in ancestors:
if p == q:
found = True
break
previous_ancestors.append(parent1)
previous_ancestors.append(parent2)
ancestors = previous_ancestors
if not found:
gen += 1
print('Case #{}: {}'.format(t+1, gen))Sqarime
Po të shikojmë rregullin e trashëgimisë, mund të vëmë kollaj se Q është gjithmonë një fuqi e dyshit. Nëse Q-ja e dhënë nuk është e tillë, atere raporti i dhënë është i pamundur që të gjenerohet me anë të rregullave të trashëgimisë.
Duke u nisur nga raportet 0/1 dhe 1/1 ne gjenerojmë të gjitha kombinimet e mundshme për çdo gjeneratë, dhe ndalojmë kur na del një raport i njëjtë me atë që na është dhënë.
Ndërkohë, për çdo person kemi ruajtur edhe prindërit e tij, kështu që pasi kemi gjetur personin me raportin e duhur, ndjekim pemën familjare të tij sipas gjeneratave, deri sa të na dalë një paraardhës që e ka raportin 1/1.
Edhe koha edhe kujtesa e kësaj zgjidhje janë \(O(2^Q)\). Eksponenciale! Kjo zgjidhje ngec te rasti i fundit.
Zgjidhja 2
from math import gcd
for t in range(int(input())):
P, Q = [int(i) for i in input().split('/')]
g = gcd(P, Q)
P = P // g
Q = Q // g
# kontrollo nëse Q është fuqi e dyshit
if Q & (Q - 1) != 0:
print('Case #{}: {}'.format(t+1, 'impossible'))
continue
gen = 0
while P < Q:
P = P * 2
gen += 1
print('Case #{}: {}'.format(t+1, gen))Sqarime
Koha e kësaj zgjidhje është \(O(ln(Q))\). Logaritmike! Kurse kujtesa e nevojshme është pothuajse zero (konstante)!
Uou! Ka zgjidhje e zgjidhje. Në krahasim me zgjidhjen e parë kjo është 1000 herë më e thjeshtë për tu shkruar dhe pafundësisht më efiçente. Por si arrihet në këtë zgjidhje dhe pse rezultati i saj është i saktë? Për më shumë sqarime shikoni këtë analizë: https://code.google.com/codejam/contest/3004486/dashboard#s=a&a=0
Siç ka thënë edhe Richard Feynman, një problem i vështirë mund të zgjidhet edhe me mjete të thjeshta, por kjo kërkon një sasi inteligjence të pafundme: https://youtu.be/xdIjYBtnvZU?t=200