Concursul Național de Informatică F11 Competition Regulamentul Secțiunii Algoritmică și Programare

Acest regulament intră în vigoare începând cu runda a doua a etapei de pregătire din cadrul secțiunii.

În cazul unei schimbări de regulament, regulile din cel inițial sunt scrise cu albastru.

Concursul Național de Informatică F11 Competition este organizat, sub egida Universității Alexandru Ioan

Cuza Iași, de către Facultatea de Informatică Iași și Asociația Studenților Informaticieni Ieșeni, în parteneriat cu

Inspectoratul Școlar Județean Iași.

Obiective

În cadrul concursului, se urmărește motivarea studenților și elevilor să:

● dezvolte pasiunea și interesul pentru Informatică și Tehnologia Informației și Comunicării,

● își valorifice, verifice și dezvolte competențele în rezolvarea problemelor folosind calculatorul,

● capete experiență profesională și personală prin schimbul de idei, cunoștințe cu alți participanți cu

interese comune,

● își valorifice abilitățile de prezentare și promovare a proiectelor realizate,

● se pregătească pentru a participa la competiții internaționale de Informatică și TIC.

În cadrul probei de Algoritmică se urmărește dezvoltarea:

● gândirii algoritmice,

● abilităților de programare,

● spiritului competitiv.

Participanți

Participanții se pot grupa în echipe. În fiecare echipă se află minim 1 (un) și maxim 3 (trei) participanți înscriși

în anul 2010-2011 la un liceu sau o facultate, indiferent de naționalitate.

Dacă numărul de persoane de la proba de Algoritmi depășește 15, Comisia își rezervă dreptul de a organiza o

etapă de calificare, în urma căreia se garantează calificarea primelor 5 echipe. Spre deosebire de probele de

Tehnologii Web și Computer Art, la proba de Algoritmică, în etapa de calificare programele echipelor

participante sunt evaluate automat, într-un mod similar evaluării din etapa finală.

Nu pot participa persoanele din organigrama internă a proiectului, și nici angajații unei companii partenere,

dacă respectiva companie a propus o problemă la această secțiune.

Condiții privitoare la statutul de mentor:

● trebuie să aibă împlinită vârsta de 18 ani la data de 27 Mai 2011,

● poate să-i însoțească pe participanți la etapa finală, în cazul calificării,

● nu poate contribui la activitățile echipei în proba Fast Development.

Etape

Competiția constă în trei etape:

● etapa de pregătire, în perioada 1 Martie - 20 Mai,

● etapa de calificare, în perioada 20 Mai - 27 Mai,

● etapa de concurs, în perioada 27 Mai - 31 Mai.

Etapa de pregătire constă în rezolvarea unor seturi de 1-4 probleme publicate în câte 3-5 runde. Fiecare rundă

se desfășoară pe o perioadă de 1-3 săptămâni. Punctajele participanților se cumulează după fiecare rundă.

Etapa de calificare constă în selectarea cel puțin a primelor 5 echipe și se organizează, deoarece numărul total

de participanți la proba de Algoritmică și Programare deja depășește 15.

Etapa de concurs constă în rezolvarea de probleme algoritmice în decursul a 4 ore. O echipă are dreptul la un

număr de calculatoare egal cu numărul de membri.

Comisia își rezervă dreptul să se asigure înainte de etapa de concurs că nu au avut loc tentative de fraudă ale

primelor echipe și să adopte măsuri în cazul în care se constată nereguli.

Înscriere

Etapa de pregătire se desfășoară pe situl concursului F11 Competition. Pentru a participa, orice echipă trebuie

să se înscrie pe site. Atunci când completează formularul de înscriere, echipa trebuie să furnizeze informaţii

corecte şi complete. După înscriere, fiecare echipă va avea un nume de utilizator şi o parolă (pe care le va utiliza

pentru a intra pe site), precum şi un ID, care va fi utilizat la evaluare.

Limbaje

Limbajele de programare admise sunt Pascal, C și C++. Compilatoarele și mediile de lucru necesare rezolvării

problemelor algoritmice vor fi instalate pe discurile stațiilor de lucru. Folosirea de resurse de orice fel, altele

decât cele indicate de Comisia este strict interzisă.

Comisie

Comisia la proba de Algoritmică este formată din:

● coordonatorul Comisiei Concursului,

● coordonatorul Comisiei la secțiunea Algoritmică,

● cadre didactice ale Facultății de Informatică,

● cadre didactice ale liceelor și colegiilor din Iași,

