Problemi 050

Kërkesa

Një listë me numra A quhet e bukur nëse për çdo dy numra të listës \(a_i, a_j (i <> j)\), gjendet në listë një numër \(a_k\) i tillë që \(a_k = a_i * a_j\). Vini re që k mund të jetë edhe i ose j.

Gjeni nëse një listë e dhënë është e bukur ose jo.

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

Shembull

$ cat input.txt
3
2
0 1
2
1 2
2
5 6

$ python3 prog.py < input.txt
yes
yes
no

Zgjidhja 1

Sqarime

Programi bën një cikël të dyfishtë për ti shqyrtuar të gjitha dyshet e mundshme të elementeve, por përjashton ato që kanë indeks të njëjtë (është i njëjti element). Nqs gjen dy numra prodhimi i të cilëve nuk ndodhet në listë, nxirret përgjigja “no” dhe ciklet ndërpriten. Përndryshe, nëse cikli i dyfishtë vazhdon deri në fund pa u ndërprerë, nxirret përgjigja “yes”.

Zgjidhja 2

Sqarime

Llogjika është e ngjashme me zgjidhjen e parë, në kuptimin që shqyrtohen të gjitha dyshet e mundshme dhe prodhimi i tyre. Në fillim supozojmë se lista është e bukur dhe vazhdojmë kontrollin deri sa të gjejmë një dyshe numrash, prodhimi i të cilave nuk ndodhet në listë. Nëse gjejmë një dyshe të tillë, ndryshorja b bëhet False, çfarë bën që edhe të dyja ciklet të ndërpriten.

Kompleksiteti (ose ndërlikushmëria) e këtyre dy zgjidhjeve është \(O(n^3)\) (ose kubike), sepse janë dy cikle nga 1n brenda njëri-tjetrit, por gjithashtu edhe kur kërkojmë të dimë nëse një element ndodhet në listë, zakonisht na duhen \(O(n)\) veprime (mesatarisht \(n/2\)).

Nqs i testojmë këto dy zgjidhje te https://www.codechef.com/submit/ICPC16B ato nuk e kalojnë testin sepse ekzekutimi i programit zgjat mbi 10 sekonda, ndërkohë që limiti i kohës së ekzekutimit që ka problemi është vetëm 2 sekonda.

Zgjidhja 3

Sqarime

Kjo zgjidhje duket pak më ndërlikuar se dy zgjidhjet e mëparshme, por në fakt është shumë më e shpejtë, me kompleksitet të rendit \(O(n)\). Si rrjedhojë kjo zgjidhje e kalon testin në https://www.codechef.com/submit/ICPC16B

Kjo zgjidhje bazohet në disa vëzhgime rreth cilësive të listave të bukura:

  • Nëse një listë ka vetëm 1 element, është e bukur.
  • Nëse në një listë janë 2 (ose më shumë) numra më të mëdhenj se 1, lista nuk mund të jetë e bukur.
  • Nëse lista ka vetëm një numër më të madh se 1 dhe të tjerët janë 0 ose 1, është e bukur.
  • Nëse lista ka më shumë se një -1, duhet të ketë edhe një 1 për të qenë e bukur.
  • Nëse një listë ka një -1 dhe një numër më të madh se 1, nuk mund të jetë e bukur.

Ndryshorja n_1 mban sa -1 ka në listë, n1 sa 1, n0 sa 0, dhe n_other sa numra të tjerë (më të mëdhenj se 1 ose më të vegjël se -1).

Detyra

Sergei ka bërë N matje dhe do të gjejë vlerën mesatare të tyre. Por për të gjetur një mesatare sa më të mirë, ai mendon se duhet ti heqë nga lista e matjeve K vlerat më të vogla dhe K vlerat më të mëdha, para se të llogarisë mesataren. Sa del vlera mesatare në këtë mënyrë?

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

Shembull

$ cat input.txt
3
5 1
2 9 -10 25 1
5 0
2 9 -10 25 1
3 1
1 1 1

$ python3 prog.py < input.txt
4.000000
5.400000
1.000000