Tangentni Četvorouglovi

View as PDF

Submit solution


Points: 1
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Džeki ima N palidrvaca (štapića) različitih celobrojnih dužina. Ona je veliki obožavalac tetivnih četvorouglova, ali voli i tangentne. Stoga, interesuje je na koliko načina može da izabere 4 različita palidrvca tako da od njih može da napravi tangentan četvorougao.

Podsetnik : Četvorougao ABCD je tangentan ako i samo ako važi AB+CD=AD+BC. U prevodu od vas se traži da nađete koliko postoji načina da izaberete četvorku (a,b,c,d) tako da je ove brojeve moguće podeliti u dva para jednakih suma.

Opis ulaza

U prvom redu standardnog ulaza nalaziće se N\le1000: broj palidrvaca. U drugom redu nalaziće N različitih prirodnih brojeva, koji predstavljaju dužine palidrvaca. Sve dužine palidrvaca su do 10^5

Opis izlaza

U prvom i jedinom redu standardnog izlaza ispisati jedan broj: broj četvorki palidrvaca od kojih je moguće napraviti tangentan četvorougao.

Primer ulaza

5
1 2 4 5 3

Primer izlaza

3

Objašnjenje primera

Takve četvorke su \{1,2,3,4\},\{1,2,4,5\},\{2,3,4,5\}, jer njih možemo da podelimo na parove 1+4=2+3, 1+5=2+4 i 2+5=3+4.


Comments


  • 0
    iva_here_  commented on June 10, 2021, 9:18 p.m. edited

    Dobardan, imam jedan mali problem vezan za zadatak. Nakon sto posaljem kod na proveru test primera, javlja da moj kod prekoracava vremenska ogranicenja, a nije mi bas jasno zasto, jer je ceo kod sastvljen iz if i while petlji koje ne bi trebale da uticu na slozenost programa. Evo i koda(pisanog u C++-u):

    #include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        int n;
        cin>>n;
        int duzine[1000+5];
    
        int i=0;
    
        while (i<n)
        {
            cin>>duzine[i];
            i++;
        }
    
        int broj=0;
    
        int i1=0;
    
        while (i1<n-3)
        {
            int i2=i1+1;
    
            while (i2<n-2)
            {
                int i3=i2+1;
    
                while (i3<n-1)
                {
                    int i4=i3+1;
    
                    while (i4<n)
                    {
                        if (duzine[i1]+duzine[i2]==duzine[i3]+duzine[i4])
                        {
                            broj++;
                        }
    
                        if (duzine[i1]+duzine[i3]==duzine[i2]+duzine[i4])
                        {
                            broj++;
                        }
    
                        if (duzine[i1]+duzine[i4]==duzine[i2]+duzine[i3])
                        {
                            broj++;
                        }
    
                        i4++;
                    }
    
                    i3++;
                }
    
                i2++;
            }
    
            i1++;
        }
    
        cout<<broj;
    }

    Ako neko ima ideju zasto je ovaj kod prespor, da li bi mogao da napise u komentaru ispod?


    • 1
      mihailot  commented on June 11, 2021, 3:51 p.m.

      Problem je što je složenost tvog rešenja O(N^4) što je previše sporo za ograničenje N \le 1000 koje je dato u zadatku.