Pai nu il folosesc la ONI, il am proiect la faculatate ( sunt in anul I ).
Algoritmul e prezentat si in Knuth. Eram curios doar sa vad si o alta implementare ca sa o imbunatatesc pe a mea . Daca e cazul...  

Stie cineva  algoritumul lui Clark A. Crane de spargere si concatenare de arbori AVL?  :cry:

Unde gasesc informatii despre probleme standard de knapsack (problema rucsacului)? Un link mi-ar fi de mare ajutor!!! va multumesc

Ai tratat cazul cand nu exista solutie?

Adica (pentru exemplul din enunt) daca afisezi "1 2 3" iei 0 puncte pentru ca din sirul "1 2 3" Haralambie ar fi obtinut "3 4 5", si nu "4 5 3" cum ti se da din fisierul de intrare.

A rezolvat cineva problema asta cu programare dinamica?

Am folosit faptul ca un punct este interior unui poligon numai daca dreapta paralela cu Ox care il contine intersecteaza intr-un numar impar de ori laturile poligonului la dreapta punctului.
Am luat numai 60 de puncte pentru ca am depasit timpul de executie.
Exista o alta metoda de rezolvare, mult mai eficienta? Sau trebuie sa-mi imbunatatesc algoritmul?

Si o intrebare pentru organizatori: dupa cat timp este oprit un executabil dupa ce a depasit timpul de executie? Daca in "Monitorul de evaluare" am la un test timp de executie "0.31s" pentru o problema care admite numai 0.2 sec, inseamna ca programul meu s-a oprit dupa 0.31 sec sau ca evaluatorul la oprit fortat?

In articolul cu solutiile pentru runda #2 cls XI-XII era mentionata o tehnica de programare numita "Rotating Calipers" (http://cgm.cs.mcgill.ca/~orm/rotcal.html ).
Articolul este deosebit de interesant dar nu am avut nici o idee buna ca sa pot sa-l implementez. A incercat cineva sa foloseasca aceasta tehnica pentru problema "Rubarba" sau pentru alte probleme care accepta o astfel de rezolvare? Am mare nevoie de ajutor. ( de fapt, nu stiu cum sa compar 2 unghiuri determinate fiecare de cate 2 drepte).

Intrebare pentru autorii solutiei sau pentru oricine a citit articolul cu solutiile la runda #2 :
    Cum generez "toate numerele x < 1000, produs de numere prime distincte" ? Daca nu ma insel, asta inseamna toate submultimile multimii P = { x  | x<100 si x prim } care au produsul elementelor mai mic decat o mie.
Dar card(P) = 170 si ar veni cam 2^170 de combinatii! Cum separ din toate submultimile lui P numai pe cele cu produsul mai mic decat 1000. Backtracking? Sau exista ceva mai eficient?

Am implementat un algoritm dar nu am reusit sa iau decat 10 puncte.
   In principiu, am cautat sa aflu unde ar trebui sa fie asezat terenul pe orizontala si pe verticala.
    Prima data am sortat abscisele punctelor. Am luat o dreapta in punctul cu abscisa cea mai mica si unul in capatul celalat si m-am apropiat cu dreptele una de cealalta pana distanta dintre ele este DX.  
   La fel am procedat si pentru verticala.
    Dupa care, avand  coordonatele terenului, calculez distanta pana la fiecare punct din exteriorul sau.

   Unde am gresit?

   Voi cum ati rezolvat problema?

Va multumesc!!!

Am rezolvat problema asta in 2 moduri.

I. Am folosit, ma rog, relatii matematice acolo.... si am facut un algoritm cat de cat eficient pentru care am luat 90 de puncte.

II. Am observat ca pot sa preprocesez solutiile si sa le pun intr-o matrice de 10x10.
    Programul meu arata cam in felul urmator:

deschide fisiere

pentru i = 1 la T
   citeste o valoare
   afiseaza a[penultimacifra][ultimacifra].
sfarsit pentru

inchide fisierele


Cu toate ca al doilea program avea 10 randuri si face de cel putin vreo 10 ori mai putine operatii, am obtinut 80 de puncte. ( timpul de executie a fost depasit pentru ultimele teste).

Am tot auzit de "linia de cache" peste tot pe forum si vreau sa stiu daca asta este problema si in cazul meu. Si chiar daca nu este, vreau ceva informatii despre linia de cache si cum putem evita problemele legate de ea.

Va multumesc!!!

Am cautat dar nu am auzit sa fi cercetat Pitagora sau altcineva cati copaci intra intr-un triunghi oarecare.
Am descoperit totusi ceva intre cmmdc si triunghiul dreptunghic ( atatea indicii am primit).
Si anume: numarul punctelor de coordonate intregi din interiorul unui triunghi cu varfurile de asemenea de coordonate intregi este:
[ (a-i)(b-1) - cmmdc(a, b) + 1]/2. Mi se pare chiar foarte corecta formula si nu cred ca e greu de gasit. Adica intru-un dreptunghi sunt (a - 1)(b - 1) puncte de coordonate intregi iar intr-un triunghi dreptunghic sunt  cam jumatate ( pentru ca scadem  numarul de puncte de pe diagonala dreptunghiului care au coordonate intregi).
Nu?
Se poate generaliza si la un triunghi oarecare daca este nevoie ( il incadrez intr-un dreptungi si scad punctele din cele 3 triunghiuri dreptunghice care apar).
Asa... si daca asta este formula pe care mi-ai cerut-o, atunci ce fac mai departe?

Mi-e nu imi plac grafurile de nici o culoare si nu prea am lucrat astfel de probleme pana acum.
Cum fac sa memorez grafuri de dimensiuni foarte mari? (ex. 100 000 de noduri, ca in problema "cerere").

Si nu am inteles solutia comisiei. Dupa cate am inteles eu din grafuri, parcurgerea in adancime pentru exemplul din problema este : 1 2 3 4 5 6 7 9 10 8. Stramosul lui 6 este p[6-1] = p[5] = 5 ( FALS).

Ce complexitate are solutia comisiei?

Imi da cineva si mie o indicatie?

Elementele subsirului sunt distincte 2 cate 2?

Cine imi spune mie cum merge exact algoritmul care verifica daca un punct apartine interiorului unui poligon oarecare?
    Daca numar toate punctele de intersectie de la dreapta punctului cu laturile poligonului imi da, dar ce se intampla daca dreapta intersecteaza un varf al poligonului?


    Si sa imi spuneti si mie daca acest algoritm s-ar putea adapta pentru aceasta problema. (Din punct de vedere al timpului de executie, pentru ca banuiesc ca altfel nu ar fi probleme).


Multumesc mult!!!

Unde gasesc o lista cu tipurile de date din gcc? Am nevoie de o structura de date pe 64 de biti.

Imi spune si mie cineva unde gasesc articolul asta de care vorbiti voi?

Va multumesc, am rezolvat problema si am luat 100p. Formula era buna dar am gresit la

implementarea adunarii numerelor. Era un caz particular si de-aia nu m-am prins repede unde

am gresit.

Problema mea este la ONI.

Eu am DJGPP. L-am si folosit pentru cele 2 probleme pe care le-am mentionat. Nici nu am mai

alocat dinamic pentru ca in GNU am putut declara un tablou de 200X500. Dar la ONI eu voi

lucra in Windows si nu cred ca au ei DJGPP instalat pe calculatoarele unde o sa stau eu. Si

chiar daca evaluarea se face in GNU, imi vine cam greu sa dau o sursa care pe BC++ 3.1 nu

se compileaza, sperand ca va merge in GNU.
 
Si, cum fac sa initializez un tablou cu 0 in GNU? Daca folosesc "memset" imi da eroare.

Mai stiu de la ONI de anii trecuti ca "stdlib.h" nu merge sub linux. Dar am compilat o

sursa in GNU si mi-a cerut sa includ stdlib ca sa pot folosi functia abs. Unde pot gasi o

