Problemi 048

Kërkesa

Pjesëtuesi më i madh i përbashkët (PMP) i disa numrave është ai numër që i plotpjesëton të gjithë.

Na jepet një listë me N numra natyrorë dhe na lejohet të fshimë disa prej tyre (nga 0 deri në N-1, mjafton që lista të mos ngelet bosh).

Bëni një program që gjen numrin më të vogël të elementëve që duhen fshirë, në mënyrë që PMP-ja e numrave që mbeten të jetë 1. Nëse është e pamundur që PMP-ja të bëhet 1, programi duhet të printojë -1.

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

Shembull

$ cat input.txt
2
2
2 3
2
2 4

$ python3 prog.py < input.txt
0
-1

Në rastin e parë nuk është nevoja të fshimë asnjë numër sepse pmp(2,3) == 1.

Në rastin e dytë është e pamundur që PMP të bëhet 1, pavarësisht se cilët numra fshijmë.

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):
    input()
    L = list(map(int, input().split()))

    # gjej pjesetuesin me te madh te perbashket
    p = L[0]
    for n in L:
        p = pmp(p, n)

    print(0) if p==1 else print(-1)

Sqarime

Nqs një numër i plotpjesëton të gjithë numrat e një liste dhe ne heqim disa prej numrave të listës, ky numër i plotpjesëton gjithsesi numrat e mbetur të listës. Kështu që nuk ka gjasa që PMP i një liste të zvogëlohet duke fshirë disa prej elementeve të listës (vetëm mund të rritet).

Si pasojë, nqs PMP i numrave të listës është 1, atere nuk është nevoja të fshimë asnjë prej numrave të listës dhe përgjigja është 0. Përndryshe është e pamundur që PMP të bëhet 1 duke fshirë numra të listës, dhe përgjigja është -1.

Programi ynë thjesht gjen PMP e të gjithë numrave të listës dhe shikon nëse është 1 ose jo.

Zgjidhja 2

import math

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

    # gjej pjesetuesin me te madh te perbashket
    pmp = L[0]
    for n in L:
        pmp = math.gcd(pmp, n)

    print(0) if pmp==1 else print(-1)

Sqarime

Përdorim funksionin e gatshëm gcd() të librarisë math.

Provoni këto komanda në terminal:

$ python3
>>> import math
>>> help(math)
>>> dir(math)
>>> help(math.gcd)
>>> quit()

Shënim: Shtypni q për të dalë nga help().

Zgjidhja 3

from math import gcd
from functools import reduce

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

    # gjej pjesetuesin me te madh te perbashket
    pmp = reduce(gcd, L)

    print(0) if pmp==1 else print(-1)

Sqarime

Funksioni functools.reduce() merr si parametër të parë emrin e një funksioni, dhe si parametër të dytë një listë. Duke përdorur funksionin e dhënë ai i përpunon elementët e listës 2 e nga 2, deri sa ta reduktojë listën në një vlerë të vetme.

P.sh. reduce(gcd, [2, 3, 4, 5]) është e njëvlershme me gcd(gcd(gcd(2, 3), 4), 5).

Shikoni edhe help-in:

$ python3
>>> from functools import reduce
>>> help(reduce)
[Ctrl+D]

Detyra

Cufi sapo ka marrë një lidhje interneti të re. Të dhënat e përdorimit të internetit prej tij janë si më poshtë.

Në \(T_1\) minutat e para shpejtësia e shkarkimit që ka përdorur është \(D_1\) MB në minutë, në \(T_2\) minutat e tjera është \(D_2\) MB/min, e kështu me radhë deri në \(T_N\) minutat e fundit kur shpejtësia ka qenë \(D_N\) MB/min.

Kompania e internetit i faturon 1 dollar për çdo 1 MB të shkarkuar, me përjashtim të \(K\) minutave të para, të cilat janë falas (si pjesë e ofertës).

Gjeni sasinë totale të dollarëve që duhet të paguajë Cufi për internetin e përdorur.

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

Shembull

$ cat input.txt
3
2 2
2 1
2 3
2 2
1 2
2 3
3 0
1 2
2 4
10 10

$ python3 prog.py < input.txt
6
3
110

Çdo rast testimi ka si rresht të parë numrat N dhe K, pastaj vijnë N rreshta me të dhënat e shkarkimit T dhe D.

Në testin e parë, 2 minutat e para janë falas, kështu që kostoja totale është: 2*3 = 6.

Në testin e dytë, 2 minutat e para janë falas, kështu që kostoja totale është: 1*3 = 3.

Në rastin e tretë, 0 minuta janë falas, kështu që kostoja totale është: 1*2 + 2*4 + 10*10 = 110.