Problemi 023

Kërkesa

Çufoja 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.

Zgjidhja 1

import math

for _ in range(int(input())):
    perberesit = list(map(int, input().split()))

    # hiq numrin e pare nga lista
    perberesit = perberesit[1:]

    # gjej pjesetuesim me te madh te perbashket
    pmp = perberesit[0]
    for p in perberesit:
        pmp = math.gcd(pmp, p)

    # shfaq pergjigjen
    for p in perberesit[:-1]:
        print(p // pmp, end=' ')
    print(perberesit[-1] // pmp)

Sqarime

Për të zvogëluar vlerat e përbërësve duke ruajtur përpjesëtimet dhe duke qenë numra të plotë, duhet të gjejmë pjesëtuesin më të madh të përbashkët të të gjithë numrave, dhe ti pjesëtojmë me të. PMP të të gjithë numrave mund ta gjejmë duke përdorur këtë veti: \(pmp(a_1, a_2, a_3) = pmp(pmp(a_1, a_2), a_3)\)

Kemi përdorur gjithashtu edhe disa mjete të gjuhës Python që përdoren për listat. Bëni këto prova:

$ python3
>>> p = [0, 1, 2, 3, 4]
>>> p
[0, 1, 2, 3, 4]
>>> p[1:4]
[1, 2, 3]
>>> p[1:]
[1, 2, 3, 4]
>>> p[:-1]
[0, 1, 2, 3]
>>> p[-1]
4
>>> 

Zgjidhja 2

from math import gcd
from functools import reduce

for _ in range(int(input())):
    perberesit = list(map(int, input().split()))

    # hiq numrin e pare nga lista
    perberesit = perberesit[1:]

    # gjej pjesetuesim me te madh te perbashket
    pmp = reduce(gcd, perberesit)

    # shfaq pergjigjen
    for p in perberesit[:-1]:
        print(p // pmp, end=' ')
    print(perberesit[-1] // pmp)

Funksioni reduce() është i ngjashëm me funksionin map() në atë që zbaton një funksion të dhënë te vlerat e një liste të dhënë, por ndërsa funksioni map() kthen një listë, funksioni reduce() kthen një vlerë të vetme. Shiko edhe: http://book.pythontips.com/en/latest/map_filter.html#reduce

Detyra

Një fermer do të shesë tokën e tij, e cila është në formë drejtkëndëshi me përmasa M dhe N. Meqenëse copat e tokës në formë katrore kanë çmim më të lartë, ai do që ta ndajë tokën e tij në copa katrore të barabarta. Sa është numri më i vogël i katrorëve të barabartë që mund të krijohen në tokën e tij?

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

Shembull

$ cat input.txt
2
10 15
4 6

$ python3 prog.py < input.txt
6
6