                      ETAPA VI -  PROBLEME
                      ^^^^^^^^    ^^^^^^^^


Moto:  Multe lucruri as fi fost capabil sa inteleg, daca nu mi se explicau...


                        NUNTA - 30 puncte
                        ^^^^^

    Pe la noi prin sat, mesele la nunti sunt dreptunghiulare, de dimensiuni
diferite, iar nuntasii pot fi asezati pe ambele laturi ale mesei. Capetele
meselor nu sunt ocupate! La o astfel de nunta au fost invitate numai perechi
(traditionale), dar in valtoarea nuntii persoanele si-au schimbat locurile,
iar la unele perechi sotul si sotia nu mai stau alaturi la masa.
    La strigatul darului este indicat, totusi, ca sotul si sotia sa stea
unul langa altul la masa. Determinati numarul minim de mutari necesare pentru
ca fiecare sot si sotia corespunzatoare sa fie asezati pe pozitii alaturate
la o masa si la marginile meselor sa fie asezati doar barbati. Determinati de
asemeni si o succesiune de astfel de mutari. Prin mutare se intelege asezarea
unei persoane pe un alt loc.

Restrictii de intrare/iesire:
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Datele de intrare se citesc din fisierul NUNTA.INP.
Fisierul contine un singur set de date de test cu urmatoarea structura:
n                   //numarul de perechi invitate, n<=1000
k                   //numarul de mese, k<=200
p1 p2 ... pk        // pi = numarul de locuri disponibile pe o latura
                            a mesei i, i=1,k
a1,1 a1,2 ... a1,p1    // indicii persoanelor asezate la masa 1, in ordine,
                          pe latura 1
a2,1 a2,2 ... a2,p1    // indicii persoanelor asezate la masa 1, in ordine,
                          pe latura 2
a3,1 a3,2 ... a3,p2    // indicii persoanelor asezate la masa 2, in ordine,
                          pe latura 1
a4,1 a4,2 ... a4,p2    // indicii persoanelor asezate la masa 2, in ordine,
                          pe latura 2
..
a2k-1,1 a2k-1,2 ... a2k-1,pk    // indicii persoanelor asezate la masa k,
                                   in ordine, pe latura 1
a2k,1 a2k,2 ... a2k,pk          // indicii persoanelor asezate la masa k,
                                   in ordine, pe latura 2

Fisierul de iesire se numeste NUNTA.OUT si contine mesajul NU EXISTA SOLUTIE
sau are urmatoarea structura:
 - pe prima linie MIN, numarul minim de mutari necesare;
 - fiecare din urmatoarele MIN linii reprezinta o mutare, codificata prin
specificarea indicelui persoanei care se muta, numarul mesei la care se
muta, latura si locul pe care se aseaza, separate prin spatii.

Observatii:
^^^^^^^^^^
1. Persoanele sunt numerotate de la 1 la 2n.
2. Fiecare barbat are ca indice un numar impar, sotia sa avand ca indice
   numarul par imediat urmator.
3. Mesele sunt complet ocupate.
4. In fiecare moment pot fi in picioare cel mult doua persoane.

Exemplul 1:
^^^^^^^^^^
Pentru fisierul de intrare:
4
1
4
4 2 3 1
5 6 8 7

Fisierul de iesire poate fi:
3
1 1 1 1
3 1 1 4
4 1 1 3

Exemplul 2:
^^^^^^^^^^
Pentru fisierul de intrare:
8
2
3 5
1 4 2
6 7 10
3 5 11 12 13
14 16 15 9 8

Fisierul de iesire va fi:
NU EXISTA SOLUTIE

Timp de executie: maxim 2 secunde/test pentru 5x86/133 MHz

                           prof. Emanuela Mateescu
                                 Liceul de Informatica "G. Moisil" Iasi
                           prof. Marinel Serban
                                 Liceul de Informatica "G. Moisil" Timisoara






                COEFICIENTII POLINOMULUI CU VALOARE MAXIMA
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                              25 puncte


      Se considera n un numar natural, n<=10 000 si a , a , ..., a
                                                     0   1        n
un sir de numere intregi fiecare avand valoarea absoluta mai mica sau
egala decat 30 000.
      Folosind elementele sirului se formeaza polinomul:

                 n         n-1
       P(x) = a x  + a   x    + ... + a x + a
               n      n-1              1     0

Fie un x numar real, dat sub forma p p ...p .q q ...q , cu semnificatia:
                                    1 2    k  1 2    r
p p ...p  reprezinta partea intreaga, iar q q ...q  partea fractionara a
 1 2    k                                  1 2    r
a numarului real x.
p , p ,...p , q , q ,...q  sunt cifre ale sistemului zecimal.
 1   2     k   1   2     r

Se cere sa se rearanjeze elementele sirului astfel incat valoarea P(x) a
polinomului sa fie maxima.

Cerintele problemei:
^^^^^^^^^^^^^^^^^^^^
 - datele de intrare se citesc din fisierul text POLINOM.IN cu structura:

 x
 n
 a0
 a1
 .....
 an
 - rezultatele se scriu in fisierul POLINOM.OUT cu structura:

 a0       //  reprezentand elementele sirului in ordinea
 a1       //  in care se realizeaza maximul
 ....
 an
 max      //  valoarea maxima P(x) a polinomului, obtinuta pentru
          //  sirul rearanjat mai sus. Aceasta valoare se va scrie sub
          //  aceeasi forma ca si x din POLINOM.IN cu 3 zecimale exacte
                                                                 ^^^^^^
          //  ( fara rotunjire).


 Exemplu:
 ^^^^^^^^
 Pentru fisierul POLINOM.IN:

1.25
3
1
3
3
1

 Fisierul POLINOM.OUT are foma:

1
1
3
3
69.125
Precizari:
  Valoarea din POLINOM.OUT pentru x=2.5 este 12.797
  Numarul de cifre de la partea intreaga si cea zecimala nu depaseste 10.
  x poate fi negativ!  Exemplu -1234.123
  Pentru x este corect  2.0 sau 2.45  si nu 2.
  Testele de evaluare sunt pentru numere reale: 2.0 nu 2.

 Timpul de executie este de 2sec/test pentru 586/133 MHz.


                           Prof. Doru Popescu Anastasiu
                         Liceul "Radu Greceanu" - Slatina
                            E-mail dpa@lotrg.sfos.ro






                EXPONENTUL CU BUCLUC - 20 puncte
                ^^^^^^^^^^^^^^^^^^^^

       Se considera un numar n, astfel incat 0 < n < 2.000.000.000
Fiind dat un numar p, 0 < p < 2.000.000.000, se cere sa se determine
exponentul la care apare p in n!.

Cerinte:
^^^^^^^
 - datele de intrare se citesc din fisierul EXP.IN, cu structura:

n  p          // despartite prin spatiu vor fi:
              // o valoare pentru n si corespunzator valoarea pentru
              // p a carui exponent al puterii in n! trebuie calculat

 - datele de iesire vor fi in fisierul EXP.OUT, cu structura:

e            // reprezentand exponentul corespunzator pentru
             // p din n!


Exemple:
^^^^^^^^
EXP.IN:                                EXP.OUT:
5 6                                    1

EXP.IN                                 EXP.OUT
125 17                                 7

EXP.IN                                 EXP.OUT
253 108                                41
Precizare:
Pentru
N=5
P=21, raspunsul este E=0

Deci pentru P=1, E=0

Timp de execut  0.5 sec pentru fiecare pereche (n p)

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




