infoarena

Aici puteți discuta despre problema Egipt (http://infoarena.ro/problema/egipt).

1. m-am uitat peste problema asta, si din cate imi dau seama solutia nu e unica, s-ar putea sa nu fie inca implementat un verificator pentru sursele trimise? mie imi da pentru testul din exemplu:


2. ce va da pentru valorile astea?


mie imi da:

Există verificator. :)

cineva care a facut problema de 100p, nu ar putea pune un test mai mare/bun decat cel din exemplu, sa imi gasesc greseala :-k :readthis:
mersi

Later Edit:am rezolvat(pacat ca nu am facut-o in timpul concursului :angry:)

Ar putea pune cineva un test (sau unul asemanator ca si cel) de la 2 la 10?

Uite aici arhiva cu testele generate de mine in timpul concursului pt a ma verifica.

http://rapidshare.com/files/369579225/egipt.zip.html

Mersi. Am reusit in cele din urma :D.

Majoritatea surselor se incadreaza in 10ms. Propun scaderea limitei de timp sau cresterea marimii lui N

Atâta timp cât nu există surse ineficiente care iau punctaje mari, nu se impune schimbarea limitei de timp.

Eu am O(3*nr_interschimbari*log(N))   si imi intra in 12 ms ,deci testele ar putea fi marite  :D

Este vreun caz particular ? ca iau doar 90 de pct ...(cu wa pe ultimul test )

Nu se  pune daca se afiseaza i si j in alta ordine?
de exemplu:
1-4
2-3
4-5

Am rezolvat aceasta problema si cu greu am reusit sa obtin 0 puncte. NU spun ca rezolvarea mea este una perfecta pentru exemplu dar la problema se poate gasi mai multe solutii
pentru datele de intrare:
5                                                                                  3                                 3
3                                                                                  2 3                             1 4
2                                     exista urmatoarele solutii            1 4               dar si       2 3
1                                                                                  4 5                             4 5
1
2                                     

as vrea o explicatie suplimentara daca se poate.

Multumesc

Lasati-mi si mie va rog niste teste mai mari. Nu reusesc sa imi dau seama unde gresesc.  :-k

Ideea mea e un fel de greedy. Pornesc de la pozitia 1 si dupa cand dau de o valoare de 2 sau 3 care nu e pozitionata unde trebuie o interschimb cu cea mai la dreapta valoare de 1 (am intr-un vector pozitiile numerelor de 1 , 2 si 3 ) Dupa fac acelasi lucru de la pozitia unde trebuie sa apara primul doi pana la pozitia unde trebuie sa apara ultimul 2. Mi se pare ok modul de gandire.

LE: Am rezolvat ... acum iau 80p.  :D

Salut. Are cineva niste teste mai speciale , ca iau WA pe ultimele doua teste si nu stiu de ce . Mi-am generat o gramada de teste de mana , dar pe toate mi-a dat corect (test cand sirul e ordonat deja , cand avem doar un element , cand e descrescator , etc).

LE : S-a rezolvat , faceam niste interschimbari inutile  :aha:.

Isi da seama cineva ce e gresit la sursa:

#include <cstdio>
 
int mutari=0,n,i,a[100005],n1=0,n2=0,n3=0,i1,i2,i3,aux;
struct schimbare
{
    int i,j;
};
schimbare mut[100005];
 
int main()
{
    freopen("egipt.in","r",stdin);
    freopen("egipt.out","w",stdout);
    scanf("%d",&n);
    for (i=1; i<=n; i++)
    {
        scanf("%d",&a);
        if (a==1) n1++; else if (a==2) n2++; else n3++;
    }
    for (i1=1; i1<=n1; i1++)
        for (i2=n1+1; i2<=n1+n2; i2++)
        if (a[i1]!=1 && a[i2]==1)
    {
        mutari++;
        mut[mutari].i=i1;
        mut[mutari].j=i2;
        aux=a[i1];
        a[i1]=1;
        a[i2]=aux;
    }
 
    for (i1=1; i1<=n1; i1++)
        for (i3=n1+n2+1; i3<=n1+n2+n3; i3++)
        if (a[i1]!=1 && a[i3]==1)
    {
        mutari++;
        mut[mutari].i=i1;
        mut[mutari].j=i3;
        aux=a[i1];
        a[i1]=1;
        a[i3]=aux;
    }
 
    for (i2=n1+1; i2<=n1+n2; i2++)
        for (i3=n1+n2+1; i3<=n1+n2+n3; i3++)
        if (a[i2]!=2 && a[i3]==2)
    {
        mutari++;
        mut[mutari].i=i2;
        mut[mutari].j=i3;
        aux=a[i2];
        a[i2]=2;
        a[i3]=aux;
    }
    printf("%d\n",mutari);
    for (i=1; i<=mutari; i++)
        printf("%d %d\n",mut.i,mut.j);
    return 0;
}

Nu mai este nevoie! :yahoo: :banana: