Finite or infinite
Tag(s):

## Algorithms, Math, Number Theory, Number theory

Problem
Editorial
Analytics

You are given the following:

• A set $S$ of size $n$
• A class of functions called $\mathbb{FUNC}$ $f: \mathbb{C} \to \mathbb{C}$ such that $\forall\ k \in S, f^k(x) = x$ holds $\forall\ x$
• A set $G$ that is defined based on the natural numbers such that a number $l \in G$ if and only if $f^l(x) = x \forall x$ holds $\forall f \in \mathbb{FUNC}$

Your task is to construct the complement set of $G$ based on the natural numbers, which implies that a number $l \in G'$ if and only if $l \notin G$

If the cardinality of $G'$ is finite, then print $FINITE$. Otherwise, print $INFINITE$. There are multiple test cases.

Mathematics note

• $f: \mathbb{C} \to \mathbb{C}$ is a notation that is used to describe a function $f$ that considers a complex number, $a+ib$, as an input and provides another complex number, $c+id$, as the output.
• $\forall$ is read as for all, particularly if $f^l(x) = x \forall x$ which implies that $​​f^l(x) = x$ is true for all $x$ in the domain of the function. Here, domain is a complex number.
• $f^l(x) = f(f(f(..f(x)))$ where $f$ is repeated $l$ times which means that $f^2(x) = f(f(x)), f^3(x) = f(f(f(x)))$.
• $\in$ is used to denote a set that is a subset of another set.
• Cardinality is used to denote the size of a set.

Input format

• First line: $t$ denoting the number of test cases
• For each test case:
• First line: $n$ denoting the size of the set $S$
• Second line: $n$ elements of set $S$

Output format

For each test case, print the string $FINITE$ or $INFINITE$ in a single line.

Constraints

$1\leq$ sum of $n$ over all the test cases $\leq 100000$

If $k \in S$, then $1 \leq k \leq 100000$

SAMPLE INPUT
2
3
2 4 1
1
2
SAMPLE OUTPUT
FINITE
INFINITE
Explanation

The sample has two test cases.

In first testcase, we have the information that $f(x) = x, f^2(x) = x, f^4(x) = x$, Note that, from $f(x) = x$ we can show that $f^m(x) = x$, $\forall m \in \mathbb{N}$. First, let us prove that $f^3(x) = x$ holds. $f(f(f(x))) = f(f(x)) = f(x) = x \implies f^3(x) = x$, where we used the fact $f(x) = x$ repeatedly. In a similar manner, we can prove the claim that $f^m(x) = x \forall m \in \mathbb{N}$. Hence, we get that for all $m \in \mathbb{N}$, $m \in G$. Thus, $G'$ is an empty set, and the answer is FINITE.

In the second testcase, we will prove that the set $G$ is exactly all the even positive numbers, i.e. $f^{2m}(x) = x$. We can get this claim from a similar inductive argument as above. Now, all we need to prove is that odd numbers are not part of $G$. Consider the simple function $f(x) = 1-x$, which satisfies the condition for all even positive integers (hence it belongs to class $\mathbb{FUNC}$), but it does not satisfy $f^{2m-1}(x) = x$ for any positive integer $m$. Hence, $G'$, the complement of $G$ is exactly the set of odd numbers, and thus the answer is INFINITE.

Updated problem name

Finite or infinite sets

Updated problem statement

You are given the following:

• A set $S$ of size $n$
• A class of functions called $\mathbb{FUNC}$ $f: \mathbb{C} \to \mathbb{C}$ such that $\forall\ k \in S, f^k(x) = x$ holds $\forall\ x$
• A set $G$ that is defined based on the natural numbers such that a number $l \in G$ if and only if $f^l(x) = x \forall x$ holds $\forall f \in \mathbb{FUNC}$

Your task is to construct the complement set of $G$ based on the natural numbers, which implies that a number $l \in G'$ if and only if $l \notin G$

If the cardinality of $G'$ is finite, then print $FINITE$. Otherwise, print $INFINITE$. There are multiple test cases.

Mathematics note

• $f: \mathbb{C} \to \mathbb{C}$ is a notation that is used to describe a function $f$ that considers a complex number, $a+ib$, as an input and provides another complex number, $c+id$, as the output.
• $\forall$ is read as for all, particularly if $f^l(x) = x \forall x$ which implies that $​​f^l(x) = x$ is true for all $x$ in the domain of the function. Here, domain is a complex number.
• $f^l(x) = f(f(f(..f(x)))$ where $f$ is repeated $l$ times which means that $f^2(x) = f(f(x)), f^3(x) = f(f(f(x)))$.
• $\in$ is used to denote a set that is a subset of another set.
• Cardinality is used to denote the size of a set.

Input format

• First line: $t$ denoting the number of test cases
• For each test case:
• First line: $n$ denoting the size of the set $S$
• Second line: $n$ elements of set $S$

Output format

For each test case, print the string $FINITE$ or $FINITE$ in a single line.

Constraints

$1\leq$ sum of $n$ over all test cases $\leq 100000$

If $k \in S$, then $1 \leq k \leq 100000$

Time Limit: 5,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

October Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Algorithms > Graphs
• Algorithms > Dynamic Programming
• Math > Basic Math
Уведомления

?