● colaboratori ai Facultății de Informatică,

● reprezentanți ai companiilor partenere Platinum.

Probleme

Problemele variază ca dificultate și se încadrează în programa la Informatică IX-XI.

Enunțurile problemelor respectă un format standard, care include:

● cerința,

● datele de intrare sau modelul de interacțiune pentru problemele interactive,

● datele de ieșire sau modelul de interacțiune pentru problemele interactive,

● minim un exemplu,

● restricțiile de timp,

● restricțiile de spațiu,

● detalii despre structura testelor, unde este cazul.

Pentru fiecare problemă poate fi specificată o limită de memorie. Memoria pentru stivă este utilizată de funcţii

pentru a memora valorile variabilelor locale, ale parametrilor, rezultatul şi adresa de revenire. Memoria totală

disponibilă reprezintă memoria utilizată de program pentru datele statice (de exemplu, variabilele globale),

memoria pentru stivă, memoria pentru variabilele dinamice, precum şi memoria utilizată de program pentru a

memora propriul cod.

Pentru fiecare problemă este specificat un timp maxim de execuţie. Acest timp este specificat pentru evaluarea

pe stația de lucru a concurenților și poate diferi de timpul real, utilizat pe stația de evaluare.

Un model de enunț de problemă este următorul:

Zog

Pe Zog, de unde Excelența Sa, Plenipotențiarul Ambasador TF provine, nu există decât două numere naturale.

Pentru a-și îmbogăți universul, el vrea să știe suma lor. S-a luat decizia ca Excelența Sa, Plenipotențiarul

Ambasador TF și pământenii să comunice prin intermediul unui traducător automat.

Cerinţă

Să se realizeze un program care afișează suma numerelor A și B.

Date de intrare

Programul tău va citi de pe prima linie a fișierului zog.in două numere naturale A și B separate prin spațiu.

Date de ieșire

Programul tău va scrie pe prima linie din fișierul zog.out suma celor două numere citite.

Numărul este urmat de caracterul sfârșit de linie.

Precizări

• 0 ≤ A, B ≤ 105

• Memorie totală: 2MB

• Memorie stivă: 1MB

• Timp execuție: 1s

Exemplu

zog.in zog.out

3 4 7

O problemă propusă conține:

enunț conform specficațiilor,

descrierea soluției,

două sau mai multe surse oficiale, dintre care minim două cu punctaj maxim,

teste de evaluare funcționale în evaluatorul OJI, împreună cu punctajele aferente.

Evaluare

Este recomandat să instalaţi pe calculatorul vostru aceleaşi versiuni pentru compilatoare ca şi cele specificate

în regulament, deoarece există diferenţe între versiuni. Fiţi deosebit de atenţi la fişierele antet utilizate.

Evaluatorul testează dacă programul nu returnează un cod de eroare. Programatorii C şi C++ trebuie să fie

atenţi ca tipul funcţiei main() să fie int şi la sfârşit să returneze 0.

Concurenții sunt invitați să inițializeze variabilele înainte de a le utiliza, să încadreze programele în limitele de

spațiu și timp ale problemei. În caz contrar, nu vor obține puncte pe testele respective.

După terminarea rundei de concurs, participanții vor pregăti rezolvările lor pentru evaluare, conform cu

specificațiile Comisiei. În cadrul rundei de pregătire, se consideră la evaluare ultima sursă trimisă pentru o

anumită problemă.

Participanții la runda de concurs vor salva sursele într-un director specificat de Comisie. La finalul concursului,

în acest director se vor găsi doar sursele, ale căror nume și extensii vor fi scrise cu litere mici.

De exemplu, echipa HAWK33, care lucrează în C++ și rezolvă problemele MAX6, PERMUTARE și JOC, va salva în

directorul specificat 3 surse, cu numele max6.cpp, permutare.cpp și, respectiv, joc.cpp. Convenţia generală este

ca numele tuturor fişierelor care intervin în problemă să se scrie folosind litere mici și cifre, conform cu numele

problemei.

Problemele sunt evaluate în Microsoft Windows cu un program automat, utilizat și la Olimpiada Județeană de

Informatică. Evaluatorul se găsește public la adresa http://www.cnlr.ro/~tucu/Evaluator.rar și este realizat și

întreținut de prof. C. Gălățan. Executabilul echipei concurente este confruntat cu o baterie de teste, ale căror

răspunsuri așteptate sunt calculate sau pe loc calculabile, tot de către un program al Comisiei. Compilatoarele

