446 Sort

[•filipb]

Aici puteţi discuta despre problema Sort.

[•Tabara]

Salut.
La problema, in enunt s-a scapat la un moment dat acolo la Cerinta un "h2" din scrierea cu headere din Textila.
"h2.Cerinta:"

Scuze.Aceasta nu este o observatie rautacioasa!
Just wanted to help!
 

[•filipb]

Foarte bine ca sesizati micile erori Calitatea enunturilor creste considerabil prin aportul a mai multor persoane.

[•Florian]

Daca tot veni vorba....propozitiile de la restrictii incep cu litera mica...desi kiar nu ma deranjeaza...[dar nu la pb asta...la cele de a 7a..]

[•peanutz]

Se repara......

[•gabitzish1]

Problema s'a dat la IOI 1996. Azi am gasit'o pe USACO data ca un exemplu pt greedy.

Sorting a three-valued sequence [IOI 1996]

You are given a three-valued (1, 2, or 3) sequence of length up to 1000. Find a minimum set of exchanges to put the sequence in sorted order.

[•dornescuvlad]

http://infoarena.ro/job_detail/571357
Sursa fara afisare care primeste 20 de puncte.Din ce cauza? 

[•vlcmodan]

Am citit si eu acuma problema si mi se pare interesanta.
Parerea mea in legatura cu modul de rezolvare este urmatarea:
Numaram cate numere de 2 ar trebui inlocuite de 1(int x1)/3(int x2) ;cate numere de 3 ar trebui inlocuite cu 2(int x3)/1(int x4) si cate numere de 1 ar trebui inlocuite cu 2(int x5)/3(int x6);
Acuma cel mai eficient ar fi daca am face o inlocuire astfel incat ambele numere sa ajunga pe pozitiile care trebuie.Dupa ce am parcurs acet lucru ar trebui sa ramana  t numere de 1 t numere de 2 si t numere de 3 care trebuie inlocuite intre ele( exemplu 3,1,2) adica cate 3 mutari si adunam 3*t.
Sper ca m-am facut inteles

[•Theodor1000]

Pai la testul opt in fisierul de iesire trebuie sa-ti dea 0, probabil asta e cauza... dar la primul n-are sens deaprece trebuie sa-ti iasa 8.
O fi avand infoarena un bug

[•StarGold2]

Sunt in clasa a 6-a si am facut problema de 30 puncte nu inteleg care este sistemul lor de corectare dar nu sunt multumit,am dat nu stiu cate teste si imi da bine  .Ideea mea este sa fac un for pana la ultima pozitie de 2 si sa inlocuiesc de la 1-ultima pozitie de 1 cu prinul numar de 1 luat de la sfarsit si de la x(ultima pozitie de 1)+1-ultima pozitie de 2 cu primul element de la n la ultima pozitie de 2+1 intr-un alt vector sortat.Nu sunt sigur daca m-am facut inteles,dar uite si sursa ca sa intelegeti mai bine:
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
ifstream fin("sort.in");
ofstream fout("sort.out");
int a,v[50002],w[50002],i,j,k,ok,minim,maxim,n,m,x,o,p,y,s;
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v;
        w=v;
    }
    sort(w+1,w+n+1);
    maxim=1;
    for(i=1;i<=n;i++){
        if(w>maxim){
            x=i-1;
            break;
        }
    }
    maxim=3;
    for(i=n;i>=1;i--){
        if(w<maxim){
            y=i;
            break;
        }
    }
    for(i=1;i<=y;i++){
        if(i<=x&&v!=1){
            for(j=n;j>x;j--){
                if(v[j]==1){
                    s++;
                    m=v;
                    v=v[j];
                    v[j]=m;
                    break;
                }
            }
        }
        if(i>x&&i<=y&&v!=2){
            for(j=n;j>y;j--){
                if(v[j]==2){
                    s++;
                    m=v;
                    v=v[j];
                    v[j]=m;
                    break;
                }
            }
        }
    }
    fout<<s;
    return 0;
}

[•PlayLikeNeverB4]

Fie ca esti nemultumit sau nu, tot ai o greseala in cod.

Uite un test:
6
2 3 1 2 3 1

Raspuns corect:
2

[•StarGold2]

YEEY!!
Dupa un an si 5 ore reusesc in sfarsit sa iau suta

[•MareSite]

Uhuu una dintre problemele care chiar mi-au placut