infoarena

infoarena - concursuri, probleme, evaluator, articole => Stelele Informaticii 2009 => Subiect creat de: Bogdan-Cristian Tataroiu din Februarie 07, 2009, 09:35:37


Titlul: Planeta
Scris de: Bogdan-Cristian Tataroiu din Februarie 07, 2009, 09:35:37
Aici puteti pune intrebari despre problema Planeta (http://infoarena.ro/problema/planeta).

Titlul: Răspuns: Planeta
Scris de: razyelx din Februarie 07, 2009, 10:38:24
Cum se rezolva?

Titlul: Răspuns: Planeta
Scris de: Andrei Grigorean din Februarie 07, 2009, 10:58:49
FARA COMENTARII :)

Titlul: Răspuns: Planeta
Scris de: Bogdan-Cristian Tataroiu din Februarie 07, 2009, 11:05:06
Timpul de intrebari a expirat. Bafta in continuare

Titlul: Răspuns: Planeta
Scris de: alexandru din Februarie 07, 2009, 13:23:17
Desi  ii putin c-am tarziu,  exemplul dat in problema 
15 14023
1 2 3 4 5 15 8 7 6 14 9 12 10 11 13
nu-i  gresit  si ar fi trebuit in loc de
1 2 3 4 5 15 8 7 6 14 9 12 10 11 13 sa  fie  1 2 3 4 5 6 7 10 14 11 15 9 8 12 13
sau in loc de  14023  3352213?

 
 

Titlul: Răspuns: Răspuns: Planeta
Scris de: Cosmin-Mihai Tutunaru din Februarie 07, 2009, 14:03:42
Citat din mesajul lui: alexandru din Februarie 07, 2009, 13:23:17
Desi  ii putin c-am tarziu,  exemplul dat in problema 
15 14023
1 2 3 4 5 15 8 7 6 14 9 12 10 11 13
nu-i  gresit  si ar fi trebuit in loc de
1 2 3 4 5 15 8 7 6 14 9 12 10 11 13 sa  fie  1 2 3 4 5 6 7 10 14 11 15 9 8 12 13
sau in loc de  14023  3352213?
 

Sunt si eu curios daca defapt era numarul de ordine a unei permutari cu n elemente.....

 :-'

Titlul: Răspuns: Planeta
Scris de: Tirca Bogdan din Februarie 07, 2009, 14:41:05
nu e ca incercai eu :D
later : aaa.. sa fie gresit exemplu zici u? nu cred

Titlul: Răspuns: Răspuns: Planeta
Scris de: Cosmin-Mihai Tutunaru din Februarie 07, 2009, 15:22:32
Citat din mesajul lui: Tarca Bogdan din Februarie 07, 2009, 14:41:05
nu e ca incercai eu :D
later : aaa.. sa fie gresit exemplu zici u? nu cred

Da....asa ma gandeam eu :D
Oricum....vedem peste o ora doua....cand se afiseaza rezultatele

Titlul: Răspuns: Planeta
Scris de: Tirca Bogdan din Februarie 07, 2009, 15:24:33
dak n=0 iau si eu 10 p =))
later : 1 ≤ N ≤ 30 mdea 0 p >:D<

Titlul: Răspuns: Planeta
Scris de: alexandru din Februarie 07, 2009, 17:16:10
Ba eu cred ca  ii , am folosit vreo 5 algoritmi care genereaza  toate permutarile de ordin n in ordine lexicografica si nici unul nu a dat pentru  n=15 si k=14023 configuratia din exemplu :P
Uitati un  algoritm folosit, stiu ca nu e prea eficienta, dar le afiseaza in ordine lexicografica:
Cod:
#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
int n,k,v[100],uz[100];
void gen(int c)
   {
    if(c-1==n)
      {k--;
       if(k==0){for(int i=1;i<=n;i++) cout<<v[i]<<" "; getche(); exit(0);}
      }
      else for(int i=1;i<=n;i++)
              if(!uz[i])
                {v[c]=i; uz[i]=1;
                 gen(c+1);
                 uz[i]=0;
                }
   }
void main()
   {
    cin>>n>>k;
    gen(1);
   }

Titlul: Răspuns: Planeta
Scris de: Tirca Bogdan din Februarie 07, 2009, 19:12:02
off. nu trebuie generate primele k permutari ~X( ca asa s-ar fi dat la oji clasa 7 cel mult :|

Titlul: Răspuns: Planeta
Scris de: alexandru din Februarie 07, 2009, 20:15:44
Citat
off. nu trebuie generate primele k permutari ~X( ca asa s-ar fi dat la oji clasa 7 cel mult
Nu progamul asta  l-am  postat  pentru  testare, logic ca e altul :P ca altfel  nu s-ar fi  incadrat in timp, ma refer un program care pur si simplu genereaza  babeste a k permutare ,  ii bine de stiu cand vrei sa te convigi de unele lucruri :P

Titlul: Răspuns: Planeta
Scris de: Flaviu Pepelea din Februarie 07, 2009, 20:31:24
nu ai drepate, aici nu trebuie sa afli a k permutare!!! Incearca pt n = 3 si ai sa vezi ca nu sunt toate permutarile! Cele care pot aparea sunt:
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1
Daca esti atent permutarea 2 3 1 lispeste :P

Era prea simplu daca trebuia generata doar a k - a permutare. Asta se poate in O(N) :)


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines