Afişează mesaje
|
Pagini: 1 ... 4 5 [6] 7 8 ... 13
|
129
|
infoarena - concursuri, probleme, evaluator, articole / Informatica / Arbori indexati binar
|
: Iulie 06, 2011, 17:49:41
|
Imi amintesc ca am citit in liceu despre arbori indexati binar intr-un articol din GInfo. Recent am dat de o problema la care vreau sa implementez structura aceasta de date. Astfel am ajuns sa imi pun urmatoarea intrebare: daca structura respectiva se numeste "arbore", atunci care sunt nodurile arborelui si care sunt relatiile de tata fiu; iar daca acest arbore este cu radacina, care este radacina? Tare sunt curios - daca stiti, va rog, postati. In GInfo nu scrie despre asta. Poate mai facem putina lumina asupra acestei structuri de date si asupra modalitatii de alegere a unui interval.
|
|
|
130
|
infoarena - concursuri, probleme, evaluator, articole / Informatica / Răspuns: Initializare variabila
|
: Iunie 23, 2011, 09:32:15
|
Pe scurt(am schimbat doar indentarea): #include <stdio.h> #include <stdbool.h>
int main(void) {
unsigned long long n, i; bool ok = 1;
(void) scanf("%llu", &n);
if(n % 2) for(i = 3; i * i <= n && ok; i += 2) if(n % i == 0) ok = 0; else ok = (n == 2);
if(ok) printf("DA\n"); else printf("NU\n");
return 0; }
P.S.: Te ajuta sa iti setezi compilatorul sa iti dea toate warning-urile. Cand am compilat codul tau, am primit un warning care imi zicea sa pun braces "{}" ca sa evit un ambiguous else.
|
|
|
131
|
infoarena - concursuri, probleme, evaluator, articole / Informatica / Răspuns: Envelope
|
: Iunie 09, 2011, 14:09:43
|
Dupa o cautare pe google am gasit destul de multe rezultate. Gandeste-te la o multime de curbe(marcate intr-un sistem de coordonate) si ca aceste curbe reprezinta niste ziduri inalte dupa care nu poti vedea nimic. Apoi gandeste-te ca te plimbi pe axa Ox de la minus infinit la plus infinit si te uiti pe o directie paralela cu Oy, sensul inspre y. Toate punctele pe care le vezi formeaza lower envelope. Pentru upper envelope, faci ceva similar pe o dreapta paralela cu oX, aflata undeva la infinit, doar ca de data asta te uiti in jos. Putin formal lower envelope L = { (x,y)|x in R && (x,y) e pe o curba din cele date si y minim } Edit: Si un link: http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Envelope_2/Chapter_main.html
|
|
|
132
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 073 Perechi
|
: Mai 15, 2011, 08:56:44
|
Pentru a afla divizorii unui numar poti face asa: for ( d = 2; d * d <= n; ++ d ){ if ( n % d == 0 ) scrie d si n/d }
Astfel in O(sqrt(n)) putem afla toti divizorii! Totusi atentie la patrate perfecte!(9, 16, ...) Pentru descompunere in factori primi, putem face similar: k = 0; for ( d = 2; d * d <= n; ++ d ){ if ( n%d==0 ){ p [ k ] = d; e [ k ] = 0; k ++;} while ( n % d == 0 ){ e [ k - 1] ++; n/=d; } } if ( n > 1 ){p[k]=n;e[k ]=1;k++;}
|
|
|
139
|
infoarena - concursuri, probleme, evaluator, articole / F11 Competition 2011 / Răspuns: Runda 2
|
: Martie 31, 2011, 14:53:38
|
La problema "Sir" ( Runda a doua, problema a treia ), ce se intampla daca avem k < s? Afisam 0 sau x [ s ] + x [ s - 1 ] + ... + x [ k ] ?
L.E.: Cred ca este gresit putin exemplul la problema Sir. Raspunsul din explicatie difera fata de cel din fisierul de iesire. In explicatie e 10, iar in fisierul de iesire e 16. L.L.E: Cum se adauga un membru unei echipe?
|
|
|
143
|
infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2011 / Răspuns: Feedback Runda 3
|
: Martie 27, 2011, 12:11:27
|
De data asta mi-au placut f mult problemele de la open. Mi se par f interesante, in special problema egal si problema subsir1000. Tare sunt curios cum se facea pb egal. Sper ca are o rezolvare "ad-hoc" si nu una cu ceva structura de date dubioasa.
P.S.: Sunt doar trei runde online anul asta? Eu ma asteptam la 4. Din mesajul de mai sus am inteles ca sunt doar 3.
|
|
|
146
|
infoarena - concursuri, probleme, evaluator, articole / Informatica / Răspuns: Suma cifrelor unui numar
|
: Martie 15, 2011, 22:50:32
|
Ai dreptate, am citit eu putin gresit. M-am gandit la o demonstratie a algoritmului. Pe scurt ar fi cam asa: 10^n da restul 1 modulo 9 pentru orice n numar natural. Fie a un numar natural mai mare ca 0. Atunci a=c0+c1*10^1+...+cn*10^n, iar restul lui a la 9 poate fi scris cam asa a%9=(c0+c1*10^1+...+cn*10^n)%9=(c0+c1+...+cn)%9 De aici putem sa demonstram prin inductie ca cifra de control a lui a da acelasi rest modulo 9 ca si a ( pentru ca suma cifrelor a unui numar este mai mica decat numarul respectiv ).
|
|
|
147
|
infoarena - concursuri, probleme, evaluator, articole / Informatica / Răspuns: Suma cifrelor unui numar
|
: Martie 15, 2011, 20:27:04
|
Pe site-ul dat de Mardare Rares sunt cateva greseli grosolane. Eu nu m-as lua dupa ce scrie acolo in locul vostru. Postul ala da o noua semnificatie a expresiei "algoritm naiv de implementare" a cifrei de control. Adica nu merge. ( Ma refer la algoritmul in O ( 1 ) ). Un simplu contraexemplu este 28.
L.E.: Scuze pentru dezinformare, m-am grabit si am citit modulo 10 in loc de modulo 9.
|
|
|
148
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 1105 Culoar
|
: Martie 10, 2011, 18:25:35
|
Poate cineva sa detalieze cineva solutia la problema asta, va rog, ca eu nu ma prind? ( Sunt foarte slab la capitolul asta ) L.E.: Mai exact m-ar interesa cum aflam cel mai apropiat punct de fiecare dintre cele n^2 drepte. M-am gandit la o sortare a punctelor dupa inaltime, ca mai apoi sa putem cauta binar(si mai apoi cu o optimizare in O(1)) punctul cu inaltimea cea mai mica fata de o dreapta data, dar functia distanta intre o dreapta si un punct nu pastreaza ordinea daca schimbam dreapta.
|
|
|
149
|
infoarena - concursuri, probleme, evaluator, articole / Teme / Răspuns: Problema pascal cls a 10
|
: Februarie 24, 2011, 20:08:12
|
Declari un tablou pentru frecvente pe care il initializezi cu 0. Tabloul trebuie sa aiba indicii de la 0 la 9, deoarece frecv [ i ] va fi frecventa cifrei i. Din n iei pe rand fiecare cifra si ii cresti frecventa cu 1. Cea mai usor de accesat cifra e ultima ( cu n mod 10 ). O data ce ai terminat cu ultima cifra a numarului n, poti sa il imparti pe n la 10(impartire intreaga cu div parca; ceva de genul n = n div 10). Acum ai penultima cifra a numarului n initial pe ultima pozitie a numarului n curent. Ii cresti frecventa si repeti algoritmul, eliminand pe rand ultima cifra din n. Numarul de cifre ale lui n este numarul de pasi facuti inainte de a ajunge la n 0. Trebuie sa descifrezi singur mesajul asta daca vrei sa intelegi problema. Sper sa te ajute.
P.S. Asta e de clasa a 9-a.
|
|
|
|