## Redstone Repeaters

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C++

Bcy is playing Minecraft 1.10 and he is building a complicated circuit using redstone dust and repeaters and comparators and redstone blocks and all that good stuff to spice up his already high-tech virtual home. Yay. However, as any redstone Minecrafter would know, if bcy places 2 repeaters facing opposite directions, hooks them up with redstone wire and sends a redstone current through the circuit, it would result in an infinite loop and a 'forever-on' status!!!! Oh no!!!

bcy's circuit has suddenly messed up. He believes it is caused by an infinite repeater loop in his circuit that he must have accidentally triggered in some point of his redstone engineering. With all the pistons and intricate wiring in the way, bcy cannot solve the problem on his own. Being a C++ freak, you decided to help bcy out by coding a program to test if any infinite loops were present.

#### Input Format

The first line of input contains 2 integers, and , space-separated. represents the number of redstone repeaters (conveniently labelled ) in bcy's circuit, while represents the number of redstone wires hooked up to each repeater (can be related to the edges of a graph). The following lines of input contain 2 integers, and . These define a connection between repeater and repeater . It is guaranteed that this defines a 1-directional connection where points to but not otherwise.

#### Output Format

Output, on a single line, Infinite Loop Present if only 1 infinite loop is present.

Output Infinite Loops Present if more than 1 infinite loop is present. If there are no infinite loops, output No Infinite Loops.

#### Sample Input 1

4 4
1 2
2 4
1 3
4 4

#### Sample Output 1

Infinite Loop Present

#### Explanation 1

According to the last line of input where repeater 4 is connected to itself. This means that an infinite loop is present as the redstone current would come out of repeater 4 and go back into itself. The graph can be visualized as follows:

As such, an infinite loop is present.

#### Sample Input 2

4 5
1 2
2 3
3 1
3 4
4 4

#### Sample Output 2

Infinite Loops Present

#### Explanation 2

The inputs 1 2, 2 3, and 3 1 all create a triangle like loop. And the input 4 4 means repeater 4 is connected to itself. Thus there are 2 infinite loops and we output Infinite Loops Present. The graph can be visualized as follows:

• Ninjaclasher  commented on June 14, 2017, 7:05 p.m. edited

Does anyone knows what RTE (aborted) means? It happens when I run this line of code: ss.pop_front();in the line while (ss.front() != pos) ss.pop_front();

• Kirito  commented on June 15, 2017, 12:53 a.m. edited

If ss is empty, the program will abort.

while (!ss.empty() && ss.front() != pos) ss.pop_front();


Will probably fix the problem.

• Ninjaclasher  commented on June 3, 2017, 5:21 p.m. edit 2

If there was for example a case: 4 5 1 2 3 1 2 3 3 4 4 2

Would that be considered 2 loops or 3 loops?