066 Permutari 3

[•domino]

Aici puteţi discuta despre problema Permutari 3.

[•supernova]

Elementele "multimii" M sunt toate distincte?

[•Cosmin]

Daca e multime are prin definitie elementele distincte. Parerea mea ...

[•supernova]

Ma gandeam ca poate din cauza aia nu-mi merge decat pe 2 teste, dar sunt intr-adevar dinstincte. Altfel ar fi fost mai grea problema ...

[•Adriana_S]

eu tot iau wa pe testul 2   . Are ceva mai special?

[•filipb]

Pai ce poate fi asa special? Ai grija sa faci corect daca este prima sau ultima permutare. In rest, nu exista nici un caz particular ( de fapt nici alea doua nu erau cazuri particulare, da' sa nu fi gresit ceva minor ).
De exemplu, pe testul

Cod:

6
1 2 3 4 5 6
1 2 3 4 5 6

sa iti dea 1.

[•Adriana_S]

stiu. Tocmai am luat 100 Am dat testul

Cod:

1
5
5

si mi-am dat seama. oricum, 10x

[•sima_cotizo]

Am si eu o problema aici... Fac o clasa de numere mari, cu fiecare "cifra" din numarul mare retine 5 cifre in sistem zecimal... fiecare numar mare are 1000 cifre => pot retine 5000 de cifre zecimale...

Cu toate astea... iau 20 p, cu WA pe restul... sa fi gresit restul implementarii sau mai trebuie mariti vectorii? 

LE: nevermind, fixed it... clasica initializare de vector... incompleta 

[•Stigma]

imi cer scuze de la inceput daca pun intrebari puerile, dar sunt novice intr-o oarecare masura.

am vazut un timp foarte foarte scurt (MULT mai scurt decat al meu!) la testele care au luat 90-100 puncte. si se pare ca metoda de rezolvare a problemei e ceva arhicunoscut, dar nu mie! eu am generat toate permutarile, in ordine lexicografica, comparand mereu vectorul curent cu cel dat - evident ca imi iese din timp. poate cineva sa ma ajute sa optimizez sau sa gasesc alta metoda? 

[•pauldb]

Te uiti la prima pozitie si numeri cate multimi sunt care incep cu un element mai mic. Apoi reiei algoritmul de la pozitia 2, ca si cum primul element n-ar fi existat. Si tot asa...

[•Stigma]

sa vad daca am inteles
pentru 4 1 3 2 ar trebui sa existe 3! astfel de multimi, nu?
pentru 1 3 2 ar trebui sa existe 0!=1
.
.
.
se pare ca am inteles gresit...
...pentru ce ni se da sirul ordonat crescator atunci?

rog rabdare si intelegere 

[•devilkind]

pentru permutarea 4 1 2 3 calculezi astfel:

Cate permutari de 4 elemente incep cu ceva mai mic ca 4? cu 1 sunt 3!, cu 2 tot 3! si surprinzator cu 3 sunt tot 3!. Deci 3!*3.
Cate permutari de 3 elemente incep cu ceva mai mic ca 1? Nici una.
Cate permutari de 2 elemente incep cu ceva mai mic ca 2? Tot nici una, deoarece permutarea nu poate sa inceapa cu 1, ptr ca 1 a fost folosit inainte, iar o permutare nu poate sa contine de 2 ori acelasi element. Tu cand ajungi la pasul acesta practic vrei sa vezi cate elemente incep cu 4 1 si sunt mai mici ca 4 1 2 3.
De asemenea ptr pasul urmator (numarul de permutari de 1 element care incep cu ceva mai mic ca 3).

Raspunsul pana la urma va fi 3!*3 = 18.

[•Stigma]

eee asa da! multumesc frumos!  scuze ca v-am irosit timpul

[•alex_mircescu]

Imi dati si mie un hint la testu' 10 ... nu-i dau de cap... iau WA...WA si iar WA 

[•anna_bozianu]

Daca lucrezi cu numere mari si in baza 10 raspunsul se incadreaza pe 3000 de cifre ( posibil mai putine, nu am avut rabdare sa verific ) . Vezi daca nu ai declarat vectori prea mici pentru operatii cu nr mari.

[•alex_mircescu]

limitele sunt bune, e altceva...
 
pentru testul maxim
1000
1 ..... 1000
1000...... 1
cat va da?
mie imi da:

Cod:

804774520154187547087404867846007971438749728421429265087599820859877024797258041184088416973938809600959977220394392117263333745989617117802647659339889181994849008174147519837647255454377465039559011901990552241749950924994087202836556189292992582112787774875772974674238362091651567295699954024953265779671911470865026370647916926151114818228524834948698695106857293153223335594793337640582414758287707439176499616253735676749119463492272170759069048443173186403856181756594616862785688806562463117222073953602714608432337495219351742696624050957178641534338264896852472262825017560416000523366302054683655955409569271736340328730048307382796562529620426185522489792719857410229929950839818684443133665144161642666372233623107231673093968093417951205801901075232951695456843779359292489890321530706816397802770884975969919906638203446711113204278900799472561500275675230614255523853698068705250400031777070294663223404207936351843021815576038786356228389090514447731082922125784375920447677942952177012553725934293349395125822468164878416320307561779787929036526487343233524358337819559823807508062549244579976010390888828564024374723491985285913163493256605911140598048648306363234420931664073573812234520317567041503032568451080530340966608452287948573866123381795936965180250916654336452916133053539917305364545614151562783716357779304416328696689651986532086735320353999225663721576772300558931910262313104072187976361224277117200602871389054448412689263594921189365146207580168048864876931314490028805643770504941870381241858046272986546995131027917441119308457499548022826693925430845691724754775076460967731377952923854767629800281534620893280519798980444443531808679803772037133052970123599404712387794035720081623779459836622042342459691803283842137768774243711292249921597445817038593638744777285229679314764582246250048373298706287940274857063853299750674437881388562868237040316028246689656030102799388580306966155289138198146304866556576539729205579728642278167012434190005194779727108554393485644497515173531504688440415147261138997650175937856325507697726793819919652561912242901989743402489032922520758058618241778173884057021280364308798914313611883745497996188509484347164802127354809191483570321658460270716163680193992745048461121711807401248542486833818008307380211867967671555878821940055506944000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

[•anna_bozianu]

Raspunsul tau e dublu fata de ce mi-a dat mie.
Probabil ca raspunsul meu e corect (evaluatorul mi-a dat 100 de puncte).

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Deci undeva inmultesti cu 2. Totusi e de mirare ca numai la testul asta nu ti-a dat.

[•alex_mircescu]

mersi...sper ca asta era 

>LE<  sutaaa...!!! 

[•avram_florin]

Cred ca timpul de executie e prea mare pentru problema asta.Ar trebui redus undeva intre 0.3-0.5 sec.

[•Florian]

Cred ca timpul de executie e prea mare pentru problema asta.Ar trebui redus undeva intre 0.3-0.5 sec.

De fapt, cred ca trebuie redus la 0.1 secunde.

[•Mishu91]

Cred ca timpul de executie e prea mare pentru problema asta.Ar trebui redus undeva intre 0.3-0.5 sec.

Atâta timp cât nu există soluții ineficiente care să ia punctaj mare, nu văd de ce ar fi redusă limita de timp.

[•Magnus]

e o mica problema in pagina problemei:
daca apesi pe comentarii si selectezi pagina a doua se poate da scroll si in dreapta, nu numai in sus si jos cum ar trebui (am verificat cu internet explorer,firefox,chrome,opera)
nu e cine stie ce bug, dar ar fi bine sa fie reparat

[•devilkind]

Poti sa precizezi si ce rezolutie folosesti? Mie mi se vede bine.

[•Magnus]

eu folosesc 1366x768 (am incercat si cu 1280x768,1280x720,1024x720,800x600, tot la fel), deci nu pare sa fie de la asta,
dar celelalte pagini (1 si 3) mi se vad bine, in afara de asta.
tu ai intrat de pe forum sau de pe pagina problemei?
ceea ce vreau sa spun cu asta este ca http://infoarena.ro/forum/index.php?topic=386 se vede bine,
dar http://infoarena.ro/problema/perm3#comentarii nu se vede bine daca selectezi pagina 2 de la comentarii

[•devilkind]

Da am inteles ce zici, in schimb mie imi merge bine si incerc sa vad de ce tie nu ti se vede bine .