3848: Code
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：5
解决：2
题目描述
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={(x1,y1),(x2,y2),...,(xN,yN)} , with their inputs x∈Rd , and outputs y∈{−1,1} . We will try to find a function
f(x)=sign(∑di=1wi⋅xi+b)=sign(wT⋅x+b) so that f(xi)=yi,i=1,2,...,N .
w,x mentioned above are all d -dimensional vectors, i.e. w=(w1,w2,...,wd) , x=(x1,x2,...,xd) . To simplify the question, let w0=b , x0=1 , then f(x)=sign(∑di=0wi⋅xi)=sign(wT⋅x) . Therefore, finding a satisfying function f(x) is equivalent to finding a proper w .
To solve the problem, we have a algorithm, PLA(Popcorn Label Algorithm).
Accoding to PLA, we will randomly generate w .
If f(x)=sign(wT⋅x) fails to give
any element (xi,yi)∈D the right classification, i.e. f(xi)≠yi , then we will replace w with another random vector. We will do this repeatedly until all the samples ∈D are correctly classified.
As a former-JBer, Tom excels in programming and quickly wrote the pseudocode of PLA.
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: sign(x)=⎧⎩⎨−10 1 x<0x=0x>0
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={(x1,y1),(x2,y2),...,(xN,yN)} , with their inputs x∈Rd , and outputs y∈{−1,1} . We will try to find a function
f(x)=sign(∑di=1wi⋅xi+b)=sign(wT⋅x+b) so that f(xi)=yi,i=1,2,...,N .
w,x mentioned above are all d -dimensional vectors, i.e. w=(w1,w2,...,wd) , x=(x1,x2,...,xd) . To simplify the question, let w0=b , x0=1 , then f(x)=sign(∑di=0wi⋅xi)=sign(wT⋅x) . Therefore, finding a satisfying function f(x) is equivalent to finding a proper w .
To solve the problem, we have a algorithm, PLA(Popcorn Label Algorithm).
Accoding to PLA, we will randomly generate w .
If f(x)=sign(wT⋅x) fails to give
any element (xi,yi)∈D the right classification, i.e. f(xi)≠yi , then we will replace w with another random vector. We will do this repeatedly until all the samples ∈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: sign(x)=⎧⎩⎨−10 1 x<0x=0x>0
输入
The first line contains an integer T(1≤T≤1000), the number of test cases.
Each test case begins with a line containing a single integer n(1≤n≤100), size of the set of training samples D.
Then n lines follow, the ith of which contains three integers xi,1,xi,2,yi (−10^5≤xi,1,xi,2≤10^5, yi∈{−1,1}), indicating the ith sample (xi,yi) in D, where xi=(xi,1,xi,2).
Each test case begins with a line containing a single integer n(1≤n≤100), size of the set of training samples D.
Then n lines follow, the ith of which contains three integers xi,1,xi,2,yi (−10^5≤xi,1,xi,2≤10^5, yi∈{−1,1}), indicating the ith sample (xi,yi) in D, where xi=(xi,1,xi,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!