utilizate se găsesc la adresa http://www.cnlr.ro/~tucu/OJIkit2.exe. Recomandăm verificarea timpilor de

execuție pentru diferite variante de citire/scriere.

Evaluarea se realizează de două ori, de către minim doi membri ai comisiei.

Dacă apar diferențe între punctajele aceleiași echipe pentru aceeași problemă, se consideră punctajul mai mare.

Rezultatele evaluării (sub formă de borderouri pentru fiecare problemă în parte), soluțiile oficiale (atât

indicațiile, cât și sursele optime), testele de evaluare și programele de evaluare sunt publicate după proba

pentru care au fost utilizate pe situl concursului. Recomandăm participanților să testeze propriile programe pe

seturile de teste publicate pe site.

Dacă rezultatele nu coincid cu cele obținute de echipa participantă la testare, sau consideră că unele date de

test nu respectă restricțiile și precizările problemei, participanții sunt invitați să se adreseze prin e-mail sau

formular Comisiei.

Contestații și întrebări

Contestațiile se trimit exclusiv la una din adresele f11@asii.ro sau f11@info.uaic.ro. Contestațiile trimise pe alte

canale, inclusiv dar fără a ne limita la adresele persoanelor din comisie, nu vor fi luate în considerare.

Întrebările se trimit exclusiv la una din adresele f11@asii.ro sau f11@info.uaic.ro precum și la adresa

specificată în enunțul problemei, dacă aceasta este diferită de cele de mai sus.

În mesajele e-mail sau via formular trimise Comisiei, fie ele întrebări sau contestaţii, trebuie să specificaţi clar

ID-ul echipei şi trebuie să utilizaţi un limbaj politicos. În caz contrar, mesajele vor fi ignorate, iar echipa va fi

descalificată. În contestație, echipa trebuie să specifice problema și motivul contestației. Fiecare contestaţie

este analizată de comisie și are ca rezultat un mesaj către echipă.

Se pot trimite întrebări comisiei despre probleme, în primele 7 zile de la publicarea problemei, pentru runda de

pregătire, respectiv în primele 25% minute din timpul alocat rundei finale. Răspunsurile oficiale (la finală) sunt

semnate de un membru al Comisiei și pot fi:

● Da,

● Nu,

● Fără comentarii / No comment.

Contestațiile se pot face în decursul a 3 zile de la publicarea soluțiilor, testelor și rezultatelor pentru fiecare

rundă din etapa de dezvoltare și, respectiv, 6 ore de la publicarea acestora pentru runda finală. Dacă se acceptă

contestaţia, pe sit apare punctajul obținut în urma reevaluării pentru echipa care a depus contestaţia şi, în cazul

în care testele de evaluare sau verificatorul au fost modificate, pentru toţi participanții care au trimis soluții la

respectiva problemă. Va fi publicat pe sit şi un anunţ general în acest sens.

Rezultate

Fiecare participant are asociat un cod ce reprezintă anul de studiu în care se află:

● un punctaj între 9 și 12 pentru elevi (clasa a XIII-a se consideră clasa a XII-a),

● un punctaj între 13 și 18 pentru studenți.

Fiecare echipă are asociat un cod ce reprezintă suma codurilor participanților. Codul unei echipe pentru proba

de Algoritmică poate lua valori cuprinse între 9 și 45. De exemplu, un elev de clasa a XI-a, unul de clasa a XIII-a,

un student în anul I și unul în anul al IV-lea fomează o echipă cu suma 11+12+13+16=52.

Ordonarea echipelor pentru clasamentul de calificare la runda finală ține cont, în această ordine, de:

● rezultatul din etapa de pregătire (descrescător), urmat de

● codificarea echipei (crescător), urmată de

● vârsta celui mai mic participant (crescător).

Ordonarea echipelor pentru clasamentul de premiere în runda finală ține cont, în această ordine, de:

● rezultatul din etapa finală (descrescător), urmat de

● penalizările de submisie a problemelor (crescător), urmate de

● rezultatul din etapa de pregătire (descrescător), urmat de

● codificarea echipei (crescător), urmată de

● vârsta celui mai mic participant (crescător).

În acest mod, se asigură unicitatea rezultatelor și se pot stabili de la început procentele din totalul disponibil. În

comun acord cu partenerii, se pot stabili premii speciale, dar nu mai târziu de festivitatea de premiere. Fiecare

concurent va primi o diplomă de participare. Premiile vor fi oferite în cadrul festivității de premiere.

Premiile obținute sunt:

● Premiul I: 45% din totalul disponibil,

● Premiul al II – lea: 25% din totalul disponibil,

● Premiul al III – lea: 15% din totalul disponibil,

● Mențiunea I: 10% din totalul disponibil,

● Mențiunea a II – a: 5% din totalul disponibil.

Laboratoare

În sălile de concurs se găsesc câte un calculator pentru fiecare concurent și un ceas vizibil. Se vor oferi

instrumente de scris și hârtii albe. Concurenții nu pot folosi:

● calculatoare, inclusiv cele programabile,

● secvențe de cod anterioare,

● suporturi de stocare externe, discuri,

● dispozitive de comunicare, inclusiv telefoane mobile,

● materiale imprimate, altele decât cele oferite de comisie.

Stațiile de lucru beneficiază de aceeași configurație și au instalat Microsoft Windows, împreună cu:

● Microsoft Visual Studio Professional Edition,

● Compilatoarele GCC, G++, FreePascal.

Configurația exactă va fi comunicată în prealabil participanților calificați în finală.

Descalificare

O echipă care:

● interferează cu activitățile altor participanți (inclusiv electronic),

● atacă stațiile de lucru sau comisia științifică (inclusiv electronic),

● instigă la fraudă prin orice mijloc (inclusiv electronic)

● accesează rețeaua, realizează fork,

● creează alte fișiere decât cele specificate,

● atacă securitatea sistemului sau evaluatorul,

● execută alte programe,

● schimbă permisiuni de fișiere,

● citește informații despre sistem,

● încalcă în alt fel regulamentul

va fi descalificată fără drept de contestație.

Coordonatorii concursului își rezervă dreptul de a descalifica fără notificare prealabilă și fără drept de

contestație participanții aflați în situație de descalificare. Pentru a descalifica o echipă, este necesar acordul

ambilor coordonatori. Echipele descalificate vor primi un mesaj cu motivul concret al descalificării.

Echipele disjuncte care au surse duplicat sunt marcate în clasament, iar punctajul lor pentru întreaga rundă se

anulează. Echipele în respectiva situație au obligația de a contesta acest fapt. În cazul în care duplicatele se

repetă într-o rundă ulterioară, echipa este descalificată fără drept de contestație.

Regulament

Coordonatorii concursului își rezervă dreptul de a modifica fără notificare prealabilă acest regulament.

Citire | Scriere

Pentru începătorii în programare, poate că este util un exemplu de utilizare a fişierelor pentru citirea/scrierea unui număr întreg.

Recomandăm participanților să compare timpii de execuție pentru citirea/scrierea unor seturi de date de dimensiuni mari, pentru a se încadra în timp.

Începând cu runda a doua, comisia își rezervă dreptul de a nu aproba contestații pe motivul depășirii timpului de execuție din enunț din cauza citirii.

Limbajul C

#include <stdio.h>

...

/* declară şi deschide fişierul de intrare */

FILE * fin=fopen("input_file_name", "r");

/* citeste un intreg în variabila n */

fscanf (fin, "%d", &n);

/* inchide fişierul de intrare */

fclose(fin);

...

/* declară şi deschide fişierul de ieşire */

FILE * fout=fopen("output_file_name", "w");

/* scrie o linie care conţine valoarea variabilei n */

fprintf (fout, "%d\n", n);

/* inchide fişierul de iesire */

fclose(fout);

Limbajul C++

#include <fstream.h>

...

/* declară şi deschide fişierul de intrare */

ifstream fin("input_file_name");

/* citeste un intreg în variabila n */

fin >> n;

/* închide fişierul de intrare */

fin.close();

...

/* declara şi deschide fişierul de iesire */

ofstream fout("output_file_name");

/* scrie o linie care conţine valoarea variabilei n */

fout<<n<<'\n';

/* închide fişierul de iesire */

fout.close();

Limbajul Pascal

{ declară fisierele de intrare şi de iesire }

fin, fout: text;

...

{ asignează variabila fin fişierului de intrare }

assign(fin,'input_file_name');

{ deschide fişierul de intrare }

reset(fin);

{ citeşte un întreg în variabila n }

read(fin,n);

{ închide fişierul de intrare }

close(fin);

...

{ asignează variabila fout fişierului de iesire }

assign(fout,'output_file_name');

{ deschide fişierul de iesire }

rewrite(fout);

{ scrie o linie care conţine valoarea variabilei n }

writeln(fout, n);

{ închide fişierul de iesire }

close(fout);