Code

After returning with honour from ICPC(International Cat Programming Contest) World Finals, Tom decides to say goodbye to ICPC and start a new period of life. He quickly gets interested in AI.

In the subject of Machine Learning, there is a classical classification model called perceptron, defined as follows:


Assuming we get a set of training samples: $D = \{(\boldsymbol{x_1},y_1), (\boldsymbol{x_2},y_2), ...,(\boldsymbol{x_N},y_N)\}$, with their inputs $\boldsymbol{x}\in \mathbb{R}^d$, and outputs $y\in \{-1, 1\}$. We will try to find a function
$f(\boldsymbol{x})={\rm sign}(\sum_{i=1}^dw_i\cdot x_i+b)={\rm sign}(\boldsymbol{w^T\cdot x}+b)$ so that $f(\boldsymbol{x_i}) = y_i,i = 1,2,...,N$.

$\boldsymbol{w},\boldsymbol{x}$ mentioned above are all $d$-dimensional vectors, i.e. $\boldsymbol{w}=(w_1,w_2,...,w_d)$, $\boldsymbol{x}=(x_1,x_2,...,x_d)$. To simplify the question, let $w_0=b$, $x_0=1$, then $f(\boldsymbol{x})={\rm sign}(\sum_{i=0}^dw_i\cdot x_i)={\rm sign}(\boldsymbol{w^T\cdot x})$. Therefore, finding a satisfying function $f(\boldsymbol{x})$ is equivalent to finding a proper $\boldsymbol{w}$.

To solve the problem, we have a algorithm, PLA(Popcorn Label Algorithm).

Accoding to PLA, we will randomly generate $\boldsymbol{w}$.

If $f(\boldsymbol{x})={\rm sign}(\boldsymbol{w^T\cdot x})$ fails to give
any element $(\boldsymbol{x_i},y_i)\in D$ the right classification, i.e. $f(\boldsymbol{x_i})\neq y_i$, then we will replace $\boldsymbol{w}$ with another random vector. We will do this repeatedly until all the samples $\in D$ are correctly classified.

As a former-JBer, Tom excels in programming and quickly wrote the pseudocode of PLA.

w := a random vector
while true do
    flag:=true
    for i:=1 to N do
        if f(x[ i ]) != y[ i ] then
            flag:=false
            break
    if flag then
        break
    else
        w := a random vector
return w

But Tom found that, in some occasions, PLA will end up into an infinite loop, which confuses him a lot. You are required to help Tom determine, when performed on a given sample set $D$, if PLA will end up into an infinite loop. Print Infinite loop! if so, or Successful! otherwise.

We only consider cases when $d=2$ for simplification.
Note: $
{\rm sign}(x) = \begin{cases}
-1 & x < 0 \\
0 \ & x = 0 \\
1 \ & x > 0
\end{cases}
$

The first line contains an integer $T(1\leq T\leq 1000)$, the number of test cases.
Each test case begins with a line containing a single integer $n(1\leq n\leq 100)$, size of the set of training samples $D$.
Then $n$ lines follow, the $i$th of which contains three integers $x_{i,1},x_{i,2},y_i$ $(-10^5\leq x_{i,1},x_{i,2}\leq 10^5,$ $y_i\in\{-1,1\})$, indicating the $i$th sample $(\boldsymbol{x_i},y_i)$ in $D$, where $\boldsymbol{x_i}=(x_{i,1},x_{i,2})$.

For each test case, output a single line containing the answer: “Infinite loop!” or “Successful!”.

3
2
1 1 1
2 0 -1
4
0 0 1
2 0 -1
1 1 1
1 -1 -1
6
0 0 1
2 0 -1
1 1 1
1 -1 -1
1 0 1
0 1 -1

Successful!
Successful!
Infinite loop!

2019 Multi-University Training Contest 1