Codeforces 954 C. Matrix Walk_综合

好久没更新了最近做的一些题，陆续写上来一些吧，，，

There is a matrix A of size x?×?y filled with integers. For every , Ai,?j?=?y(i?-?1)?+?j. Obviously, every integer from [1..xy] occurs exactly once in this matrix.

You have traversed some path in this matrix. Your path can be described as a sequence of visited cells a1, a2, ..., an denoting that you started in the cell containing the number a1, then moved to the cell with the number a2, and so on.

From the cell located in i-th line and j-th column (we denote this cell as (i,?j)) you can move into one of the following cells:

(i?+?1,?j) — only if i?<?x;
(i,?j?+?1) — only if j?<?y;
(i?-?1,?j) — only if i?>?1;
(i,?j?-?1) — only if j?>?1.

Notice that making a move requires you to go to an adjacent cell. It is not allowed to stay in the same cell. You don't know x and yexactly, but you have to find any possible values for these numbers such that you could start in the cell containing the integer a1, then move to the cell containing a2 (in one step), then move to the cell containing a3 (also in one step) and so on. Can you choose x and yso that they don't contradict with your sequence of moves?

Input

The first line contains one integer number n (1?≤?n?≤?200000) — the number of cells you visited on your path (if some cell is visited twice, then it's listed twice).

The second line contains n integers a1, a2, ..., an (1?≤?ai?≤?109) — the integers in the cells on your path.

Output

If all possible values of x and y such that 1?≤?x,?y?≤?109 contradict with the information about your path, print NO.

Otherwise, print YES in the first line, and in the second line print the values x and y such that your path was possible with such number of lines and columns in the matrix. Remember that they must be positive integers not exceeding 109.

        Examples
       
          input
          
           Copy
          
8
1 2 3 6 9 8 5 2

          output
          
           Copy
          
YES
3 3

          input
          
           Copy
          
6
1 2 1 2 5 3

          output
          
           Copy
          
NO

          input
          
           Copy
          
2
1 10

          output
          
           Copy
          
YES
4 9

Note

The matrix and the path on it in the first test looks like this:

Also there exist multiple correct answers for both the first and the third examples.

题意：给出你一个n和n个数，问你是否存在 x * y的一个矩阵，可以满足n个数依次走的路径。

比如样例1

8
1 2 3 6 9 8 5 2

然后下面这个图的解释，就是可以在 3 * 3的矩阵里保存这个序列，所以YES 3 3，不存在这个矩阵的话就 NO

思路：

稍微想一下，其实根本不用管x这个行有多少的，只要满足，我们就直接输出最大值，真正影响的是后面的这个y，y列的情况，刚开始想的是如果两个数之间的差，除了1，除了另外一个数，还存在一个与他们俩个不同的数的话，肯定就NO了，

但是即使他满足前面那个条件也不一定是yes ，

比如

2 3 4 2 只有1 和 2 ，但是他是不存在2 可以走到 3 的，这就是问题所在。

其实在一行里，只有第一个数，和最后一个数是特殊的，在这儿设第一个数l，最后一个数r

比如第一个数，如果y！=1的时候，第一个数肯定不可能从l - 1得来的，最后一个数也不可能是由r - 1得来的，因此你需要特判这两种情况就可以了。

刚开始没想到，暴力判断的，后来wa在18组，一看那组数据，突然就想到了，

代码如下：

#include <bits/stdc++.h>using namespace std;int n,a[200200];
int main() {ios::sync_with_stdio(false);while(cin >> n) {int flag = 0;for(int i = 0; i < n; i++)cin >> a[i];int y = -1;for(int i = 0; i < n - 1; i++) {int x = abs(a[i + 1] - a[i]);if(x == 1)continue;else if(x == 0) {cout << "NO" << endl;return 0;} else {y = x;}}if(y == -1)cout << "YES" << endl,cout << 1000000000 << " " << 1 << endl;else {for(int i = 1; i < n; i++) {int ll = abs(a[i] - a[i - 1]); if(y != ll && ll != 1) {cout << "NO" << endl;flag  = 1;break;}if(a[i] % y == 0 && a[i - 1] - a[i] == 1) {cout << "NO" << endl;flag = 1;break;}if(a[i] % y == 1 && a[i] - a[i - 1] == 1) {cout << "NO" << endl;flag = 1;break;}}if(!flag)cout << "YES" << endl,cout << 1000000000 << " " << y << endl;}}return 0;
}