Titlul: 458 Order 2 Scris de: Filip Cristian Buruiana din Mai 22, 2007, 15:19:29 Aici puteţi discuta despre problema Order 2 (http://infoarena.ro/problema/order2).
Titlul: Răspuns: 458 Order 2 Scris de: Paul-Dan Baltescu din Mai 22, 2007, 19:42:13 Poate ar fi mai interesant la problema asta sa se ofere punctajul si in functie de numarul de mutari.
Eu m-am gandit la ceva de genul 100-([X/N]-2)*20, unde x e numarul de mutari. Voi ce spuneti? Titlul: Răspuns: 458 Order 2 Scris de: Paul-Dan Baltescu din Mai 23, 2007, 10:01:57 Daca nu ma insel, ultimele 3 teste au N>1000. :eyebrow:
Titlul: Răspuns: 458 Order 2 Scris de: Savin Tiberiu din Mai 23, 2007, 10:06:15 :-# s-a corectat
Titlul: Răspuns: 458 Order 2 Scris de: Gabi Tulba-Lecu din Martie 01, 2016, 15:19:46 Imi poate spune cineva cum trebuie rezolvata problema? Adica... rezolvata pentru mai putin de 2N+1 operatii.
Pentru 2N+1 operatii am rezolvat-o si nu stiu cum altfel sa o abordez. Help! Aici este codul meu: #include <iostream> #include <fstream> using namespace std; ifstream in("order2.in"); ofstream out ("order2.out"); int N,sort[2002],arr[2002]; int part(int *arr,int start,int end) { int index=start,piv=arr[end],t; for(int i=start;i<=end;i++) if(arr<=piv) { t=arr; arr=arr[index]; arr[index]=t; index++; } index--; return index; } void Qsort(int *arr,int start,int end) { int index; if (start<end) { index=part(arr,start,end); Qsort(arr,start,index-1); Qsort(arr,index+1,end); } } void Read() { in>>N; for(int i=1;i<=N;i++) { in>>arr; sort=arr; } Qsort(sort,1,N); } int find(int n,int *arr,int start,int end) { int pos; for(int i=start;i<=end;i++) if(arr==n) { pos=i; break; } return pos; } void Reverse(int *arr,int pos) { int t; for(int i=1;i<=pos/2;i++) { t=arr; arr=arr[pos-i]; arr[pos-i]=t; } for(int i=pos+1;i<=N-(N-pos)/2;i++) { t=arr; arr=arr[N+1-i+pos]; arr[N+1-i+pos]=t; } out<<pos<<'\n'; } bool checkforpos(int sortpos,int arrpos) { int val=false; if(arr[arrpos-1]==sort[sortpos-1]) val=true; return val; } void Bringforward(int pos) { int posarr=find(sort[pos],arr,1,N); if(!checkforpos(pos,posarr)) { Reverse(arr,posarr); Reverse(arr,posarr+1); } } int main() { Read(); for(int i=1;i<=N;i++) Bringforward(i); if(arr[1]==sort[N]) Reverse(arr,N+1); return 0; } |