Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-04-09 09:54:15.
Revizia anterioară Revizia următoare

Sandbox (cutiuţa cu năsip)

$\underbrace{0,0,\ldots,0}_{text}$
$\frac{m_0}{2^2}$

Vrei sa stii ce fac membrii infoarenei chiar acum ?

nume	varsta	judet
Popescu	24	Bucuresti
Ionescu	12	Constanta

nume	varsta	judet	nume	varsta	judet	nume	varsta	judet
Popescu	24	Bucuresti	Popescu	24	Bucuresti	Popescu	24	Bucuresti
Ionescu	12	Constanta	Popescu	24	Bucuresti	Popescu	24	Bucuresti

log me

LaTeX pe mai multe rânduri:
$\begin{array}{rcl} f: R^3 & \to & R \ (x,y,z) & \to & x + y + z \ f(x,y,z) & = & x + y + z \end{array}$

sau:
$\begin{array} {lcl} f(x) & = & (a+b)^2 \ & = & a^2+2ab+b^2 \end{array}$

Tabel mic:

A	B	A->B
0	2	3

Tabel mare:

A	B	A->B
1	2	3

Tabel si mai mare:

A	B	A->B
1	2	3

Diacritice:

Straşnic de îngâmfat, ţăranul crapă streaşina.
Straşnic de îngâmfat, ţăranul crapă streaşina.

In Windows XP sp2 cu IE6 fara update de font se vede asa:

Ordered list:

1st item
2nd item

Use only F/OSS, Microsft sucks ;) just because I say so.

Love Linux, beacuse I say so.

However, on a GNU system NEVER type <b>sudo make me sandwich</b> , and expect the results...

$2^n * 2^n$
Vivi's blog
$d/(2\"a)=d/(2\Omega^2)$
* $d = \sqrt{(c_{2}-c_{1})^{2} + 1 }$
p. $\displaystyle \sigma_{\lambda} = \frac{24 \pi^3}{\lambda^4 N^2} \left(\frac{n^2-1}{n^2+2}\right)^{\!2}$

Avem suport pentru $\LaTeX$ !

$\frac{a^2 - b^2}{a + b} = a - b$
$n! \approx \sqrt{2 \pi n} (\frac n e) ^n$

Acest articol a fost adăugat de

Mircea Pasoi •domino
Intră aici dacă doreşti să scrii articole sau află cum te poţi implica în celelalte proiecte infoarena!

| test | test |

User macro bug

Worship me

Feel free to plghay around, but Big Brother is watching you.

codetest

What does this button do?

lalallaa

Intrebare: cum poti seta culoarea cu care scrii?
Uite asa: scris cu rosu

Siteul sub IE 7 -- vezi pagina dedicata

Siteul sub FF 2 - ~~mica problema panoul de 'editeaza', 'vezi istoria', 'sterge' etc (in IE7 panoul nu se suprapune)~~

[test]
OMG test, good work people :D
Acuma doar trebuie putin stimulata comunitatea
[/test]

Interesting choice of words.
a very bold MAN
CAPSOMANII-I DESPISE THEM

gasise pe-un teren viran,
un geamantan.

si-n geamantan,
un pachet.

si in pachet,
un pachetel gasise el.

si-n pachetel,
alt pachetel.

si-un pachetel in pachetel,
legat cu funde elegante.

si-n pachetel...vreo 40 de diamante...
...
Adio voi...va las si plec fiindca mi-e dor...
si a plecat Apolodor
!!!<>

tralalala blablabla lala

salut, aici poate sa scrie oricine ce vrea? _Robert

1	2	3
unu	doi	trei
1... unu	2... doi	3... trei

Moraru Ionut has been here. :))
shnako was here :)

:) gosh...

inca unul, de tipul cel mai heyyyyyyyyyy prost din corcodus, se joaca cu in nisip.. ura ...
cel mai prost din corcodus a terminat... altcineva?:D
tot el: atentie fratilor ne urmareste big brother 3 (sau 4)
Care imi da o lopata ? :)

// comentariu
#include <cstdio> // comment1
// comment2

