infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din Mai 23, 2005, 14:18:45


Titlul: 066 Permutari 3
Scris de: Mircea Pasoi din Mai 23, 2005, 14:18:45
Aici puteţi discuta despre problema Permutari 3 (http://infoarena.ro/problema/perm3).

Titlul: Răspuns: 066 Permutari 3
Scris de: Mihai Pantis din Iunie 11, 2005, 22:35:53
Elementele "multimii" M sunt toate distincte?

Titlul: Răspuns: 066 Permutari 3
Scris de: Cosmin Negruseri din Iunie 11, 2005, 23:25:25
Daca e multime are prin definitie elementele distincte. Parerea mea ...

Titlul: Răspuns: 066 Permutari 3
Scris de: Mihai Pantis din Iunie 12, 2005, 07:42:20
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 ...

Titlul: Răspuns: 066 Permutari 3
Scris de: Adriana Sperlea din Decembrie 04, 2005, 21:34:09
eu tot iau wa pe testul 2  :( . Are ceva mai special?

Titlul: Răspuns: 066 Permutari 3
Scris de: Filip Cristian Buruiana din Decembrie 04, 2005, 21:45:44
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.

Titlul: Răspuns: 066 Permutari 3
Scris de: Adriana Sperlea din Decembrie 04, 2005, 21:52:55
stiu. Tocmai am luat 100 :D Am dat testul
Cod:

1
5
5
si mi-am dat seama. oricum, 10x

Titlul: Răspuns: 066 Permutari 3
Scris de: Sima Cotizo din Martie 29, 2007, 09:27:29
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  :roll:

Titlul: Răspuns: 066 Permutari 3
Scris de: Simina Pitur din Martie 07, 2008, 22:24:07
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?  :'(

Titlul: Răspuns: 066 Permutari 3
Scris de: Paul-Dan Baltescu din Martie 08, 2008, 00:51:16
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...

Titlul: Răspuns: 066 Permutari 3
Scris de: Simina Pitur din Martie 08, 2008, 14:30:52
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  :'(

Titlul: Răspuns: 066 Permutari 3
Scris de: Savin Tiberiu din Martie 08, 2008, 15:19:22
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.

Titlul: Răspuns: 066 Permutari 3
Scris de: Simina Pitur din Martie 08, 2008, 16:53:44
eee asa da! multumesc frumos!  [-o< scuze ca v-am irosit timpul

Titlul: Răspuns: 066 Permutari 3
Scris de: Alex Mircescu din August 21, 2008, 15:41:01
Imi dati si mie un hint la testu' 10 ... nu-i dau de cap... iau WA...WA si iar WA  #-o

Titlul: Răspuns: 066 Permutari 3
Scris de: Bozianu Ana din August 21, 2008, 18:36:41
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.

Titlul: Răspuns: 066 Permutari 3
Scris de: Alex Mircescu din August 22, 2008, 09:00:20
limitele sunt bune, e altceva...
 
pentru testul maxim
1000
1 ..... 1000
1000...... 1
cat va da?
mie imi da:
Cod:
804774520154187547087404867846007971438749728421429265087599820859877024797258041184088416973938809600959977220394392117263333745989617117802647659339889181994849008174147519837647255454377465039559011901990552241749950924994087202836556189292992582112787774875772974674238362091651567295699954024953265779671911470865026370647916926151114818228524834948698695106857293153223335594793337640582414758287707439176499616253735676749119463492272170759069048443173186403856181756594616862785688806562463117222073953602714608432337495219351742696624050957178641534338264896852472262825017560416000523366302054683655955409569271736340328730048307382796562529620426185522489792719857410229929950839818684443133665144161642666372233623107231673093968093417951205801901075232951695456843779359292489890321530706816397802770884975969919906638203446711113204278900799472561500275675230614255523853698068705250400031777070294663223404207936351843021815576038786356228389090514447731082922125784375920447677942952177012553725934293349395125822468164878416320307561779787929036526487343233524358337819559823807508062549244579976010390888828564024374723491985285913163493256605911140598048648306363234420931664073573812234520317567041503032568451080530340966608452287948573866123381795936965180250916654336452916133053539917305364545614151562783716357779304416328696689651986532086735320353999225663721576772300558931910262313104072187976361224277117200602871389054448412689263594921189365146207580168048864876931314490028805643770504941870381241858046272986546995131027917441119308457499548022826693925430845691724754775076460967731377952923854767629800281534620893280519798980444443531808679803772037133052970123599404712387794035720081623779459836622042342459691803283842137768774243711292249921597445817038593638744777285229679314764582246250048373298706287940274857063853299750674437881388562868237040316028246689656030102799388580306966155289138198146304866556576539729205579728642278167012434190005194779727108554393485644497515173531504688440415147261138997650175937856325507697726793819919652561912242901989743402489032922520758058618241778173884057021280364308798914313611883745497996188509484347164802127354809191483570321658460270716163680193992745048461121711807401248542486833818008307380211867967671555878821940055506944000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Titlul: Răspuns: 066 Permutari 3
Scris de: Bozianu Ana din August 22, 2008, 17:34:13
Raspunsul tau e dublu fata de ce mi-a dat mie.
Probabil ca raspunsul meu e corect (evaluatorul mi-a dat 100 de puncte).

Citat
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

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

Titlul: Răspuns: 066 Permutari 3
Scris de: Alex Mircescu din August 30, 2008, 13:59:41
mersi...sper ca asta era  :thumbup:

>LE<  sutaaa...!!!  :-'

Titlul: Răspuns: 066 Permutari 3
Scris de: avram florin constantin din Februarie 05, 2010, 22:45:21
Cred ca timpul de executie e prea mare pentru problema asta.Ar trebui redus undeva intre 0.3-0.5 sec.

Titlul: Răspuns: 066 Permutari 3
Scris de: Florian Marcu din Februarie 05, 2010, 22:52:55
Citat din mesajul lui: avram florin constantin din Februarie 05, 2010, 22:45:21
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 (http://infoarena.ro/job_detail/389167).

Titlul: Răspuns: 066 Permutari 3
Scris de: Andrei Misarca din Februarie 06, 2010, 00:33:08
Citat din mesajul lui: avram florin constantin din Februarie 05, 2010, 22:45:21
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. :)

Titlul: Răspuns: 066 Permutari 3
Scris de: cont cu nume gresit sau fals din Mai 28, 2011, 12:05:27
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 ;)

Titlul: Răspuns: 066 Permutari 3
Scris de: Savin Tiberiu din Mai 28, 2011, 14:39:54
Poti sa precizezi si ce rezolutie folosesti? Mie mi se vede bine.

Titlul: Răspuns: 066 Permutari 3
Scris de: cont cu nume gresit sau fals din Mai 28, 2011, 15:09:33
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 (http://infoarena.ro/forum/index.php?topic=386) se vede bine,
dar http://infoarena.ro/problema/perm3#comentarii (http://infoarena.ro/problema/perm3#comentarii) nu se vede bine daca selectezi pagina 2 de la comentarii

Titlul: Răspuns: 066 Permutari 3
Scris de: Savin Tiberiu din Mai 28, 2011, 19:10:49
Da am inteles ce zici, in schimb mie imi merge bine si incerc sa vad de ce tie nu ti se vede bine :).

Titlul: Răspuns: 066 Permutari 3
Scris de: Mihai Visuian din Decembrie 18, 2011, 17:53:03
Ati gasit vreo formula recurenta la metoda programarii dinamice?

Titlul: Răspuns: 066 Permutari 3
Scris de: TestulSuprem din Martie 10, 2012, 19:00:42
aceasta declarare este buna?long long  a[1010],b[1010]
iau wa pe testele 3-10 si cred ca sunt de vina vectorii 

Titlul: Răspuns: 066 Permutari 3
Scris de: andreycurent din Martie 10, 2012, 19:55:23
@Gigel cel Bun : Rezultatul acestei probleme ajunge pe undeva pe la 2500 cifre sau cat are 1000! ... de aceea va trebui sa lucrezi cu numere mari. http://infoarena.ro/lucrul-cu-nr-mari (http://infoarena.ro/lucrul-cu-nr-mari) E un link ajutator ... iar o idee de rezolvare a scris-o Savin Tiberiu la pagina 2.


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