Round 1: November 14th, 1997
Problem 1: Numbers
Problem 2: The First Figure
Problem 3: The Parallel Machine

"People are divided in two categories: some of them seek and do not find, others find and are not satisfied."
Mihai Eminescu (Romanian poet - 1850-1889)

Problem 1: Numbers (20 points)

A positive number is represented as a string; the characters in this string can be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; the condition to be put is that the first character should be other than 0. If such a number L (made of maximum 500 figures) is given, you are to find how many numbers bigger than L can be built using all the figures in L.

Input Data:
The input file (INPUT.TXT) contains the figures of the number L, 10 on each line (except the last line). There is at least one line and not more than 50 lines with figures.

Output Data:
Write in the OUTPUT.TXT file a number which represents how many numbers, bigger than the given number,can be built out of its (the former's) figures.

Example Input and Output:
For the input file:
      1 1 1 1 1 1 1 1 1 1
      1 2
the output is:
Execution time: 5 seconds/test.

Adrian Atanasiu,
Bucharest University.

Problem 2: The First Figure (35 points)

Given a positive integer n, 0<=n<=65535, find out the first figure of the number n!=1*2*..*n.
Input: the keyboard.

Output: the screen.

Example Input and Output:

For n=4 the answer is:
4! begins with 2.

Execution time: 1 second/test for n<1000; 3 seconds/test for 1000<=n<=65535.

Adrian Atanasiu,
Bucharest University.

Problem 3: The Parallel Machine (20 points)

A parallel machine is a computer containing several processors. Each processor (CPU) can execute a job which is independent from the other processors.
Suppose there are n jobs J1, J2, .. Jn, that have to be processed by a parallel machine with P processors. A job can be processed by any processor. The P processors have the same execution speed. Of course, if all the processors are busy, some jobs have to wait until one of the processors becomes free.
You have to define an algorithm in order to minimize the average waiting time. The waiting time for a job is equal with the time that the job has to wait for a processor to become free, until the processor begins the execution of the job. The average waiting time is the sum of the average waiting times for all the jobs, divided with the number of jobs.
All the jobs are supposed to come (arrive) at the same time, and the programming decision of a job is 0 time units.

Input Data:
The file INPUT.TXT is defined in the following way: the first line contains two positive integer numbers representing the number P (1<=P<=500) of processors and the number J (1<=J<=1000) of jobs. Starting with the following lines, J positive integer numbers are listed, 25 in a line, separated by a space; they represent the execution time of the jobs.

Output Data:
The program will write in the OUTPUT.TXT file a real number (with 3 specific, exact decimals), representing the smallest average time of waiting for the jobs.

Example Input and Output:
      2 6
      4 1 1 2 2 3

Execution time: 1 second/test.

Adrian Atanasiu,
Bucharest University.

Translated into English by
Ioana Lucaciu.

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