int main()
{
    return 0;
}

Eu vreau să scriu cu ŢŢŢŢŢ dublu ţ mic şi tripul Ţ mare! Iată un Ţ ţŢŞ

Imaginile trebuie neaparat sa fie atasamente ale unei pagini.

Link

Latura 1	Latura 2	Latura 3	Latura 4	Latura 2	Latura 3	Latura 1
0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0	0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0	0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0	0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0	0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0

&6 7 8&
# Hello
## Hello 2
### Hello 3

Subsir 2

(problema grea clasa a 9a, problema medie clasa a 10a, problema usoara clasele 11-12)

Problema poate fi considerata asemanatoare cu cea a celui mai lung subsir crescator, avand o rezolvare similara de complexitatea O(N²) folosind metoda programarii dinamice.

Se vor construi doi vectori:

A_i = lungimea celui mai scurt subsir crescator maximal care incepe cu pozitia i
T_i = urmatorul element dupa pozitia i in cel mai scurt subsir crescator maximal care incepe cu i (pentru reconstiutire)

Pentru fiecare i, se va cauta un j > i astfel incat V_i ≤ V_j (unde V este vectorul de numere) si se alege acela cu A_j minim, A_i devenind A_j+1, iar T_i devine j. Daca nu exista nici un j, A_i se initializeaza cu 1 si T_i cu i.

Ca sirul construit sa fie maximal trebuie ca atunci cand verificam j-urile pentru un i fixat, j-ul respectiv sa fie "dominant", in sensul ca sa nu existe un i < k < j astfel incat V_i ≤ V_k ≤ V_j, deoarece sirul construit cu primul element in i si al doilea in j ar putea fi extins inserand k intre i si j. Verificarea pentru acest k se poate face in O(N), obtinand o solutie O(N³) care ar fi adus 50-60p. Pentru a face verificarea in O(1), facem observatia ca ne intereseaza doar acel V_k minim care este ≥ V_i. Pe masura ce se avanseaza cu variabila j, se pastreaza o variabila min, reprezentand minimul dintre valorile V_j parcurse pana acum, care sunt ≥ V_i.

Astfel, cand se ajunge la un j, se verifica inainte daca V_j < min (conditie necesara pentru a construi un sir maximal). Un ultim detaliu in solutie este obtinerea solutiei minime din punct de vedere lexicografic. Cand se selecteaza j-ul pentru fiecare i, pe langa faptul ca se alege acela cu A_j minim, in caz de egalitate se va alege acela cu valoarea V_j minima. Selectarea este corecta deoarece nu vor exista j1, j2 cu A_j1 si A_j2 minim , iar V_j1 = V_j2.
Problema se poate rezolva mai bine intr-o complexitate O(N*lg² N) folosind structuri de date avansate, astfel transformandu-se intr-o problema de clasele 11-12 grea, sau chiar o problema de finala. Lasam aceasta rezolvare ca exercitiu pentru cititor.

Sum

(problema usoara, clasa a 10a)

Vom face o prima observatie:

(n, d) = 1 <=> (n, n - d) = 1, (n, n + d) = 1

Fie a = phi (n), indicatorul lui Euler. Fie b numarul de numere prime cu n cuprinse intre n si 2 * n.
Deoarece (n, d) = 1 <=> (n, n + d) = 1, a ≤ b. Deoarece (n, d) = 1 <=> (n, n - d) = 1, b ≤ a => b = a. Fie x₁, x₂, .. x_a numerele < n si prime cu n => numerele cuprinse intre n si 2 * n si prime cu n vor fi x₁ + n, x₂ + n, .. x_a + n.

Conform observatiei facute, (n, n - x₁) = 1, (n, n - x₂) = 1, .. (n, n - x_a) = 1 =>

x_a = n - x₁ <=> x₁ + x_a = n
x_a-1 = n - x₂ <=> x₂ + x_a-1 = n
...
x₁ = n - x_a <=> x_a + x₁ = n

