Rezolvari pentru Etapa 3

Problema 1: Canalizari impotriva inundatiilor
Problema 2: Alegerea pietrelor
Problema 3: Numere


Problema 1: Canalizari impotriva inundatiilor

Se observa ca anumite rauri au un surplus de debit la intrare iar altele au un deficit de debit la intrare fata de debitul maxim admis pe fiecare rau. Se utilizeaza algoritmul pentru determinarea unui flux maxim Ford Fulkerson astfel:

Teste

Evaluarea s-a facut cu un program care pentru fiecare solutie scria mesajul:
      Evaluarea Problemei 'Canalizari impotriva Inundatiilor'
      Programul 'CANALE' al Concurentului 'Autor'

      Test 1 -> Timp 110ms -> O.K. -> Punctaj 3 puncte
      Test 2 -> Timp 110ms -> O.K. -> Punctaj 3 puncte
      Test 3 -> Timp 110ms -> O.K. -> Punctaj 4 puncte
      Test 4 -> Timp 165ms -> O.K. -> Punctaj 4 puncte
      Test 5 -> Timp 110ms -> O.K. -> Punctaj 4 puncte
      Test 6 -> Timp 660ms -> O.K. -> Punctaj 4 puncte
      Test 7 -> Timp 220ms -> O.K. -> Punctaj 4 puncte
      Test 8 -> Timp 110ms -> O.K. -> Punctaj 4 puncte

      Total Punctaj 30 puncte
Observatii:


Problema 2: Alegerea pietrelor

Au existat solutii foarte elegante, bazate pe reprezentarea Fibonacci a numerelor naturale. Schitam succint cateva rezultate, in scopul unei mai bune intelegeri si argumentari a solutiilor.

Definitia 1:

Fie x un numar natural. Definim xk xk-1 ... x1 reprezentarea numarului natural x in sistemul de numeratie Fibonacci astfel:
  1. xi apartine multimii {0, 1} pentru orice i=1, 2, ..., k (se folosesc numai cifrele 0 si 1).
  2. xi+xi+1 < 2, pentru orice i=1, 2, ..., k-1 (nu exista doua cifre 1 consecutive).
  3. x = x1*f1 + x2*f2 + ... + xk*fk, unde f1 = 1, f2 = 2, fi = fi-1 + fi-2, pentru orice i > 2 (f este sirul Fibonacci).
Definitia 2:

Perechea (n, m), n < m se numeste distinsa daca:
  1. reprezentarea Fibonacci a lui n se termina cu un numar par de zerouri.
  2. reprezentarea Fibonacci a lui m se obtine din reprezentarea Fibonacci a lui n prin adaugarea la sfarsit a unui 0.
Exemple:

  1. n=1 ("1") , m=2 ("10")
  2. n=3 ("100"), m=5 ("1000")
  3. n=4 ("101"), m=7 ("1010")
Observatii:

  1. Fiecare numar natural x intra intr-o singura pereche distinsa.
  2. In sirul {m-n | (n,m) pereche distinsa, n<m} fiecare numar natural apare o singura data.
Propozitie:

Daca n si m, numarul de pietre din prima, respectiv cea de a doua gramada nu formeaza o pereche distinsa, atunci primul jucator are strategie sigura de castig (castiga dintr-o singura mutare, sau poate aduce jocul printr-o singura mutare intr-o situatie in care (n, m) formeaza o pereche distinsa).

Demonstratie:

  1. Daca n=m sau n=0 primul jucator castiga dintr-o singura mutare.
  2. Daca 0 < n < m, determinam perechea distinsa (n, p) si perechea distinsa (a, b) astfel incat b - a = m - n.
    • Daca p < m, atunci se poate trece cu o singura mutare de la perechea (n, m) la perechea distinsa (n, p).
    • Daca If p > m, deducem p - n > b - a = m - n, deci perechea distinsa (n, p) este mai mare decat perechea distinsa (a, b), deci p > m, a > n. Deducem n - a = m - b, deci dintr-o singura miscare putem trece la perechea distinsa (a, b).
  3. Daca perechea (n, m) este distinsa, dupa orice miscare ea va inceta sa mai fie distinsa.
  4. Programele concurentilor se bazeaza pe relatia dintre numerele Fibonacci si numarul phi (sectiunea de aur):
    phi = (1 + sqrt( 5 )) / 2 = 1, 6180339887...
    an = trunc(1 + sqrt (5)) / 2)
    bn = trunc(3 + sqrt (5)) / 2).

    Teste

    Exemple de surse frumos realizate (Pascal si C):

    Solutia nr. 1 (Pascal)
    Solutia nr. 2 (C)


    Problema 3: Numere

    Pentru verificarea problemei, deoarece intervalul in care N putea lua valori era foarte mare ([0, 2 000 000 000]), am "nascocit" 20 de teste notate fiecare cu un punct. Au fost surse care au incercat determinarea solutiilor (x, y), folosind structuri repetitive... normal timpul de executie a fost depasit.
    Solutia se baza pe calculul direct pentru x si y, dupa cateva observatii matematice:
          m := trunc ((-1 + sqrt (1+8*n))/2);
          x := n-m*(m+1)/2;
          y := m-n+m*(m+1)/2;
    

    Teste

    Surse frumos realizate:

    Solutia nr. 1 (Pascal)
    Solutia nr. 2 (C)

    Observatii:


    [Enunturile] [Prima etapa] [Etapa anterioara] [Etapa urmatoare] [Ultima etapa] [English] [Inapoi!]

    Inapoi!