Solutions for Round 6

Problem 1: Nunta
Problem 2: Colonies on Mars
Problem 3: Zeroes Again...


Problem 1: Nunta

    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

The tests are sent as attached documents:
   input.zip
   output.zip.

There was no problem in C to get the maximum score.
The following programs (C++ and Pascal) are examples of maximum scored programs.
We also attach the two libraries C++ and Pascal that we used.



Input files: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
Output files: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


Author: Catalin Andrei Francu

Solution no. 1 (Pascal) Solution no. 2 (C)


Problem 2: Colonies on Mars

The difficulty of the problem was, probably, in the used algorithm.
The Greedy algorithm didn't lead to the best solution in this case.
There was a simple text of application of the Ungar Algorithm (name with
which it is very well-known in our country).
Because one of the sources made this algorithm, step by step, we commented
(without asking for permission from the one who made the program) the
received source.In fact, we were very much helped by the "tidy" and clear
manner in which this source was realized, source belonging to Mr.George
Stoianov.

No source in C obtained the maximum score.
We afford to give another example (also in Pascal), as the source is very
short.

Input files: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Output files: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
The maximum given score, respectively for the tests that got it, was:
1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 = 25 points.

We wish you lots of luck further on.

Solution (Pascal)

                         Teachers
                             Prof. Maria si Adrian Nita
                         Liceul Teoretic "Emanuil Gojdu"
                                   Oradea

Problem 3: Zeroes Again...

For a number made up of the figures:
c c c ....c
1 2 3 n
the algorithm could be the following:
- it is read figure by figure from the last figure;
- if c <> 0, then in Number_zero := c c c ....c
n 1 2 3 n-1
- if c <> 0, then Number_zero := Number_zero + c c c ...c 0
n-1 1 2 3 n-2
- the same if c <> 0,
i
Number_zero := Number_zero + c c c ...c 00000 ;
1 2 3 i-1 0 n-i times
- if c = 0, then,in order to continue the algorithm, we consider
i
the number b b b ....b ..... = c c c ... c - 1
1 2 3 i-1 1 2 3 i-1
and to Number_zero we add the number:
c c .... c + 1
i+1 i+2 n
Example:

for 123456
Number_zero = 12345 + 12340 + 12300 + 12000 + 10000 = 58985
for 1001
Number_zero = 100 + 2 + 90 = 192
To correct the problems, we used a checking program that compared the
files .OUT figure by figure.
Input files: 1 2 3 4 5 6 7 8 9 10
Output files: 1 2 3 4 5 6 7 8 9 10 
Solution no. 1 (Pascal) Solution no. 2 (C)
We wish you good luck further on.

                           Teachers
                               Maria and Adrian Nita
                           "Emanuil Gojdu" - Highschool
                                    Oradea

[The problems] [First Round] [Previous Round] [Next Round] [Current Round] [Romāna] [Go Back!]

Go Back!