Afişează mesaje Pagini: [1] 2
 1 infoarena - concursuri, probleme, evaluator, articole / .com 2012 / Răspuns: Feedback .com 2012 : Martie 11, 2013, 12:25:51 Pentru runda 3:Foarte bune problemele( mai ales arbpal ).Felicitari!
 2 Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Fox Hunting : August 31, 2012, 11:22:57 If the holes are numbered from 0 to 10, first assume that the fox is in an odd numbered hole(let's call "F" the position of the fox). F switches between even and odd every step that the fox makes. Since now F is odd, it can't be 0, so we check hole 1. If F != 1, F must have been one of 3,5...9, so in the next step we are certain that F will be at least 2. We check further in hole 2. If F!=2, then F certainly is one of 4,6,8,10 so F will be bigger than 2 in the next step. And so on until we reach hole 9. If F!=9 we have reached a contradiction( if our assumption was correct, in this point F should be odd, but we are also certain F >9). Then F must have been an even number initially. But 9 steps have passed, so F must be odd now. We repeat the whole process, being certain that this time we will find the fox.18 steps are needed in worst-case.
 3 Comunitate - feedback, proiecte si distractie / Blog / Răspuns: Meet in the middle : August 11, 2012, 08:53:02 4. Split vertices in 2 equal-sized sets. We need 3 states for each vertex:A. Active in the local set of verticesB. Active in the whole graphC. InactiveFrom all generated sets(3^(n/2)) we must check if the A and B vertices cover all egdes between all vertices in the set. If so, then we encode the configuration treating A and C the same(ex: A,C->0; B->1). Associated with the hash we should also keep the A and B sets. We do the same thing with the second set, checking in first's hashlist for a complementary configuration:For every vertex from the first set we expect it's value to be:A or C (0): if all edges between this vertex and the second set's vertices are BB (1): otherwiseIf a complementary configuration is found then A and B vertices from the first and the second set form a vertex-cover. We keep the vertex-cover with the smallest cardinalityNote:The reason why we actually need 3 states comes from the fact that while a vertex which isn't in the vertex cover(inactive) implies that all vertices in the other set that share an edge with it must be in the vertex cover, an edge that is already in the vertex cover(active) implies nothing about the vertices from the other set that share an edge with it. This is a variable we don't want when we need to search the exact configuration hash, so one solution is to split the active state into: active only locally in the set and active overall.5. Split the array in 2 equal-sized sets. For each set, associate to each of the set elements one of the states:A. part of the 1st edgeB. part of the 2nd edgeC. part of the 3rd edgeD. part of the 4th edgeGenerating all possible configuration will take O(4^(n/2))We keep as a hash the resulted sizes of the 4 edges. Associated to this hash we keep the sets for each state.When we compute hashes for the second set we search for the complementary configuration in the first:desired edge size - edge1 size(sum of all A planks in second set)desired edge size - edge2 size(sum of all B planks in second set)desired edge size - edge3 size(sum of all C planks in second set)desired edge size - edge4 size(sum of all D planks in second set)Where (desired edge size) = sum of all planks/4If such configuration is found, then the union is the answer.6. We generate all configurations that are reachable in 16 moves from the given position and we hash them. Associated to the hash we keep the moves used to reach this configuration. We generate all configurations that are reachable in 15 moves from the final position and search the hash for each. If found, then the moves associated to the hash followed by the reversed list of moves used to reach the "middle" configuration starting with the final configuration is the answer.
 4 Comunitate - feedback, proiecte si distractie / Blog / Răspuns: 4 carti : Iunie 23, 2012, 16:11:06 @AdrianPentu exemplu dat de tine, algoritmul ar functiona asa:Jucatorul 1:1 2 3 4 6r = 16%5 = 1, deci se ascunde cartea cu index 1, adica 2.Aranjamentul  cartilor 1 3 4 6 trebuie sa codifice valoarea 2/5 = 0 ( deci jucatorul 2 le primeste in acceasi ordine ). Jucatorul 2:1 3 4 6S = 14%5 = 4, n=0(valoare din ordinea aranjamentului)Daca i = 0 -> 5*0+(0-4+5)%5=1, dar 1<1 e fals, deci nu poate fi vorba de slotul 0.Daca i = 1 -> 5*0+(1-4+5)%5=2, 1<2<3 ceea ce e ok, deci valoarea cartii e 2.Cu toate astea din exemplul tau mi-am dat seama ca pentru carti mai mari de 119 algoritmul meu nu ar merge, pt ca permutarea codifica de la 0 la 23 nu pana la 24 si 23*5+rest<=119. Pentru a putea codifica 124 carti, trebuie transmisa valoarea cartii - pozitia ei, si cum pozitia ei este dedusa de jucatorul 2, cu o mica corectie la cat, se poate reconstitui valoarea. Mai jos codul algoritmului, poate se intelege mai bine.Accepta carti de la 0 la 123:Cod:#include #include #include using namespace std;//#define CHECKALL#define DEBUGMSG(bla) cout << bla//#define DEBUGMSG(bla)int getRest(vector carti){    int rest = 0;    for (int i=0; i < carti.size(); i++)    {        if (carti[i] >= 124)        {            cout << "Eroare!";        }        rest = (rest + carti[i]) % 5;    }    return rest;}//codifica aranjamentvector aranjament(vector carti, int nr){    while (nr)    {        next_permutation(carti.begin(),carti.end());        nr--;    }    return carti;}//decodifica aranjamentint getVal(vector carti){    int nr=0;    while (next_permutation(carti.begin(),carti.end()))    {        nr++;    }    return 23 - nr;}vector jucatorul1(vector carti){    if (carti.size() != 5)    {        cout << "Eroare!";    }    sort(carti.begin(),carti.end());    int rest = getRest(carti);    int valC = carti[rest];    carti.erase(carti.begin() + rest);    return aranjament(carti , (valC - rest) / 5);}int jucatorul2(vectorcarti){    int sumaInitialaMod5 = getVal(carti);    if (carti.size() != 4)    {        cout << "Eroare!";    }    int rest = getRest(carti);    sort(carti.begin() , carti.end());    for (int i=0; i<5; i++)    {        int r = ( i + 5 - rest ) % 5;      // restul cartii ascunse        int corectieCat = (i>r)?1:0;        int val = r + (sumaInitialaMod5 + corectieCat)*5;        if (i==0)        {            if ( !(val < carti[i]) ) continue;        }        else if (i == 4)        {            if  ( !(val > carti[i-1]) )  continue;        }        else        {            if ( !( (carti[i-1] < val)&&(val < carti[i]) ) ) continue;        }        // slotul acesta e ok        return val;    }    // slotul nu a fost gasit    cout << "e gresit algoritmul!";    return -1;}int main(){    int sumaVerificare=0;#ifdef CHECKALL    int carti[5];    for (carti[0]=0; carti[0]<=123; carti[0]++)        for (carti[1]=carti[0]+1; carti[1]<=123; carti[1]++)            for (carti[2]=carti[1]+1; carti[2]<=123; carti[2]++)                for (carti[3]=carti[2]+1; carti[3]<=123; carti[3]++)                    for (carti[4]=carti[3]+1; carti[4]<=123; carti[4]++)#else    int carti[]= {6,4,3,2,1};#endif                    {                        vector vcarti(carti,carti+5);                        DEBUGMSG("Initial:");                        for (int i=0; i < vcarti.size(); i++)                        {                            sumaVerificare += vcarti[i];                            DEBUGMSG(vcarti[i]<<" ");                        }                        DEBUGMSG(endl);                        vector arata = jucatorul1(vcarti);                        DEBUGMSG("Aratate:"<
 5 Comunitate - feedback, proiecte si distractie / Blog / Răspuns: 4 carti : Iunie 22, 2012, 09:10:51 Am uitat ceva destul de important. Inainte de a ascunde cartea (a+b+c+d+e)%5, a b c d e sunt sortate si abia apoi e aleasa cartea cu indexul respectiv. La fel la jucatorul 2, odata ce a extras informatia data de ordinea aranjamentului, sorteaza a b c d si abia apoi incearca cele 5 sloturi.
 6 Comunitate - feedback, proiecte si distractie / Blog / Răspuns: 4 carti : Iunie 22, 2012, 01:09:34 Pentru cartile a b c d e extrase daca consideram ca se arata a b c d(le fixam) atunci de o parte avem124-4=120 posibilitati(valorile ramase pt e) si de cealalta parte 4! = 24. Deci afisand a b c d putem reprezenta doar1/5 din valorile posibile ale lui e. M-am gandit sa reprezint valori din 5 in 5 pentru ca pentru fiecare a b c d sa corespunda un invariant e%5 .Ascundem intotdeauna cartea cu indexul (a+b+c+d+e)%5. Aranjam cartile sa reprezinte valoarea cartii ascunse / 5 ( 124/5 <= 4! deci ar trebui sa putem reprezenta toate valorile). Jucatorul 2 va avea 2 informatii cu care va reconstitui secventa: suma S a celor 4 carti ramase modulo 5 si numarul n de ordine alaranjamentului. Incercand fiecare slot i (0<=i<=4) unde sa introduca cartea ascunsa, valoarea acesteia ar fi val = ( 5+i-S )%5 + 5*n pentru ca i reprezinta si suma celor 5 carti initiale modulo 5. Dar cartea se poate potrivi doar intr-un slot deoarece:Daca din a b c d e ascundem c, deci val=c , cu un slot inapoi(i-1), val va fi cu o unitate mai mica sau cu 4 unitati mai mare. Si a val = 4 + 3*5 = 19 dar 19<10 FALSi=1 => val = 0 + 3*5 = 15 dar 10<15<15 FALSi=2 => val = 1 + 3*5 = 16 dar 15<16<16 FALSi=3 => val = 2 + 3*5 = 17      16<17<20 ADEVARAT!Daca observati ceva erori in demonstratie va rog sa imi spuneti. N-as stii sa demostrez ca redundanta e zero la solutia mea... Problema e foarte misto
 7 infoarena - concursuri, probleme, evaluator, articole / Informatica / Raspuns: cel mai lung drum : Februarie 08, 2007, 13:41:09 Citat din mesajul lui: Mircea Pasoi din Februarie 08, 2007, 12:50:46Daca ai graf oarecare si inlocuiesti fiecare nod cu o muchie atunci un drum cat mai lung care nu trece printr-o muchie decat odata e echivalent cu un drum hamiltonian.Da nu-i sigur ca poate exista un ciclu hamiltonian in graf chiar daca adaugam un nod prin care legam sursa de destinatie.Adik poate de la sursa la destinatie putem trece numai prin cateva noduri nu neaparat prin toate(daca avem noduri terminale de exemplu).Nu?
 8 infoarena - concursuri, probleme, evaluator, articole / Informatica / cel mai lung drum : Februarie 07, 2007, 12:50:22 Problema mea este urmatoarea:Am un graf(cu cicluri), un punct de pornire si un punct de oprire.Trebuie sa gasesc cel mai lung drum intre cele 2 puncte fara se trec prin aceeasi muchie de 2 ori ,avand voie sa trec prin orice nod de cate ori vreau.Nu stiu dak are importanta dar fiecare muchie are costul 1.Ce algoritmi as putea folosi pt a rezolva cat mai optim problema?
 9 Comunitate - feedback, proiecte si distractie / Off topic / mea culpa : Octombrie 04, 2006, 16:41:58 Ok stiu k informatica este diferita de programare, am spus informatica pt k n-am vrut ca "programare" sa se repete si n-am crezut k cineva o sa observe si o sa-mi atraga atentia  .In plus programatori sunt deseori numiti "informaticeni" chiar de multi care cunosc aceasta diferenta.In al doilea rand nu stiam ca exista facultate de AC la UBB.Credeam k este doar mate-info iar multi mi-au zis k mate-info nu se merita.Am citit postul lui Cosmin legat de UBB pt k chiar eu am cerut informatii si atunci .In momentul acela n-am primit prea multe pareri si nici nu ma interesa chiar asa tare fiindca eram a 10. Acum am intrebat ink odata cerand mai multe detalii.
 10 Comunitate - feedback, proiecte si distractie / Off topic / Facultati de info din Ardeal : Octombrie 04, 2006, 13:09:39 Am vazut subiectul de mai sus dar din pacate n-am gasit nici o informatie legata de vreo facultate din cluj,timisoara,etc.Ii rog pe cei care sunt,au fost studenti ,sau au informatii legate de subiect sa imi dea niste indicatii.M-am gandit sa urmez Automatizari si calculatoare si as dori sa stiu ce facultate imi recomandati.Pana acum am vrut sa merg la Politehnica Timisoara dar si Universitatea tehnica Cluj(cineva mi-a spus k are legaturi cu Microsoft.Ii adevarat?) pare o optiune buna.Nu prea stiu ce vreau sa fac in informatica asa ca am nevoie de cunostinte in fiecare domeniu al programarii.Deasemenea caut o facultate care ofera studentilor oportunitati de munca (sa aiba tot felu de legaturi cu firme din strainatate sau chiar din Romania).Daca cunoasteti voi alta facultate klumea din Ardeal va rog sa-mi ziceti si mie(cu argumente).Va multumesc anticipat!
 11 Comunitate - feedback, proiecte si distractie / Arhiva / Propuneri : Noiembrie 08, 2005, 12:23:43 Citat din mesajul lui: danielpSi asa sursele de la ONI, baraje se mai gasesc si din anii trecuti si se poate invata de acolo.Voi unde ati gasit sursele ca io nu le gasesc pe nici un site oficial ONI .Nu-mi poate da cineva un link plz?
 12 Comunitate - feedback, proiecte si distractie / Arhiva / Propuneri : Octombrie 26, 2005, 18:40:19 Cred ca realizarea acestui proiect nu prea depinde de noi ci doar de administratori.Mai bine zis daca ei hotarasc sa faca asta sau nu.Noi cred ca putem doar sa-i incurajam sa o faca si sa ne exprimam dorinta asta in numar cat mai mare.A si am mai putea face un lucru:[dreaming] Am putea realiza o aplicatie file-sharing cu un server si aplicatie client,un evaluator propriu care sa verifice daca sursele respective sunt corecte(sau macar partial pentru ca nush daca putem sa facem teste pt toate cazurile ca si eval-u infoarena) caz in care serverul permite clientului vizualizarea tuturor surselor trimise la problema respectiva   [/dreaming].Si eu cred de asemenea ca open-source este o solutie foarte buna care ne-ar ajuta pe toti.Postati cat mai multi sa-i convingem!!!
 13 Comunitate - feedback, proiecte si distractie / Arhiva / Propuneri : Octombrie 25, 2005, 12:57:07 Asa stiam si eu ca sursele de la ONI nu se mai fac publice din motive "morale".Mai mult site-ul ONI 2004 care odata continea sursele concurentilor a fost modificat si nu mai apar decat sursele grupei gimnaziale(eu cel putin n-am mai gasit arhiva 9-12).
 14 Comunitate - feedback, proiecte si distractie / Off topic / Patente ?!? : Iunie 27, 2005, 18:14:44 Deci pana la urma chestia asta cu "patentele" ii un fel de adio software,adio freeware,welcome opensource.De fapt asta ii ideea ca daca vreau sa fac un soft chiar si freeware si refuz sa-i dezvalui sursa pot fi dat in judecata nu? Daca asa sta treaba toata chestia asta mi se pare un mare cosmar(mai ales pt cei care dorim sa lucram in acest domeniu)... :cry:
 15 Comunitate - feedback, proiecte si distractie / Off topic / Plz help!! : Iunie 26, 2005, 15:35:29 Mersi pt indicatii.Cred ca pana la urma o sa fac asa cu socketuri sau o sa incerc si-n java.10x again.
 16 Comunitate - feedback, proiecte si distractie / Off topic / Plz help!! : Iunie 25, 2005, 14:02:50 Vreau sa fac un program care trimite un mail cu fisiere atasate dar fara sa fie vizibil si fara interventia utilizatorului(nu-i nimic de hacking serios   ).Am cautat pe net da n-am gasit nimic si va rog daca stiti sa-mi dati niste indicatii(ce limbaj de programare sa folosesc si eventual niste linii de cod...) ca deja de 1 saptamana ma tot chinui   .
 17 Comunitate - feedback, proiecte si distractie / Off topic / Patente ?!? : Iunie 25, 2005, 08:24:30 Io cred ca-i o gluma.Adik hai sa fim seriosi:CitatIf that happens, software developers will no longer own what they write and can be sued for selling or distributing their own software. Asta ce vrea sa insemne?Atunci cine mai face softul?
 18 Comunitate - feedback, proiecte si distractie / Sondaje / Concursuri de vara : Iunie 24, 2005, 18:59:44 Mai da secretosi mai sunteti .Oricum as vrea sa propun ca sa se tina concursuri si in august pt ca multi dintre noi pleaca in vacanta in iulie si sa prindem si noi cate ceva cand ne intoarcem.
 19 Comunitate - feedback, proiecte si distractie / Sondaje / Concursuri de vara : Iunie 24, 2005, 07:43:14 cand vor avea loc aceste concursuri?
 20 infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / 073 Perechi : Iunie 19, 2005, 08:18:55 lucrez in pascal si am verificat fisierul de iesire si nu este decat numarul fara alte marcaje.Oricum mersi filipb.
 21 infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / 073 Perechi : Iunie 18, 2005, 15:01:08 Am facut problema si am facut teste verificand rezultatul prin forta bruta si toate testele pe care le-am facut mi-au iesit bine.Problema este ca iau 0 puncte si nu stiu de ce.Poate cineva care a rezolvat corect problema sa-mi zica cat ii da pt:5040 : mie mi-a dat 203 si la fel si pe programul de verificare.87297210:imi da 7655 da asta nu l-am testat (prea mult de asteptat )
 22 Comunitate - feedback, proiecte si distractie / Arhiva / Am descoperit un bug... : Mai 09, 2005, 17:17:56 Citat din mesajul lui: dobremips:Probabil ca ai pus variabila i locala si cine stie pe unde pierdeai...Sau poate a avut evaluatorul un bug pentru moment si apoi s-a rezolvat.Nu mi se pare logic sa se intample asa   .Apropo ti-a dat WA sau eroare?Nu mi-a dat WA,mi-a dat eroare de compilare iar variabila i era globala.Procedura care am facut-o incrementa i tot ca variabila globala.Asta a fost singura procedura din tot programu.bogdan2412: Fiind moderator,n-ai acces la sursa mea?
 23 Comunitate - feedback, proiecte si distractie / Arhiva / Am descoperit un bug... : Mai 09, 2005, 15:38:24 No asta-i 100% bug.Am folosit cautare binara ca sa gasesc "eroarea" din sursa mea .Am ajuns la o adunare:'i:=i+1'.Am inlocuit adunarea cu o procedura care face exact aceasi operatie si am luat 100 de puncte   .Totusi ar trebui sa verificati care a fost problema ca s-ar putea s-o pateasca si altu ca mine.
 24 Comunitate - feedback, proiecte si distractie / Arhiva / Am descoperit un bug... : Mai 08, 2005, 14:05:31 Asta-i foarte ciudat.Cand pun click pentru detalii nu-mi zice nimic in locul unde ar trebui sa-mi spuna ce erori am in program. Cred ca este un bug sau poate am gresit eu ceva dar m-as mira c-am trimis 3 surse la aceasi problema si la toate mi-o dat eroare de compilare.Rog administratorii sa se uite si sa-mi zica de ce nu-mi compileaza.
 25 Comunitate - feedback, proiecte si distractie / Arhiva / Am descoperit un bug... : Mai 08, 2005, 12:44:15 Citat din mesajul lui: Fr3eM4n..la tine se compileaza ca probabil ai alt compilator. o eroare destul de des intalnita e ca declari variabile in "mijlocul" functilor, si trebuie doar la inceputul lor.Nu e cazul deoarece lucrez in pascal si variabilele se pot declara numai la inceput.Cat despre compilator,am aceasi versiune ca si cea folosita pentru evaluare.
 Pagini: [1] 2