Rezolvari pentru Etapa 6

Problema 1: Nunta
Problema 2: Coeficientii polinomului cu valoare maxima
Problema 3: Exponentul cu bucluc


Problema 1: Nunta

  1. Programele au fost verificate pe 8 teste, acordandu-se respectiv: 2, 4, 3, 1, 8, 7, 1, 4 puncte:
    • T1 - exemplul din problema
    • T2 - test mediu (1/5 din maxim)
    • T3 - test mic 2 mese
    • T4 - test mic 2 mese gata aranjate
    • T5 - test maxim perechi si mese
    • T6 - test maxim perechi, mese putine
    • T7 - test fara solutie
    • T8 - test mediu (2/5 din maxim)
    Solutiile NUNTA1.OUT, ..., NUNTA8.OUT nu sunt unice!!!
    Validarea solutiei s-a facut cu un program care porneste de la fisierul initial si efectueaza mutarile indicate de solutia furnizata in fisierul concurentului; daca in final mesele sunt aranjate si numarul de mutari este corect, solutia este validata.
  2. O singura lucrare (Ileana Ioana) a trecut toate testele. Remarcabil este modul de abordare: doua variante de rezolvare, in acelasi program, dand, eventual, doua solutii diferite; solutia minima era cea furnizata la iesire; tot la aceasta lucrare merita remarcat timpul de lucru: chiar rulat pe 386SX/20MHz, programul furnizeaza solutia aproape instantaneu; rezultatele furnizate de evaluator pe 386:
          PROGRAMUL D-rei. ILEANA IOANA:
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
          TESTUL 1
          Programul ruleaza ...
          Timp de executie : 0.10 secunde
          Se analizeaza fisierul de iesire ...
          FISIER CORECT
          DA
          3-3
          TESTUL 2
          Programul ruleaza ...
          Timp de executie : 0.38 secunde
          Se analizeaza fisierul de iesire ...
          FISIER CORECT
          DA
          204-204
          TESTUL 3
          Programul ruleaza ...
          Timp de executie : 0.16 secunde
          Se analizeaza fisierul de iesire ...
          FISIER CORECT
          DA
          16-16
          TESTUL 4
          Programul ruleaza ...
          Timp de executie : 0.16 secunde
          Se analizeaza fisierul de iesire ...
          FISIER CORECT
          DA
          0-0
          TESTUL 5
          Programul ruleaza ...
          Timp de executie : 1.70 secunde
          Se analizeaza fisierul de iesire ...
          FISIER CORECT
          DA
          1365-1365
          TESTUL 6
          Programul ruleaza ...
          Timp de executie : 1.37 secunde
          Se analizeaza fisierul de iesire ...
          FISIER CORECT
          DA
          1013-1013
          TESTUL 7
          Programul ruleaza ...
          Timp de executie : 0.10 secunde
          Se analizeaza fisierul de iesire ...
          DA
          TESTUL 8
          Programul ruleaza ...
          Timp de executie : 0.71 secunde
          Se analizeaza fisierul de iesire ...
          FISIER CORECT
          DA
          455-455
    
  3. Nici o sursa in CPP nu a fost competitiva, unele ducand la blocarea sistemului indiferent de test.
  4. Consideram lipsa de respect fata de ceilalti concurenti, ca si fata de eforturile organizatorilor EIC, lucrarea concurentului:
    
      >> Program wedding;
      >> Begin
      >>      assign(output,'nunta.out');
      >>      rewrite(output);
      >>      Writeln (output,'NU EXISTA SOLUTIE');
      >> end.
    
    In aceeasi categorie intra si alte lucrari.
  5. Fisiere de intrare: 1 2 3 4 5 6 7 8
    Fisiere de iesire: 1 2 3 4 5 6 7 8

    Iata solutia care a realizat cerintele problemei:

    Solutia nr. 1 (Pascal)


    Problema 2: Coeficientii polinomului cu valoare maxima

    Descrierea algoritmului:

            Notam cu b = ( b[0], b[1], ..., b[n])
      sirul cu coeficientii polinomului P(X) in ordinea care realizeaza
      maximul P(x), pentru x dat.
            Se ordoneaza crescator sirul a, obtinand
            a[0] <= a[1] <= ... <= a[n].
    

    Distingem cazurile:

    1) x > 1
       Maximul global P(x) este dat de maximul local pentru fiecare termen
       a[i]*x^i. Deci:
    
       b[0] := a[0], b[1] := a[1], . . . , b[n] := a[n].
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    
    2) x = 1
       Nu are importanta ordinea elementelor, deci putem lua spre exemplu:
       b[0] := a[0], b[1] := a[1], . . . , b[n] := a[n].
    
    
    3) 0 < x < 1
       Din 1 > x > x^2 > x^3 >... > x^n, rezulta:
       b[0] := a[n], b[1] := a[n-1], . . . , b[n] := a[0].
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    
    4) x = 0
       Valoare lui P(x) este b[0], deci:
       b[0] := max{ a[0], a[1], . . . , a[n] } adica:
       b[0] := a[n], ordinea celorlalti termeni nu mai are importanta.
       ^^^^^^^^^^^^
    
    5) -1 < x < 0
       Obtinem:
       x < x^3 < x^5 < ... < 0  si
       1 > x^2 > x^4 >... .
       In acest caz sirul b se construieste astfel:
       b[1] := a[0],            b[0] := a[n]
       ^^^^^^^^^^^^             ^^^^^^^^^^^^
       b[3] := a[1],            b[2] := a[n-1]
       ^^^^^^^^^^^^             ^^^^^^^^^^^^^^
       ...                      ...
    
       b[2*k+1] := a[k]         b[2*k] := a[n-k]
       ^^^^^^^^^^^^^^^^         ^^^^^^^^^^^^^^^^
    6) x = -1
       Exista mai multe variante pentru sirul b.
       Una dintre ele ele este spre exemplu  cea de la punctul 5) explicat mai sus.
    
    7) x < -1
       Obtinem:
       -1 > x > x^3 > x^5 > ...  si
        1 < x^2 < x^4 <....
        Tinand seama de aceste inegalitati se construieste sirul b.
    

    Observatie:

    Operatiile de calcul a valorii polinomului si de citire a datelor din fisierul de intrare s-au facut cu siruri pentru ca acestea pot depasi tipurile numerice.

    Fisiere de intrare: 1 2 3 4 5 6 7 8 9 10
    Fisiere de iesire: 1 2 3 4 5 6 7 8 9 10

    Deoarece nici o sursa nu a intrunit punctajul maxim, va propun sursa realizata de colaboratorul meu, Cristian Streng:

    Solutia nr. 1 (Pascal)


    Problema 3: Exponentul cu bucluc

    Consideratii teoretice:

    Fie p un numar natural, avand descompunerea in factori primi: p = p1e1* p2e2* ... * pkek, unde p1, p2, ..., pk sunt numere prime, iar e1, e2, ..., ek reprezinta numere naturale, exponentii la care apar numerele prime. Daca n este un numar natural oarecare, atunci exponentul e al lui p in n! este dat de formula:
    
    
    e = min      S  [n /(pij * ei)]
              1<=i<=k
    
    Exemplu:

          n = 253
          p = 108 = 22 * 33
          Conform consideratiilor de mai sus:
    	  - exponentul lui 22 in 253! este 120
    	  - exponentul lui 33 in 253! este 41
    	  - min (120,41) = 41.
    

    Teste

    S-au remarcat prin rezolvarea in timp foarte bun urmatoarele surse:

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

    In prag de An Nou va transmitem cele mai sincere urari de sanatate si implinirea dorintelor dvs. Dorim ca si in anul urmator sa avem o buna colaborare care sa ne aduca tuturor satisfactii. Cu cele mai sincere sentimente de prietenie:

    Prof. Maria si Adrian Nita
    Liceul "Emanuil Gojdu" - Oradea


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

    Inapoi!