Fie S1 suma numerelor prime cu n si mai mici ca n, fie S2 suma numerelor prime cu n, cuprinse intre n si 2 * n.
Adunand cele a egalitati, obtinem 2 * S1 = a * n => S1 = (a * n) / 2.

S2 = a * n + S1 => S1 + S2 = 2 * a * n.

Se foloseste o singura data ciurul lui Erathostene pentru a determina functia phi pentru toate intrebarile. Se poate consulta articolul despre cirulul lui Erathostene.

Pavare 2

(problema grea, clasa a 10a)

Problema se rezolva cu programare dinamica. Utilizam urmatoare structura de date:

V[i][j][0] = numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie albe
V[i][j][1] = numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie negre

Relatiile de recurenta sunt acum usor de dedus. Odata calculata matricea putem raspunde foarte usor primei cerinte, facand suma V[N][i][0] (pentru 1 ≤ i ≤ A) si V[N][i][1] pentru (1 ≤ i ≤ B).

Pentru a 2-a cerinta incercam sa construim a K-a secventa lexicografica de la inceput catre sfarsit. Astfel, la fiecare pas incercam sa punem o segventa de tipul '0...01' care sa contina un numar maxim de '0'. Daca la pasul curent nu putem pune nici un '0' atunci vom pune o secventa de tipul '1..1' care sa contina un numar minim de 1. Numarul de '0'-uri sau de '1' pe care il punem il vom calcula cu ajutorul matricei precalculate la prima cerinta. Astfel, daca putem pune p de '0' inseamna ca numarul de posibilitati pentru a completa restul solutiei daca punem cel putin p de '0' la inceput este mai mare sau egal cu K. Alegem cel mai mare numar p cu proprietatea de mai sus. Daca p nu exista, incercam sa punem cat mai putini '1' in aceeasi maniera. Continuam apoi cu restul secventei, iar din K scadem numarul de solutii peste care am "sarit".

Tare de tot acest sandbox :)

Editorial MScex_s1

http://www.infoarena.ro/problema/cifra

Rezolvarea de 100 era una mai putin "ortodoxa". La astfel de probleme de obicei incerci brutul si
te bazezi pe niste observatii. Observatia era ca rezultatul cerut se repeta din 100 in 100. Astfel
cu o preprocesare puteam calcula cele 100 valori si erau necesare doar ultimele 2 cifre ale celor
T numere. Complexitate era O(T*L) supraestimat , unde L e lungimea maxima a unui query.

http://www.infoarena.ro/problema/prim

Numarul cerut de problema va fi al K+1-lea numar prim. Cu un ciur cu marime rezonabila ( 2 000 000 ) se poate determina in O(Marime_ciur log log Marime_ciur) ( complexitate aproape liniara ) al K+1-lea numar prim. Alte solutii in complexitati mai mari ( gen O(N sqrt N) ) puteau lua ceva puncte.

http://www.infoarena.ro/problema/fact

Problema asta a fost aleasa ca sa fie cea mai grea din set. Nu necesita decat cunostiinte elementare si e abordabila pentru un incepator de clasa a 9-a care stie cautare binara.

Asadar , problema poate fi rezolvata daca o descompunem in 2 subprobleme. Pentru un numar fixat N cate 0-uri are factorialul acestuia. Un 0 apare de fiecare data cand apare un factor de 2 si un factor de 5 in descompunerea lui N! . Observatia care ne va ajuta mult este ca un factor de 5 apare mult mai rar decat unul de 2 , deci numarul de 0-uri este determinat de numarul de factori de 5 din descompunerea numarului.

Pentru un N fixat putem numara numerele divizibile cu 5 din N! , lucru care este usor de intuit ca e N/5. Dar ce facem cu numerele care au mai multi factori de 5 in decompunere ? ( gen 50 , 125 ) La fel de usor de intuit e ca numarul de factori de 5 va fi N/5 + N/(5^2) + ...

Acum avem pentru un numar N fixat numarul de 0-uri din descompunerea lui. Numarul cu P zerouri poate fi cautat binar. Complexitate finala va fi astfel
O( log^2 N ).

infoarena informatica de performanta