1011 Egipt

[•stef2n]

Aici puteți discuta despre problema Egipt.

[•crus]

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:

Cod:

3
1 3
2 4
3 5

2. ce va da pentru valorile astea?

Cod:

6
3
2
3
2
1
1

mie imi da:

Cod:

3
1 5
2 6
3 6

[•stef2n]

Există verificator.

[•andrey932]

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

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

[•danimihalca]

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

[•toni2007]

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

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

[•danimihalca]

Mersi. Am reusit in cele din urma .

[•gabipurcaru]

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

[•Mishu91]

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.

[•Bogdan_tmm]

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

[•vendetta]

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

[•VisuianMihai]

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

[•serediucctin]

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

[•danalex97]

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

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. 

[•hasmasandragos]

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  .

[•RaduToporan]

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;
}

[•RaduToporan]

Nu mai este nevoie!