Pai tocmai ca BAC - ul nu e in regula, iar informatica din liceu e o amestecatura nefericita. Cum ar trebui sa fie nu stiu si nici nu stiu care ar trebui sa fie scopul ei.Pentru asta avem oameni si ei nu isi fac treaba. Noi avem laboratoare de informatica foarte bine dotate si totusi nu am reusit sa scapam de borland c. Asta spune multe. Aici voiam si eu sa ajung. Sunt asa de multe chestii gresite incat faza cu STL chiar n-are nicio relevanta.

Chestia cu STL la bac este un mare moft. Mihai Calancea cred ca tu pui problema complet gresit.

1. Vorbind strict de bac nu o sa ai niciodata nevoie de hash sau de map sau ceva ce nu se poate implementa foarte repede.
2. Informatica din liceu nu isi propune sa fie nici o materie de structuri de date nici una de algoritmi si cu atat mai putin sa te faca programator sau castigator de ACM. Ca nici fizica nu te face fizician, de exemplu.
3. Da stiu, nenorocitii aia de profi care ii invata pe elevi programare in C cu cin si cout si zic ca e C++ si n-ar stii sa corecteze daca ai folosit STL. Dar hai sa ne mai uitam si la noi. Cati din cei care termina la mate-info au habar sa scrie un hello world ? Persoanele despre care vorbesti tu si sunt dezavantajate sunt doar o mica parte din cei care dau bacul.
4. Multi dintre olimpicii la info, cu calitati algoritmice remarcabile, nu stiu sa scrie o clasa in C++. Si nu pentru ca ar fi ceva complicat dar nu le-a trebuit asta niciodata. Deci hai sa nu ne cacam nici noi pe noi ca vrem sa rezolvam glumele alea de probleme de la bac in C cu STL.

Eu am participat doar la 2 ONI-uri deci clar nu am experienta celor de dinainte. Dar poate ca tocmai asta imi ofera o perspectiva mai buna asupra lucrurilor.

In primul rand, chestia cu evaluatorul e o prostie. Din motivele expuse de Vlad Gavrila + ca s-ar duce tot farmecul. Una e sa iesi din concurs si sa astepti apoi cu sufletul la gura, sa discuti cu ceilalti cum au facut si alta ar fi sa iesi stiind ca iei x puncte. Nu poti sa compari OJI cu IOI. Normal ca acolo treaba e serioasa si sunt alte conditii.

Apoi chestia cu selectia pentru ONI e foarte proasta. Stiu ca e foarte improbabil sa se schimbe ceva dar totusi e cam nasol acum si trebuie inceput de undeva. E aiurea sa iei in functie de clasamentul pe tara pentru ca o sa te trezesti cu judete nereprezentate. Eu nu inteleg de ce nu se ia primul, de la fiecare clasa, de la fiecare judet, si apoi in functie de clasamentul pe tara. Asa esti sigur ca ai fiecare judet reprezentat si iti raman destule locuri si pentru cei buni, dezavantajati de sistemul actual, chiar daca, in unele judete, si cei de pe primul loc au punctaje mici. Daca nu esti cel mai bun nici din judet, nici la nivel national nu prea ai ce sa cauti la ONI, locul unde se intalnesc cei mai buni din tara. E mai motivant sa te lupti sa ajungi printre cei mai buni decat sa stii ca esti intr-un judet in care si daca iei 20 de puncte o sa te califici.

