A9597. Design Tutorial: Make It Nondeterministic
编程题
普及/提高-
知识点
题目描述
A way to make a new task is to make it nondeterministic or probabilistic. For example, the hard task of Topcoder SRM 595, Constellation, is the probabilistic version of a convex hull.
Let's try to make a new task. Firstly we will use the following task. There are $n$ people, sort them by their name. It is just an ordinary sorting problem, but we can make it more interesting by adding nondeterministic element. There are $n$ people, each person will use either his/her first name or last name as a handle. Can the lexicographical order of the handles be exactly equal to the given permutation $p$ ?
More formally, if we denote the handle of the $i$ -th person as $h_{i}$ , then the following condition must hold: .
Let's try to make a new task. Firstly we will use the following task. There are $n$ people, sort them by their name. It is just an ordinary sorting problem, but we can make it more interesting by adding nondeterministic element. There are $n$ people, each person will use either his/her first name or last name as a handle. Can the lexicographical order of the handles be exactly equal to the given permutation $p$ ?
More formally, if we denote the handle of the $i$ -th person as $h_{i}$ , then the following condition must hold: .
输入格式
A way to make a new task is to make it nondeterministic or probabilistic. For example, the hard task of Topcoder SRM 595, Constellation, is the probabilistic version of a convex hull.
Let's try to make a new task. Firstly we will use the following task. There are $n$ people, sort them by their name. It is just an ordinary sorting problem, but we can make it more interesting by adding nondeterministic element. There are $n$ people, each person will use either his/her first name or last name as a handle. Can the lexicographical order of the handles be exactly equal to the given permutation $p$ ?
More formally, if we denote the handle of the $i$ -th person as $h_{i}$ , then the following condition must hold: .
Let's try to make a new task. Firstly we will use the following task. There are $n$ people, sort them by their name. It is just an ordinary sorting problem, but we can make it more interesting by adding nondeterministic element. There are $n$ people, each person will use either his/her first name or last name as a handle. Can the lexicographical order of the handles be exactly equal to the given permutation $p$ ?
More formally, if we denote the handle of the $i$ -th person as $h_{i}$ , then the following condition must hold: .
输出格式
If it is possible, output "YES", otherwise output "NO".
输入输出样例
输入 #1
3 gennady korotkevich petr mitrichev gaoyuan chen 1 2 3
输出 #1
NO
输入 #2
3 gennady korotkevich petr mitrichev gaoyuan chen 3 1 2
输出 #2
YES
输入 #3
2 galileo galilei nicolaus copernicus 2 1
输出 #3
YES
输入 #4
10 rean schwarzer fei claussell alisa reinford eliot craig laura arseid jusis albarea machias regnitz sara valestin emma millstein gaius worzel 1 2 3 4 5 6 7 8 9 10
输出 #4
NO
输入 #5
10 rean schwarzer fei claussell alisa reinford eliot craig laura arseid jusis albarea machias regnitz sara valestin emma millstein gaius worzel 2 4 9 6 5 7 1 3 8 10
输出 #5
YES
说明/提示
In example 1 and 2, we have 3 people: tourist, Petr and me (cgy4ever). You can see that whatever handle is chosen, I must be the first, then tourist and Petr must be the last.
In example 3, if Copernicus uses "copernicus" as his handle, everything will be alright.
In example 3, if Copernicus uses "copernicus" as his handle, everything will be alright.