lista cu ce header-e sa folosesc in gnu?

Poate ma ajuta cineva care a luat maxim la problema asta.

Am rulat cateva teste:
1. N=13; K=8; Am obtinut sol = 1095154;
2. N=17; K=4; Am obtinut sol = 87077748875904;
2. N=70; K=45; Am obtinut
 sol = 26269688897329413126924403900781315211553781164470;

Va da si voua la fel?

[12.15 Demonstrati ca numarul permutarilor p ale multimii {1,2,...,n} care au proprietatea ca exista exact k elemente j pentru care p(j)>p(i) pentru orice i<j este egal cu |s(n,k)|.]

Am sa raspund la toate mesajele:
1. am implementat operatii pe numere mari de pana la 500 de cifre

(iar din calculele mele cel mai mare numar se obtine pentru 200 si 2 sau 200 si 3 si nu are decat 370 si ceva de cifre, un pic mai mult decat 200!).
2. folosesc primul numar al lui stirling, primesc "Wrong answer"

iar tmpul de executie este sub 0.05 sec (pt N=200).
3. pt Bogdan2412: ce ai gasit tu este nr lui Stirling de speta a

doua, care este cu totul altceva. Si am inteles bine problema. Pt n = 5, obtin 24, 50, 35 (ca in exemplul din problema), 10 si 1. Nu-i asa?

Acesta e textul problemei din "Probleme de combinatorica si teoria
grafurilor":
12.15 Demonstrati ca numarul permutarilor p ale multimii {1,2,...,n} care au proprietatea ca exista exact k elemente j pentru care p(j)>p(i) pentru orice i<j este egal cu |s(n,k)|.


|s(n,k)| numarul lui Stirling de speta intai si este egal cu coeficientul lui x^k din dezvoltarea: x(x+1)(x+2)...(x+n-1).


Daca doreste cineva am sa pun pe forum si demonstratia lui Ioan Tomescu.

[De ce?]

Am demonstrat ca rezultatul este de fapt numarul lui Stirling

de speta intai |s(N,K)|, unde N si K sunt numerele din problema.

Am determinat s(N,K) cu formula de recurenta:
s(N,K) = (N-1)s(N-1,K) + s(N-1, K-1).
   Desi atat formula cat si calcularea ei recursiva mi se par

corecte ( sunt demonstrate in "Probleme de combinatorica si teoria

grafurilor" de Ioan Tomescu, Editura Didactica si Pedagogica,

1981, pag. 51) sursa mea este evaluata la 10 puncte.
  De ce?

[Cum sa procedez ca sa pot aloca tablouri mari in memorie???]

Am nevoie de niste informatii referitoare la alocarea dinamica in C++.
Lucrez in Borland  C++ 3.1 si am rezolvat 2 probleme propuse pe Infoarena. Solutiile sunt pe baza de formule de calcul usor de implementat si care ofera rezultatul aproape instantaneu.
Problema este ca am nevoie de tablouri de dimensiuni mari.
Ex.   int   a[200][400];

O astfel de declarare produce eroare la compilare : "Array size to large".

Am incercat sa aloc dinamic in felul urmator:
===================================
int   *a[200];

for(i=0; i<200; i++)
   a = new int[400];
===================================

Operatia decurge cu succes dar pentru numere mari apar diferite neajunsuri:
Exemple:
1. valorile unor variabile se modifica nejustificat;
2. obtin erori de tipul : "Null pointer assignment";
3. se inchide Borland C++ brusc;


Am incercat sa folosesc si "malloc":
========================================================
int   *p;

if( (p = (int*) malloc(NMax)) == NULL )
      printf("Not enough memory to allocate buffer\n");
========================================================

Aceleasi rezultate le-am obtinut si cu aceasta implementare iar la alocarea tablourilor mesajul "Not enough memory to allocate buffer" aparea pe ecran de mai multe ori.



Cum sa procedez ca sa pot aloca tablouri mari in memorie???

(Am marit si heap-ul dar nu am observat nici o imbunatatire).