O sa fiu foarte nepopular pentru ce zic acum dar nu inteleg de ce trebuie mereu sa ii plangem de mila comisiei. Mereu comisia se victimizeaza ca o virgina pangarita. Ok, am inteles, este munca voluntara, timpul e scurt, de facut sunt multe. Tot respectul meu pentru voi. Dar majoritatea sunteti studenti si fosti olimpici, deci ati beneficiat si voi de voluntariatul si munca altor oameni, mai ales cei care ati fost tari. Stiti de la bun inceput conditiile asa ca e penibil sa va lamentati apoi. Asa cum munciti voi se pregatesc si altii un an intreg pentru o mana de probleme. Nu va cere nimeni un set perfect echilibrat sau mai stiu eu cum. Dar macar se poate acorda o mai mare atentie redactarii problemelor si eventual testelor. La unele probleme testele pur si simplu si-au batut joc de munca participantilor. Imi aduc aminte pe clasa a 9a ca aveam o problema unde trebuia sa simplifici niste fractii sau ceva de genu. Enuntul a fost gresit si am fost anuntati foarte tarziu ca e nevoie de numere mari. Ori mie ca elev incepator de clasa a 9a mi-ai schimbat total problema. Nu ma incalzeste cu nimic ca a fost gresita pentru toti deoarece daca ai avut proasta inspiratie sa incepi cu problema aia e aiurea pentru ca intervine sansa si nu e normal. E aiurea si sa ai un enunt de o pagina jumate in care informatiile inutile sa fie in mai mare cantitate decat cele utile. E frumos sa ai si o poveste in spatele problemei dar uneori se exagereaza. Eu sunt sigur ca niste enunturi clar redactate, cu limite precizate calumea ar mai reduce din erori. In ultima vreme s-a imbunatatit calitatea lor in privinta asta, dar totusi mai mereu se nimereste o problema la care e gresit enuntul. E drept ca vine comisia apoi cu precizari dar pana trimit ei o tipa din aia pe tocuri sa se plimbe prin toate clasele se duce dracu tot timpu(asta la OJI)


Singur chestie utila si realizabila mi se pare sa maresti durata la OJI la 4 ore. Marea majoritate a participantilor sunt incepatori, e greu sa le ceri sa scrie cod bun si rapid. Stiu ca sunt si astea calitati necesare si importante dar orice ati zice e frustrant sa ai o idee calumea si sa nu ai timp sa o implementezi bine si iei mai putin decat aia care fac back.

Pentru ca nu respecti standardul actual.

Cod:

#include<iostream.h>
#include<fstream.h>

sunt invechite. Inlocuieste cu

Cod:

#include<iostream>
#include<fstream>

using namespace std;

Din cate tin eu minte problema asta admite si o rezolvare cu programare dinamica. E mai usor de inteles. Ar trebui sa incerci.

Ca o completare..

push_back(x) adauga elementul x la sfarsitul vectorului si creste dimensiunea vectorului cu 1
pop_back() sterge elementul de la sfarsitul vectorului si scade dimensiunea vectorului cu 1
O alta functie utila, presupunand ca ai un vector a, este a.size() care iti returneaza numarul de elemente ale vectorului a

Se declara exact cum ai spus tu acolo vector<int> a[10]. Acel 10 reprezinta numarul de noduri.

Cod:

 
a[x].push_back(y);              //inseamna ca adaug nodul y la lista de vecini a nodului x
for(int i=0;i<a[x].size();i++)  //parcurg lista de vecini a nodului x in care se afla a[x].size() noduri
 int vecin=a[x][i];               // al i+1- lea nod din lista de vecini a lui x     

 Accesarea e la fel ca la matrice dar ai grija ca indexarea se face de la 0. Adica primul nod din lista de vecini a nodului x este A[ x ][0] al doilea A[ x ][1] si asa mai departe. Elementul A[ x ][z] exista doar daca ai facut z+1 operatii push_back(). Cu alte cuvinte, desi poti simula si in felul asta o matrice, ai grija sa nu accesezi elemente inexistente altfel s-ar putea sa iei KBS.

Nu stiu sa iti raspund la intrebare dar problema asta o poti rezolva si altfel. Sa zicem ca ai un vector A si -100<=i<=100. O sa declari A[205] sa zicem. Acum imi fixez originea pe pozitia 100. Pentru asta iei o variabila mid=100. Iar acum elementul de pe pozitia i din vector se gaseste la A[mid+i]. Asta o poti extinde mai departe si in 2 dimensiuni. Poate ca nu e asa elegant dar e o metoda.

Cum ti s-a mai zis timpul de executie e strans legat de memorie. Coada o poti declara char. Incearca asa.

Vezi ca si inversul il faci prost. De fapt cam tot de pe acolo e prost.

Tu stii deja din enunt cum se numesc fisierele : intrare.txt si iesire.txt. In bucata asta de cod ce faci ?

