Round 6: January 9th, 1998
Problem 1: Wedding
Problem 2: The Coefficients of the Polynom with Maximum Value
Problem 3: The Trouble Exponent


I would have been able to understand many things if they had not been explained to me...

Problem 1: Wedding (30 points)

In our villages, the wedding tables are rectangular, having different sizes, and the wedding guests are sitting on the both sides of the table. No person sits at the heads of the tables! At one wedding party were invited only traditional families (husband and wife), but during the wedding the guests changed their places, so that for some families the husband and the wife do not stay together.
At a specific time (the festive moment) the husbands and their wives should stay together, but not necessarily at same table as at the beginning. Determine the minimum number of necessary movings, so that every husband stays near his wife; at the margin places of the tables should stay only men! Determine a succession of such moves, too! A move means placing one person on another chair.

Input Data:
Input file is NUNTA.INP. The input file contains one data test, having the following structure:
      n                             // the number of families, n<=1000
      k                             // the number of tables, k<=200
      p1 p2 ... pk                  // pi = number of places on one side of
                                       table i, i=1,k
      a1,1 a1,2 ... a1,p1           // indexes of the persons sitting at table 
                                       1, on the side 1, in order
      a2,1 a2,2 ... a2,p1           // indexes of the persons sitting at table 
                                       1, on the side 2, in order
      a3,1 a3,2 ... a3,p2           // indexes of the persons sitting at table 
                                       2, on the side 1, in order
      a4,1 a4,2 ... a4,p2           // indexes of the persons sitting at table 
                                       2, on the side 2, in order
      ...
      a2k-1,1 a2k-1,2 ... a2k-1,pk  // indexes of the persons sitting at table 
                                       k, on the side 1, in order
      a2k,1 a2k,2 ... a2k,pk        // indexes of the persons sitting at table 
                                       k, on the side 2, in order

Output Data:
The output file, NUNTA.OUT, contains the message
      'NU EXISTA SOLUTIE'
if there is no solution for the problem or it has the following structure:

Remarks:
  1. The persons are numbered from 1 to 2n.
  2. Every man has as index an odd number, and his wife has as index the following even number.
  3. The tables are completely occupied.
  4. At every moment at most two persons may stand.
Example 1:
      NUNTA.INP
      4
      1
      4
      4 2 3 1
      5 6 8 7

      NUNTA.OUT
      3
      1 1 1 1
      3 1 1 4
      4 1 1 3

Example 2:
      NUNTA.INP
      8
      2
      3 5
      1 4 2
      6 7 10
      3 5 11 12 13
      14 16 15 9 8

      NUNTA.OUT
      NU EXISTA SOLUTIE

Maximum execution time: 2 seconds/test on a 5x86/133 MHz.

Emanuela Mateescu,
"Grigore Moisil" High School,
Iasi.

Marinel Serban,
"Grigore Moisil" High School,
Timisoara.


Problem 2: The Coefficients of the Polynom with Maximum Value (25 points)

Let n be a natural number, n<=10.000 and a0, a1, ..., an a string of integers, each one having the absolute value equal to or less than 30,000. Using the elements of the string, we can obtain the polynom: P(x) = anxn + an-1xn-1 + ... + a1x + a0.
Let x a real number, in the form p1p2...pk.q1q2...qr , where p1p2...pk reprezinta is the integer part, and q1q2...qr the fractionary part of the real number x. p1, p2, ...pk, q1, q2, ..., qr are decimal digits.
Rearrange the elements of the string so that the value P(x) of the polynom be maximum.

Input Data:
Input file is POLINOM.IN, having the following structure:
      x
      n
      a0
      a1
      ...
      an

Output Data:
The results should be written in the file POLINOM.OUT, having the following structure:
      a0   //  the elements of the string in such an order
      a1   //  that the value is maximum
      an
      max  //  the maximum value of P(x), obtained for the above
	   //  rearranged string. This number has the same form as
	   //  x in POLINOM.IN with 3 exact decimals (no roundingoff).
				      ^^^^^

Example Input and Output:
      POLINOM.IN
      1.25
      3
      1
      3
      3
      1

      POLINOM.OUT
      1
      1
      3
      3
      12.797

Execution time: 2 seconds per test on a 586/133 MHz.

Doru Popescu Anastasiu,
"Radu Greceanu" High School,
Slatina.


Problem 3: The Trouble Exponent (20 points)

Let's take a number n, so that 0 < n < 2,000,000,000. Having a number p, 0 < p < 2,000,000,000, it is asked to determine the exponent for which we have p in n!.

Input Data:
The input data will be read from the EXP.IN file, having the structure:
      n  p        // separated with space will be:
		  // a value for n and a coresponding value for p whose
		  // power exponent in n! must be calculated

Output Data:
The output will go to EXP.OUT file, having the structure:
      e       // the exponent for p in n!

Examples Input and Output:
      EXP.IN
      5 6

      EXP.OUT
      1

      EXP.IN
      125 17

      EXP.OUT
      7

      EXP.IN
      253 108

      EXP.OUT
      41

Execution Time: 0.5 seconds for each pair (n, p) on a 586/133 MHz.

Maria & Adrian Nita,
"Emanuil Gojdu" High School,
Oradea
.


[First Round] [Previous Round] [Next Round] [Last Round] [Romāna] [Go Back!]