Algoge Judge

Tangentni Četvorouglovi

Points: 1

Time limit: 1.0s

Memory limit: 64M

Author:

Problem type

Džeki ima $N$ ~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$ ~4~ različita palidrvca tako da od njih može da napravi tangentan četvorougao.

Podsetnik : Četvorougao $ABCD$ ~ABCD~ je tangentan ako i samo ako važi $AB+CD=AD+BC$ ~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)$ ~(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$ ~N\le1000~: broj palidrvaca. U drugom redu nalaziće $N$ ~N~ različitih prirodnih brojeva, koji predstavljaju dužine palidrvaca. Sve dužine palidrvaca su do $10^5$ ~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

Objašnjenje primera

Takve četvorke su $\{1,2,3,4\},\{1,2,4,5\},\{2,3,4,5\}$ ~\{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+4=2+3~, $1+5=2+4$ ~1+5=2+4~ i $2+5=3+4$ ~2+5=3+4~.

Comments

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?

2

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

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