Pentru runda 3:
Foarte bune problemele( mai ales arbpal ).

Felicitari!

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.

4. Split vertices in 2 equal-sized sets. We need 3 states for each vertex:
A. Active in the local set of vertices
B. Active in the whole graph
C. Inactive

From 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 B
B (1): otherwise

If 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 cardinality

Note:
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 edge
B. part of the 2nd edge
C. part of the 3rd edge
D. part of the 4th edge
Generating 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/4
If 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.

@Adrian
Pentu exemplu dat de tine, algoritmul ar functiona asa:
Jucatorul 1:

1 2 3 4 6

r = 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 6

S = 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 <algorithm>
#include <iostream>
#include <vector>
using namespace std;

//#define CHECKALL

#define DEBUGMSG(bla) cout << bla
//#define DEBUGMSG(bla)

int getRest(vector<int> 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 aranjament
vector<int> aranjament(vector<int> carti, int nr)
{
    while (nr)
    {
        next_permutation(carti.begin(),carti.end());
        nr--;
    }
    return carti;
}

//decodifica aranjament
int getVal(vector<int> carti)
{
    int nr=0;
    while (next_permutation(carti.begin(),carti.end()))
    {
        nr++;
    }
    return 23 - nr;
}

vector<int> jucatorul1(vector<int> 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(vector<int>carti)
{
    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<int> vcarti(carti,carti+5);
                        DEBUGMSG("Initial:");
                        for (int i=0; i < vcarti.size(); i++)
                        {
                            sumaVerificare += vcarti[i];
                            DEBUGMSG(vcarti[i]<<" ");
                        }
                        DEBUGMSG(endl);
                        vector<int> arata = jucatorul1(vcarti);
                        DEBUGMSG("Aratate:"<<endl);
                        for (int i=0; i<arata.size(); i++)
                        {
                            DEBUGMSG(arata[i] << " ");
                            sumaVerificare -= arata[i];
                        }
                        DEBUGMSG(endl);
                        int ascunsa = jucatorul2(arata);
                        sumaVerificare -= ascunsa;
                        DEBUGMSG("ascunsa " << ascunsa);
                        DEBUGMSG(endl);

                        if (sumaVerificare != 0)
                        {
                            cout << "e gresit algoritmul!";
                        }
                    }
}

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.

Pentru cartile a b c d e extrase daca consideram ca se arata a b c d(le fixam) atunci de o parte avem
124-4=120 posibilitati(valorile ramase pt e) si de cealalta parte 4! = 24. Deci afisand a b c d putem reprezenta doar
1/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 al
aranjamentului. 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-1<b sau a<val+4<b  nu pusca. Similar in celalalt sens, sau la distante mai mari de 1 fata de pozitia corecta.

Practic ordinea cartilor afisate da catul impartirii la 5 si pozitia cartii ascunse da restul impartirii la 5.

Exemplu:
Jucatorul 1 primeste cartile 10 15 16 17 20
rest = 3, ascunde 17 pune cartile (10 15 16 20) in ordinea corespunzatoare lui 3

Jucatorul 2 primeste cartile (10 15 16 20) aranjate in ordinea 3
noul rest S = 1
n=3
i=0 => val = 4 + 3*5 = 19 dar 19<10 FALS
i=1 => val = 0 + 3*5 = 15 dar 10<15<15 FALS
i=2 => val = 1 + 3*5 = 16 dar 15<16<16 FALS
i=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

Daca 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?

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?

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.

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!

Si 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?

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!!!

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).

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:

Mersi pt indicatii.Cred ca pana la urma o sa fac asa cu socketuri sau o sa incerc si-n java.10x again.

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   .

Io cred ca-i o gluma.Adik hai sa fim seriosi:

If 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?

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.

cand vor avea loc aceste concursuri?

lucrez in pascal si am verificat fisierul de iesire si nu este decat numarul fara alte marcaje.Oricum mersi filipb.

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 )

mips:
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?

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.

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.

..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.