•Mishu91
|
|
« Răspunde #50 : Octombrie 04, 2009, 10:55:07 » |
|
Încearcă să calculezi după o formulă de genul cmmmc(...cmmmc(cmmmc(v[ 1 ], v[ 2 ]), v[ 3 ])... v[ N ]). Pentru că produsul v[ 1 ] * v[ 2 ] * v[ 3 ] * ... * v[ N ] e posibil să iasă din long long.
|
|
|
Memorat
|
|
|
|
•zeroblitz36
Strain
Karma: -5
Deconectat
Mesaje: 18
|
|
« Răspunde #51 : Februarie 22, 2011, 22:36:58 » |
|
1 0ms 244kb Corect! 5 2 0ms 8kb Corect! 5 3 0ms 16kb Corect! 5 4 0ms 12kb Corect! 5 5 8ms 12kb Corect! 5 6 0ms 12kb Corect! 5 7 0ms 12kb Corect! 5 8 0ms 12kb Corect! 5 9 0ms 8kb Corect! 5 10 4ms 260kb Corect! 5 11 0ms 8kb Corect! 5 12 4ms 8kb Corect! 5 13 4ms 12kb Corect! 5 14 0ms 8kb Corect! 5 15 4ms 16kb Corect! 5 16 0ms 8kb Corect! 5 17 0ms 12kb Corect! 5 18 0ms 12kb Corect! 5 19 4ms 8kb Corect! 5 20 0ms 8kb Corect! 5 Punctaj total 100 Moamah ce noroc, cred ca are complexitate O(log n)
|
|
|
Memorat
|
|
|
|
•Alexandru13
Strain
Karma: 1
Deconectat
Mesaje: 5
|
|
« Răspunde #52 : Iulie 27, 2011, 12:00:00 » |
|
int valid(int k) { for(int j=1;j<=k;j++) if(p[j]!=j) return 0; return 1; } int main() { f>>n; for(i=1;i<=n;i++) f>>p[i]; for(;valid(n)==0;nr++) { for(i=1;i<=n;i++) p[i]=p[p[i]]; } g<<nr; g.close(); f.close(); return 0; } ma poate ajuta cineva.. nu imi dau seama cu ce am gresit.
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #53 : Iulie 27, 2011, 13:09:22 » |
|
Nu am vazut sursa trimisa, cat ai luat cu ea. Iti da bine pe exemple ?
|
|
|
Memorat
|
|
|
|
•Alexandru13
Strain
Karma: 1
Deconectat
Mesaje: 5
|
|
« Răspunde #54 : August 02, 2011, 08:56:58 » |
|
nici nu am trimis sursa. imi intra in bucla... nu imi da nici un rezultat si nu stiu cum sa fac, nu inteleg greseala.
|
|
|
Memorat
|
|
|
|
•ctlin04
|
|
« Răspunde #55 : August 14, 2011, 12:25:44 » |
|
Dati cineva ceva indicii pentru determinarea ciclului fiecarui numar in O ( n ), am citit postul lui Adrian, dar nu-mi dau seama cum pot sa marchez undeva ceva, eu generez toate permutarile pe rind pina cind toate numerele nu s-au repetat cel putin odata, apoi fac cmmmc dintre ciclurile determinate, si astfel iau TLE la testele 1,5 si 10, pls, help
|
|
|
Memorat
|
|
|
|
•Steve
Client obisnuit
Karma: 36
Deconectat
Mesaje: 72
|
|
« Răspunde #56 : August 15, 2011, 03:29:34 » |
|
Edit: Ia un vector binar pana la N pe care il initializezei cu 0. cand ajunge elementul pe pozitia pe care vrei, marchezi in vectorul binar. Daca mai ai nevoie de ajutor PM! O(N) Sper ca n-am zis prea mult sry
|
|
|
Memorat
|
|
|
|
•ctlin04
|
|
« Răspunde #57 : August 15, 2011, 10:01:59 » |
|
Ms mult Stefan, am prins ideea
|
|
|
Memorat
|
|
|
|
•VisuianMihai
|
|
« Răspunde #58 : Octombrie 14, 2011, 17:31:10 » |
|
nu inteleg la al treilea exemplu... care sunt permutarile
|
|
|
Memorat
|
|
|
|
•SpiderMan
|
|
« Răspunde #59 : Octombrie 14, 2011, 21:25:05 » |
|
FA ca la mate pe foaie si o sa vezi .
|
|
|
Memorat
|
|
|
|
•gabitzish1
|
|
« Răspunde #60 : Octombrie 14, 2011, 21:51:48 » |
|
p1: 1 5 2 3 4 8 6 7 p2: 1 4 5 2 3 7 8 6 p3: 1 3 4 5 2 6 7 8 p4: 1 2 3 4 5 8 6 7 p5: 1 5 2 3 4 7 8 6 p6: 1 4 5 2 3 6 7 8 p7: 1 3 4 5 2 8 6 7 p8: 1 2 3 4 5 7 8 6 p9: 1 5 2 3 4 3 6 7 8 p10: 1 4 5 2 3 8 6 7 p11: 1 3 4 5 2 7 8 6 p12: 1 2 3 4 5 6 7 8
Deci raspunsul e 12.
E bine sa citesti prima data ce s'a mai postat pe un anumit subiect, poate nu mai e nevoie sa intrebi.
|
|
|
Memorat
|
|
|
|
•granny
Strain
Karma: 0
Deconectat
Mesaje: 2
|
|
« Răspunde #61 : Februarie 29, 2012, 00:57:14 » |
|
Salut tuturor , stiu ca e cam tarziu sa discut despre aceasta problema , dar nu pot intelege dc scot decat 90 puncte si nu inteleg ce pot sa mai fac.. am observat ciclul pe ex 3 , am facut asa si nu imi da 100.. imi da ca am depasit limita de timp la test 1 si test 10.. am calculat gradele si le-am pus intr-un vector. si am facut cmmmc apoi.. aveti vreun sfat?
|
|
|
Memorat
|
|
|
|
•Trixer
Strain
Karma: 0
Deconectat
Mesaje: 3
|
|
« Răspunde #62 : Martie 25, 2012, 17:41:50 » |
|
va rog vrumos explicati-mi si mie ce vrea enuntul asta de la mine, nu inteleg deloc. spune la exemplul 1 ca solutia este k=1 iar in enunt spune ca Pk(i) = p(i) pentru ca k=1, deci rezulta p(1)=2; p(2)=3; p(3)=4... nu inteleg nimic
|
|
|
Memorat
|
|
|
|
•DorelBarbu
Strain
Karma: 0
Deconectat
Mesaje: 34
|
|
« Răspunde #63 : Iulie 08, 2012, 12:02:19 » |
|
Salut! Sunt nou aici. Am incercat si eu sa rezolv aceasta problema. Rezolvarea am gasit-o singur, insa am probleme cu implementarea. Pe sursa mea obtin 30 pct. Am mers pe urmatoarea idee. Am creat un vector vp, in care vp retine o valoare, care arata la cate repetitii apare cifra i pe pozitia i. Dupa care am facut cmmc-ul tuturor valorilor din acest vector. Sunt constient ca implementarea mea, nu este cea mai buna ( si este departe de a o putea numi macar "buna"), si de aceea va cer ajutorul.
#include <iostream> #include <fstream> #include <string.h> using namespace std; int n; int v[100000],v2[10000],vp[100000]; void citeste() { freopen("perm2.in","r",stdin); scanf("%d",&n); int i; for(i=1; i<=n; i++) scanf("%d",&v[i]); } int completeaza(int k,int i) { if(k==1) return v[i]; else return v[completeaza(k-1,i)]; } bool verifica(int j) { if(v2[j]!=j) return false; return true; } int cmmdc(int a, int b) { int c; while (b) { c=a%b; a=b; b=c; } return a; } int calculeazacmmmc() { int a=1,b=1,m,cmmc,i; a=vp[1]; b=vp[2]; m=cmmdc(a,b); cmmc=a*b/m; a=cmmc;
for(i=3; i<=n; i++) { b=vp[i]; m=cmmdc(a,b); cmmc=a*b/m; a=cmmc; }
return cmmc; }
int main() { ofstream out("perm2.out"); citeste(); int i=0,j,a=1,b=1,nrc; j=n+1; for(j=1; j<=n; j++) { while(verifica(j)==false) { i++; v2[j]=completeaza(i,j); } vp[j]=i; i=0; }
out<<calculeazacmmmc(); return 0;
}
M-ati putea ajuta, va rog? Multumesc anticipat!
|
|
|
Memorat
|
|
|
|
•danalex97
|
|
« Răspunde #64 : Iulie 09, 2012, 10:21:27 » |
|
La tine nu implementarea este problema , ci ideea de rezolvare. Algoritmul tau lucreaza prea incet pentru ca faci de mai multe ori acelasi lucru. Ia un sir in care cand ajunge elementul pe pozitia pe care vrei il marchezi. Succes !
|
|
|
Memorat
|
|
|
|
•DorelBarbu
Strain
Karma: 0
Deconectat
Mesaje: 34
|
|
« Răspunde #65 : Iulie 09, 2012, 11:22:04 » |
|
Deci, prin secventa asta de cod, nu fac ceea ce ai zis tu?: for(j=1; j<=n; j++) { while(verifica(j)==false) { i++; v2[j]=completeaza(i,j); } vp[j]=i; i=0; }
Adica, de ce fac de prea multe ori acelasi lucru? Trec prin fiecare pozitie, o data, pentru a plasa acolo elementul corespunzator. La sfarsit calculez cmmc-ul. Scuza-ma, dar cred (sunt aproape sigur), ca nu am inteles prea bine ce ai vrut sa spui. Ai putea, te rog, sa fii putin mai detaliat (nu vreau mura in gura!!!)? Multumesc!
|
|
|
Memorat
|
|
|
|
•TwistedFaith
Strain
Karma: 0
Deconectat
Mesaje: 8
|
|
« Răspunde #66 : Octombrie 23, 2012, 09:06:54 » |
|
Killed by signal 11(SIGSEGV). la toate testele.
|
|
|
Memorat
|
|
|
|
•SebiSebi
|
|
« Răspunde #67 : Octombrie 23, 2012, 09:16:17 » |
|
Declara tablourile in afara main-ului. Succes!
|
|
|
Memorat
|
|
|
|
•TwistedFaith
Strain
Karma: 0
Deconectat
Mesaje: 8
|
|
« Răspunde #68 : Octombrie 23, 2012, 09:38:21 » |
|
Eu am declarat vectorii asa: int n; fin>>n; int v[2][n],k[n/2+3]; pt ca sa mananc cat mai putin spatiu. Daca ar fi sa ii declar in afara main ar trebui sa le dau 20000, respectiv v[2][20000] (1 rand pentru permutare si 1 pentru verificare/marcare) si k[10000] (pt a pune lungimea ciclilor in el).
|
|
|
Memorat
|
|
|
|
•SebiSebi
|
|
« Răspunde #69 : Octombrie 23, 2012, 09:45:44 » |
|
Asa ii declari. Compilatorul oricum calculeaza doar cat folosesti. Deci, nu pierzi memorie.
|
|
|
Memorat
|
|
|
|
•DxH5dIMHN
Strain
Karma: -5
Deconectat
Mesaje: 9
|
|
« Răspunde #70 : Noiembrie 07, 2012, 04:49:31 » |
|
Câţi? 15! Ce 15? Ce câţi? perm2.in 21 12 3 16 5 19 8 21 14 18 10 4 17 1 11 2 20 6 13 7 15 9 perm2.out 15 46 de linii de cod -> punctaj total: 100
|
|
|
Memorat
|
|
|
|
•Daniel_Bot
Strain
Karma: 0
Deconectat
Mesaje: 1
|
|
« Răspunde #71 : Februarie 20, 2013, 14:39:13 » |
|
+1 pentru ideea lui DITzoneC
|
|
|
Memorat
|
|
|
|
•DorelBarbu
Strain
Karma: 0
Deconectat
Mesaje: 34
|
|
« Răspunde #72 : August 18, 2013, 13:28:17 » |
|
Ar putea cineva sa detalieze putin chichita? Cunosc notiunea de ciclu al unei permutari. Am reusit sa obtin 80 de puncte, intelegand ca algoritmul meu era infeicient, si imbunatatindu-l, facand cateva mici retusuri. Dar pic testele 1,5,10,12. Ma poate ajuta cineva?
|
|
|
Memorat
|
|
|
|
•vld7
Strain
Karma: 7
Deconectat
Mesaje: 17
|
|
« Răspunde #73 : August 18, 2013, 19:41:54 » |
|
Tu in functia in care completezi matricea gasesti pentru fiecare element i un numar c[ i ] astfel incat permutarea la puterea c[ i ] sa aiba elementul i pe pozitia corespunzatoare. Nu e necesar sa verifici la toate pentru ca ciclul unei permutari iti da pentru toate elementele care-l alcatuiesc acel c[ i ]. Daca ai de exemplu ciclul (1, 3, 4) ridicand la putere vei avea 1 -> 3 -> 4 -> 1 deci {1, 3, 4} vor fi pe pozitiile 1, 3 si 4 in p^3, p^6 etc.
|
|
|
Memorat
|
|
|
|
•DorelBarbu
Strain
Karma: 0
Deconectat
Mesaje: 34
|
|
« Răspunde #74 : August 18, 2013, 20:39:31 » |
|
Iti multumesc frumos pentru ajutor! Am reusit si eu sa iau 100 de puncte. Multumesc din nou! Spor la rezolvat!
|
|
|
Memorat
|
|
|
|
|