Pagini recente » Cod sursa (job #331876) | Cod sursa (job #937524) | Cod sursa (job #2183699) | Cod sursa (job #2337579) | Cod sursa (job #1997848)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("order.in");
ofstream out("order.out");
int n;
int arbInt[10001];
int pozSiNrCaut;
int nrCopii;
void creeareArbore(int pozNod, int st, int dr){
if(st == dr){
arbInt[pozNod] = 1;
return ;
}
int mijloc = (st + dr) / 2 ;
creeareArbore(pozNod * 2, st, mijloc);
creeareArbore(pozNod * 2 + 1, mijloc + 1, dr);
arbInt[pozNod] = arbInt[pozNod * 2] + arbInt[pozNod * 2 + 1];
}
void cautareElement(int pozNod , int st, int dr){
if(st == dr){
out << st << ' ';
arbInt[pozNod] = 0;
return ;
}
int mijloc = (st + dr) / 2;
if(pozSiNrCaut <= arbInt[pozNod * 2])//am destule nr pe stanga
cautareElement(pozNod * 2, st, mijloc);
else {
pozSiNrCaut = pozSiNrCaut - arbInt[pozNod * 2] ;//scad cate sunt pe stanga si caut a "pozSiNrCaut"-a poz din intervalul drept
cautareElement(pozNod * 2 + 1, mijloc + 1, dr);
}
arbInt[pozNod] = arbInt[pozNod * 2] + arbInt[pozNod * 2 + 1];//actualizare valori
}
void rezolvare(){
in >> n;
for(int i = 1; i <= n; i++)
creeareArbore(1,1,n);
pozSiNrCaut = 1;
nrCopii = n;
int aux = 1;
for(int i = 1; i <= n; i++){//trebuie sa scot n copii
aux = aux + i;
if(aux > nrCopii)//depasesc limita
aux %= nrCopii;
if(aux == 0)
aux = nrCopii;
if(i != 1)// la fiecare are loc o schimbare de semn
aux --;
if(i == n)
aux = 1;
pozSiNrCaut = aux;
cautareElement(1, 1, n);
nrCopii = arbInt[1];
}
}
int main(){
rezolvare();
return 0;
}