No.3576 Mapping Check
タグ : / 解いたユーザー数 31
作問者 : 👑
Problem Statement
The input gives a non-negative integer $N$ and $N$ pairs of $2$ non-negative integers.
Let $F$ be the set consisting of the given $N$ pairs.
That is, for each positive integer $i$ not exceeding $N$, if we denote the $i$-th given pair by $(s_i,t_i)$, then $F = \{(s_i,t_i) \mid i \in \N \cap [1,N]\} = \{(s_1,t_1), \ldots, (s_N,t_N)\}$.
We say that $F$ is a good set if $F$ satisfies the following property:
- For any elements $(s,t)$ and $(s',t')$ of $F$, if $s = s'$, then $t = t'$.
Determine whether $F$ is a good set.
Background
$F$ being a good set means precisely that $F$ is a map. In other words, this problem asks you to determine whether $F$ is a map.
Here is a supplementary note for those who want to know more about maps. (Click to open)
First, here is a rough picture. A map is a generalization of a function: it is a concept in which the domain (the set of all values that can be substituted) can be chosen freely, and the values can also be chosen freely and are not limited to numbers. In this problem, we only consider maps whose domain is a subset of the set of all non-negative integers and whose values are non-negative integers.
A map is itself a set, and the elements of a map $f$ are the pairs $(x,f(x))$ as $x$ ranges over the elements of the domain. It may look like a strange set at first glance, but picturing a map in c++ may make it easier to understand.
The rough understanding above is sufficient for solving this problem, but here is an explanation for those who want the rigorous formulation of the domain and substitution. When $f$ is a map, the set of all first components (component $1$) $s$ of its elements $(s,t)$,
$\displaystyle \{s \mid \exists t[(s,t) \in f]\} $
is called the domain of $f$, and the set of all second components (component $2$) $t$,
$\displaystyle \{t \mid \exists s[(s,t) \in f]\} $
is called the range of $f$. In a context where a set containing the range is fixed, such a set is called the codomain of $f$.
Once $f$ and an element $s$ of its domain are fixed, the definition of a map implies that there is exactly one $t$ satisfying $(s,t) \in f$, and we denote it by $f(s)$. In this sense, $f(s)$ is defined only when $s$ belongs to the domain of $f$, so the domain of $f$ is exactly the region on which $f(s)$ is defined.
As you can guess from this notation using $()$ and from the term "domain", the concept of a map is used as a set-theoretic generalization of (single-valued) functions. Indeed, if you think of the graph of a function you know, you will be convinced that it satisfies the definition of a map (as the set of all points on the graph).
For example, the set $f = \{(0,3),(1,2),(2,5)\}$ is a map with domain $\{0,1,2\}$, and it satisfies
$\displaystyle \begin{array}{rcl} \displaystyle f(0) &\displaystyle = &\displaystyle 3 \\ \displaystyle f(1) &\displaystyle = &\displaystyle 2 \\ \displaystyle f(2) &\displaystyle = &\displaystyle 5 \end{array} $
.
Input
The input is given from standard input in $1 + N$ lines in the following format:
- Line $1$ contains $N$.
- For each positive integer $i$ not exceeding $N$, line $1 + i$ contains $s_i, t_i$ separated by a single-byte space.
$N$ $s_1$ $t_1$ $\vdots$ $s_N$ $t_N$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $0 \leq N \leq 10^5$.
- For any positive integer $i$ not exceeding $N$:
- $s_i$ is an integer satisfying $0 \leq s_i \leq 10^5$.
- $t_i$ is an integer satisfying $0 \leq t_i \leq 10^5$.
Output
Print Yes if $F$ is a good set, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
1 0 1
Output
Yes
$F = \{(0,1)\}$ is a good set.
For those familiar with maps, $F$ is a map with domain $\{0\}$ satisfying $F(0) = 1$.
Sample 2
Input
2 1 0 0 0
As in this case, it may be that $s_0 \leq s_1$ does not hold.
Output
Yes
$F = \{(1,0),(0,0)\}$ is a good set.
For those familiar with maps, $F$ is a map with domain $\{0,1\}$ satisfying $F(0) = F(1) = 0$.
Sample 3
Input
2 0 1 0 2
Output
No
Here, $F = \{(0,1),(0,2)\}$.
Since $(0,1) \in F$, $(0,2) \in F$, and $1 \neq 2$, $F$ is not a good set.
Sample 4
Input
2 0 1 0 1
As in this case, it may be that $(s_0,t_0) \neq (s_1,t_1)$ does not hold.
Output
Yes
$F = \{(0,1),(0,1)\} = \{(0,1)\}$ is the same set as in Sample 1, so it is a good set.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。