Probleme - Etapa 5

Etapa 5: 12 februarie 1997

Problema 1: Un alt fel de Hanoi (45 puncte)

Fie 2 <= n <= 10 tije pe care se afla bile colorate. Culorile sunt notate cu numere de la 1 la n. Sa se aranjeze bilele pe tije, astfel incat pe fiecare sa fie n bile notate, de jos in sus, de la 1 la n. Pentru miscarea bilelor se va folosi o tija ajutatoare, notata n+1. Pe fiecare tija numarul maxim de bile este n. O bila se poate muta pe o alta tija, daca pe aceasta tija este loc si daca deasupra bilei nu se afla o alta.

Pozitia finala trebuie sa arate astfel:


        n       n      n       ...      n          |
       n-1     n-1    n-1              n-1         |
        .       .      .                .          .
        .       .      .                .          .
        .       .      .                .          .    <-- tije
        3       3      3                3          |
        2       2      2                2          |
        1       1      1                1          |
     ----------------------------------------------------
        1       2      3                n         n+1   <-- numarul
                                                             tijei

Configuratia initiala se citeste din fisierul "date" avand structura: pe prima linie este numarul de tije n pe urmatoarele n linii sunt n numere de la 1 la n,separate prin spatii, reprezentand asezarea bilelor pe fiecare tija, asezare citita de jos in sus.

Iesirea se face in fisierul "rez" in care fiecare linie, cu exceptia ultimei care contine un numar m, are forma i x y unde: i reprezinta culoarea; x si y numarul tijei de pe care, respectiv pe care, se muta bila; aceste numere sunt cuprinse intre 1 si n+1. m numarul total de mutari
Exemplu :

fisierul date:
2                                         1     2     |
1 1                                       1     2     |
2 2                                     -----------------
                                          1     2     3
fisierul rez:
2 2 3
2 2 3                                     2     2     |
1 1 2                                     1     1     |
2 3 1                                   -----------------
2 3 2                                     1     2     3
5

Timp de executie: 1min/test pe un 586 la 133MHz.

prof.Maria si Adrian Nita
Liceul "Emanuil Gojdu"
Oradea

Problema 2: Numere (30 puncte) (mai simplu decat pare!)

Sa se determine toate numerele naturale n < 60.000 cu urmatoarea proprietate: daca 1 < m < n si daca m este natural si prim cu n, atunci m este numar prim.

Scrierea in fisierul 'numsol' cu structura:

n1
n2
...
nk

unde ni sunt numerele cerute.
Timp de executie : 10 secunde.

prof. Maria si Adrian Nita
Liceul "Emanuil Gojdu"
Oradea

[Index] [Informatii importante!] [Participanti] [Etapa 4] [Etapa 6] ]