## HCI '16 - Redstone Repeaters

View as PDF

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

Authors:
Problem type

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 at some point in 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 Specification

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 Specification

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.

#### Constraints

Sample test cases.

#### 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:

• commented on March 5, 2024, 5:18 p.m.

Clarification: For those like me who aren't experienced in graphs and cycles, the problem is asking for the amount of Simple Cycles in the graph. A simple cycle is any path in a graph that has the same start and end node. This is seen in 4 -> 4 and 1 -> 2 -> 3 -> 1 in the second example. They are asking for the amount of unique simple cycles. Good luck and have fun!

• commented on Nov. 10, 2022, 1:42 a.m.

jusr realized the image isnt correct...

• commented on June 14, 2017, 11: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();

• commented on June 15, 2017, 4: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.

• commented on June 3, 2017, 9: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?