Problemi 021

Kërkesa

Në një shumëkëndësh që ka N brinjë, këndet formojnë një progresion aritmetik, ku këndi më i vogël e ka madhësinë A gradë. Gjeni madhësinë e këndit K (\(1 \leq K \leq N\)) dhe shpreheni atë si një raport dy numrash natyrorë X dhe Y që janë reciprokisht të thjeshtë (pjesëtuesi më i madh i përbashkët është 1).

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

Shembull

$ cat input.txt
1
3 30 2

$ python3 prog.py < input.txt
60 1

Tre numrat që jepen në input janë N, A dhe K. Në rastin tonë kemi një trekëndësh, ku këndi më i vogël është 30 gradë, dhe na kërkohet vlera e këndit të dytë.

Zgjidhja 1

def pmp(a, b):
    '''
    Gjej pjesetuesin me te madh te perbashket te dy numrave te dhene.
    '''
    while a > 0:
        a, b = b % a, a
    return b

T = int(input())
for t in range(T):
    N, A, K = map(int, input().split())
    X = A*N*(N - 1) + 2*(K - 1)*(180*(N - 2) - N*A)
    Y = N*(N - 1)
    p = pmp(X, Y)
    print(X // p, Y // p)

Sqarime

Vërtetohet kollaj se shuma e këndeve të një N-këndëshi është \(180*(N - 2)\). Meqenëse këndet formojnë progresion aritmetik, këtë shumë mund ta shkruajmë edhe: \(A + (A + x) + (A + 2*x) + ... + (A + (N - 1)*x) = N*A + \frac{x*N*(N - 1)}{2}\) . Duke barazuar këto dy vlera gjejmë: \(x = \frac{2*(180*(N - 2) - N*A)}{N*(N - 1)}\) . Atere vlera e këndit të K-të është: \(A + (K - 1)*x = \frac{A*N*(N - 1) + 2*(K - 1)[180*(N - 2) - N*A]}{N*(N - 1)}\) Kështu që përgjigja është \(X = A*N*(N - 1) + 2*(K - 1)[180*(N - 2) - N*A]\) dhe \(Y = N*(N - 1)\).

Vetëm se këto vlera duhet ti thjeshtojmë duke i pjesëtuar me pjesëtuesin më të madh të përbashkët, të cilin e gjejmë me anë të funksionit pmp(). Ky funksion bazohet në faktin që pmp(a, b) është i njëjtë me pmp(b - a, a), dhe si rrjedhim është i njëjtë edhe me pmp(b % a, a).

Zgjidhja 2

import math

T = int(input())
for t in range(T):
    N, A, K = map(int, input().split())
    X = A*N*(N - 1) + 2*(K - 1)*(180*(N - 2) - N*A)
    Y = N*(N - 1)
    p = math.gcd(X, Y)
    print(X // p, Y // p)

Sqarime

Në këtë rast kemi përdorur funksionin e gatshëm math.gcd() (greatest common denominator), për të gjetur pjesëtuesin më të madh të përbashkët.

Detyra

Çufo ka një recetë me përbërësit që duhen për një gatim. Por sipas kësaj recete do të gatuhej shumë më tepër ushqim nga ç’i duhet Çufos. Kështu që ai do që ti pakësojë përbërësit, por duke ruajtur përpjesëtimin (raportin) e tyre, dhe duke qenë numra të plotë.

Reference: https://www.codechef.com/problems/RECIPE

Shembull

$ cat input.txt
3
2 4 4
3 2 3 4
4 3 15 9 6

$ python3 prog.py < input.txt
1 1
2 3 4
1 5 3 2

Për çdo rast testimi, numri i parë tregon numrin e përbërësve, dhe më pas vijnë sasitë përkatëse të përbërësve.