Cod:

  fstream f1(nume,ios::in),f2(nume,ios::in);

De ce afisezi pe ecran si nu tot in fisier ? Daca tot ai facut tu ceva si te-ai straduit incearca sa intelegi unde gresesti. Daca iti spunem noi nu inveti nimic.

Poti sa compilezi si sa rulezi programe fara sa faci proiecte, CodeBlocks iti permite asta.

Si ce legatura are asta cu ce a intrebat el ?

Poate n-are evaluator si compara fisierul .in cu cel .out doar. Tin minte ca mi s-a intamplat si mie la o problema. Poate merge daca incerci sa le afisezi crescator, asa par acolo. Adica daca din solutie fac parte muchiile 1 2 si 1 3 afiseaza mai intai pe 1 2.

Nu e de la tine. Asteapta sa rezolve un admin problema

Apropo...cum se rezolva problema asta de 100 de puncte ? Se poate O(n^2) ? Avand in vedere ca sunt asa putine scoruri de 100 chiar nu cred ca s-ar supara nimeni daca ar da cineva o solutie.

In loc sa te chinui sa parsezi ai putea sa incerci sa folosesti sort() din stl. Merge mai repede si cred ca asta e optimizarea de care ai tu nevoie.

Nu am rezolvat problema dar in timp nu are cum sa iti intre. Iar wa e normal sa iei pentru ca n<=10^18, deci trebuie sa retii toate numerele prime <= 10^9 si nu prea ai cum sa faci asta. Metoda ta de rezolvare nu e buna. Pentru 0 si 1 raspunsul ar trebui sa fie "NU"

Sau la switch merge un algoritm random. Aparent dupa 20 de operatii determina corect daca are sau nu solutie.S-ar putea sa mearga si cu mai putin.

La problema asta ar merge refacut un test si eventual grupat cu altele. E destul de aiurea sa se ia 100 cu un algoritm similar ciurului. Adica mie mi se pare bulaneala. Beleaua e ca un astfel de algoritm obtine timpi mai buni decat solutia oficiala(cel putin implementarea mea)

Mda mi-am dat si eu seama de asta. Dar daca stii sigur ca elementul ala se afla in vector il poti cauta apoi liniar. Oricum e clar ca nu e o abordare buna )

Nu se poate sa presupui ca sirul e sortat si sa cauti binar ? Adica atat timp cat a[ left ]<=a[ mid ]<=a[ right ] caut binar. Cand conditia nu mai e respectata ma opresc si il caut liniar. Bine ca probabil in cel mai defavorabil caz o sa fie O(n+logn) dar nu se aproximeaza la O(n) ?

Da, trebuie. Gandeste-te ca numarul ala are 10 000 de cifre iar long long poate retine un numar de maxim 18 cifre(aproximativ).

Apropo se putea face fara sa deschizi de 2 ori fisierul ?

La hacker e nevoie de numere mari ?

Cartile de pe pozitiile 2,3,4 sunt cele din mijloc. Sunt 6 posibilitati de a alege ultima carte. Exista 6 permutari pentru o multime cu 3 elemente. Daca le consideram in ordine lexicografica inseamna ca , de exemplu, daca primul formeaza din cele 3 carti a 4-a permutare posibila (in ordine lexicografica) ii indica celui de-al doilea ca trebuie sa alega a 4-a carte in ordine crescatoare.

Daca am inteles eu bine ideea lui Radu Berinde din protocol face parte si regula "avand 2 carti cu valoarea x si y, cu x<y atunci daca y-x e par prima carte pe care o arat e y, altfel x".  In exemplul tau 5-4 e impar deci o sa puna mai intai cartea mica, pe 4. Acum al doilea jucator trebuie sa incerce ambele posibilitati :

1. Diferenta dintre y si x e para, deci cartea aratata e cea mare. Atunci singura carte ramasa ar mai fi 2.

2. Diferenta dintre y si x e impara, deci cartea aratata e cea mica. Atunci mai are posibilitatile 5,7,9,11,13.

In total sunt  6 variante. Iar numarul permutarii celor 3 carti din mijloc probabil ii arata a cata carte e cea ascunsa, considerand sortate toate cele 6 carti posibile in ordine crescatoare.