Programming contests

DEIK Regionális Programozó Csapatverseny, egyetemi kategória, 2024. december 1.

December 1, 2024, 10:00 AM – December 1, 2024, 3:00 PM

System

Peter is building a communication network—or rather, just a line. He has two base stations that are robust and never fail. These will be connected by NN relay stations, which are positioned in a straight line at intervals of 100 meters.

The reliability of each relay station is known, meaning we know the probability that each will fail within one year. The stations fail independently of one another.

Operational stations (including the base stations) can bridge neighboring failed stations within a certain range. For Peter’s stations (and the base stations), this range is 300 meters. This means that if a signal needs to be transmitted, and there is an operational station within 300 meters in the direction of transmission, it can relay the signal.

A communication line is considered operational if it is possible to transmit signals between the two base stations.
Example:
The base stations are at the two ends, with 0 indicating a failed station and 1 an operational station.
This is an operational line:
B 0 0 1 1 0 1 0 0 B
because the largest gap to be bridged is 300 meters.
This is a non-operational line:
B 0 0 0 1 1 1 1 1 B
because the closest operational station is 400 meters away from the left base station.

Peter has designed several such lines, all of the same length. The difference between them lies in the reliability of the stations. He wants to rank these designs based on their reliability.

Let the failure probabilities of the relay stations be:
0.1 0.1 0.3 0.2
In this case, the system becomes non-operational in the following scenarios:
B 0 0 0 0 B
B 1 0 0 0 B
B 0 0 0 1 B
The probabilities of these failure scenarios are, respectively:
0.1 * 0.1 * 0.3 * 0.2
0.9 * 0.1 * 0.3 * 0.2
0.1 * 0.1 * 0.3 * 0.8
The total probability of the system failing within one year is the sum of these probabilities. This illustrates the kinds of patterns
we need to account for.
Peter asks you to determine the reliability of his designed systems. However, you don’t need to calculate the exact probabilities. Instead, for two given designs, you only need to decide which one is better—that is, which one has a lower probability of failure.

Input specification

The first line contains NN, the number of relay stations (excluding the base stations). The next two lines each contain NN real numbers separated by spaces—these are the individual reliability values of the relay stations for the first and second designs, respectively. Each of these values is one of the following: 0.01,0.05,0.1,0.15,0.2,0.30.01,0.05,0.1,0.15,0.2,0.3.

Output specification

If the first design is better, output 1. If the second design is better, output 2. If they are equally good, output 0. Two numbers are considered equal if the absolute difference between them is less than 101210^{-12}.

Constraints

3N203\le N \le 20

Sample input 1

  1. 3
  2. 0.1 0.2 0.1
  3. 0.2 0.1 0.2
download as text file

Sample output 1

  1. 1
download as text file

Sample input 2

  1. 3
  2. 0.1 0.2 0.1
  3. 0.2 0.2 0.2
download as text file

Sample output 2

  1. 1
download as text file
University of Debrecen; Faculty of Informatics; v. 09/30/2024