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: 8

Thyesa 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