Round 7: January 16th, 1998
Problem 1: Once upon a Time...
Problem 2: Colonies on Mars
Problem 3: Zeroes Again...


Having intelligence is not enough, you have to use it well.
Descartes

Problem 1: Once upon a Time... (30 points)
"Quaevis comparatio claudicat"
("Any comparison has its weak points")
Cicero, "De senectute"

(hope you're not hungry, we're going to talk about lots of chips here :-)

...and then the stepmother told Cinderella: "Here you have these N<=10000 VLSI chips, numbered from 1 to N. Some of them are good, but some of them are defective. And you'd better select the good chips from the bad chips at once... or else !" Then the wicked woman left for the prince's ball with her two daughters.

Poor Cinderella sat in a corner and started crying. The N chips looked exactly the same - how could she tell the good ones from the bad ones ? But as she was weeping, the good fairy showed up and presented her with a strange object. Then she said:
"Dear Cinderella, I shall help you because you're good-hearted. Take this module; you can use it to test the chips. By putting any two chips in the module, they will test each other. A good chip will always say precisely whether the other chip is good or bad. But you should not trust what a bad chip will say. It can offer you correct information on the other chip, or it can lie to you. Thus the conclusions you may draw by testing chips A and B are:
Chip A says: Chip B says: Conclusions
"Chip B is good" "Chip A is good" Both chips are good
or they're both bad
"Chip B is good" "Chip A is bad" At least one chip is bad
"Chip B is bad" "Chip A is good" At least one chip is bad
"Chip B is bad" "Chip A is bad" At least one chip is bad
This module will help you finish your job and go to the ball. Yet you must remember two things. First, you should know that more than N/2 of the chips are good. Second, the module will burn out after you use it 2*N times. Therefore take care and do not waste your tests. Well, I'd like to stay a bit more and help you, but I've got to get to the ball, too. Good luck!" And gone she was.

Very happily, Cinderella went straight to her phone book and called you asking you to write a program that would help her in her job of sorting the chips. Cinderella will provide all the data you need through a Pascal or C module. The module will be included by adding the following line in your source code:
      Pascal : uses Cindy;
      C      : #include "cindy.h"
The module will provide you the following functions and procedures:
      Pascal: procedure LoadData;
      C     : void loaddata(void);
This procedure MUST be executed only once, before you call any other procedure or function in this module. Its mission is to load the data.
      Pascal: function NChips:Integer;
      C     : int nchips(void)
This function returns the number of chips, N.
      Pascal: procedure Test(X,Y:Integer; var SayX, SayY:Integer);
      C     : void test(int X, int Y, int *SayX, int*SayY);
This procedure tests the chips numbered X and Y. It returns values in SayX and SayY in the following manner:
      SayX=0 if chip X says "Chip Y is bad"
      SayX=1 if chip X says "Chip Y is good"
      SayY=0 if chip Y says "Chip X is bad"
      SayY=1 if chip Y says "Chip X is good"
Here's a brief Pascal example of how to use the module:
program mingIsFun;
uses Cindy;
var N, A, B:Integer;
begin
  { ... other instructions ... }
  LoadData;
  N:=NChips;
  Test(1, 2, A, B);
  if A*B=1
    then WriteLn('Chips 1 & 2 are either both good or both bad')
    else WriteLn('At least one chip among 1 & 2 is bad');
  { ... other instructions ... }
end.
Your program must write N characters 0 or 1 (all on the same line, not separated by spaces) to the output file CHIPS.TXT. No EOLN or blank line will be added at the end of the file (therefore the output file will be exactly N bytes long). The first character to be written will be 0 if the first chip is bad or 1 if it is good. The second character will be 0 if the second chip is bad or 1 if it is good and so on. For example, the string 1010110 means that chips 1, 3, 5 and 6 are good, while chips 2, 4 and 7 are bad.

Time limit: 2 seconds/test.

Other information:
  1. A program test will NOT be passed if it uses the testing module more than 2*N times.
  2. There will be given no partial points for correctly identifying only a part of the chips.
  3. There will be given no points for programs which exceed the running time of 2 seconds. It is guaranteed that the runing time of the module Cindy is less than 0.1 seconds. (by "running time of the module" we understand the time needed for one call of the LoadData procedure, one call of the NChips function and 20000 calls of the Test procedure).
  4. The programs will be run on a Cyrix P166+ with 16MB RAM.
  5. When your program is run, 500kB of the conventional memory will be free.
  6. To discourage the use of heuristic methods, the evaluation of your programs will work in the following manner: 15 tests will be run, grouped in 5 sets of 3 tests each. Each set will be worth a few points, which will be given only if all the 3 tests in the set are passed.
  7. E-mail me at cfrancu@pcnet.pcnet.ro for any questions.

Catalin Frāncu,
Politehnica University,
Bucharest.


Problem 2: Colonies on Mars (25 points)

In the year 2003, on planet Mars, the building of an "oasis" in which humans could live was finished. With a view to colonisation, each country on Earth sent its representative. Knowing that, to transport an individual, a special plane is being used, and that each travel has a well-established cost given in a matrix of the shape:
     C[i,j] = the cost for transporting person "i" using plane "j",
you are to determine a repartition of the persons in the planes, so that the total transport costs be minimum.

Input Data:
The input data is read from the file MARTE.IN, having the following structure:
      n                     // in the first line, the number of individuals;
      c11 c12 c13 ... c1n
      c21 c22 c23 ... c2n
      ...
      cn1 cn2 cn3 ... cnn
			    // in the following n lines, the costs
			    // corresponding to the travels, the natural
			    // integers between 1 and 255, separated by space
			    // 0 < n < 100;

Output Data:
The output data is written in the file MARTE.OUT, having the following structure:
c1i1     // representing in the first n lines the costs
        // ckik   1 <= k <= n;  1 <= ik <= n
c2i2     // that make the minimum requested and in
c3i3     // the last line, the value of this minimum
...
cnin     // min = c1i1 +
min     // c2i2 + ... +
        // cnin

Example Input and Output:
      MARTE.IN
      17 43 27 14 39 52
      29 24 69 90 23 13
      18 90 62 12 16 70
      58 14 6 18 73 64
      15 41 38 36 40 60
      25 44 18 44 13 50

      MARTE.OUT
      27
      13
      16
      14
      15
      18
      90

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

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


Problem 3: Zeroes Again... (20 points)

Given the natural integers, written one after the other, from 1 to n, where n is read from the Z.IN file and has maximum 1000 figures, how many times does the figure zero appear when writing these numbers? The number of zeroes will be written in the file Z.OUT.

Examples Input and Output:
      Z.IN
      123456

      Z.OUT
      58985

      Z.IN
      222222222

      Z.OUT
      175308642

Maximum Execution Time: 3 seconds per test 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!]