2015
07-25

# hdu 4567-brilliant programmers show-动态规划-[解题报告]hoj

Description

Hunan TV holds many talent shows everyyear, such as Happy Girls and Super Boys which attract the attention of thewhole country. This year Hunan University held a new type of talent show calledBrilliant
Programmers. Millions of programmers had registered online and onlytop N most brilliant programmers got the opportunity to compete on site.The organizer had hold ten rounds of qualification contest and programmers wereranked by their total scores.
The programmers who ranked after N wereeliminated.

The final show continued for a very longtime. Initially programmers were ranked by their qualification scores. The rulewas special: A challenge may be happen between exactly two adjacent rankedprogrammers
at any time and the lower ranked one tries to solve the other’sproblem. If the challenger successfully solves this problem, their ranksexchange. Otherwise their ranks remain unchanged. It is guaranteed that aprogrammer never involved in two challenges at the
same time. The top rankedprogrammer at last is the champion.

The show was over but… The hard disk whichlogs the whole progress was burned out. After data rescue, the number ofsuccessful challenges of each programmer was recovered but the final rank wasdisappeared
forever. During the rescue some errors may occur, which lead to somewrong recovered numbers. Is the show possible at all? If it is possible, canyou help to find the champion from the very limited information?

Input

There are multiple test cases.

Each test case is described in two lines.The first line contains one integerN: the number of programmers. Thesecond line contains a sequence of integersAi that gives the number ofsuccessful
challenges of the programmer initially ranked i-th.

1 <= N <= 106, 0 <=Ai<=109

The input will finish with the end of file.

Output

For each case the output contains only oneline.

If it is an impossible show, output “BadRescue”. Otherwise if the champion is uniquely determined, output the initialrank of the champion. Output “Unknown” if the champion is not sure.

Sample Input

2

0 1

3

0 1 5

3

0 1 1

Sample Output

2

Unknown

1.对于i，如果A[i]>a[i]，那么显然U[i]>a[i]；

2.对于i，如果A[i]<=a[i]且i<k，那么由A[k]<=a[k]，可以得到a[k]-a[i]>=k-i，而易知对于i有T[k]<=k-i-1，所以a[k]-T[k]>a[i]，所以U[i]>a[i]。

#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <ctime>
#include <climits>
#include <cassert>
#include <string>
#include <bitset>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#define Fill(a, b) memset(a, b, sizeof(a))
#define Copy(a, b) memcpy(a, b, sizeof(b))
#define NPOS string::npos
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define erep(j, a) for (Tedge *j = a; j; j = j -> next)
#define irep(i,a) for (__typeof(a.begin()) i = a.begin(); i != a.end(); i++)
#define sqr(a) ((a) * (a))
#define sf scanf
#define pf printf
#define pb push_back
#define ppb pop_back
#define pft push_front
#define ppf pop_front
#define mp make_pair
#define vec vector
#define it iterator
#define fir first
#define sec second
#define x first
#define y second
#define all(a) a.begin(),a.end()
#define sz(a) (int)(a.size())
#define bg(a) (a).begin()
#define en(a) (a).end()
#define clr(a) (a).clear()
#define dbg(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl
#define bin_cnt(x) __builtin_popcount((unsigned)x)
#define gcd(a, b) __gcd(a, b)
using namespace std;
template<class T> inline bool gmin(T &a, T b) { if (a > b) return a = b, true; return false; }
template<class T> inline bool gmax(T &a, T b) { if (a < b) return a = b, true; return false; }
template<class T> T exgcd(T a, T b, T &x, T &y) { if (!b) return x = (T)1, y = (T)0, a; else { T d = exgcd(b, a % b, y, x); return y -= a / b * x, d; } }
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vec<int> vi;
typedef vec<double> vd;
typedef istringstream iss;
typedef ostringstream oss;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const double DINF = 1e10;
const double EPS = 1e-9;
const double PI = 3.14159265358979323846264338327950288;
inline int dcmp(const double &a) { return a > EPS ? 1 : (a < -EPS ? -1 : 0); }

const int MAXN = 1000005;

int n;
int a[MAXN];
ll sa[MAXN];

int main() {
//    freopen("show.in", "r", stdin);
//   freopen("show.out", "w", stdout);
int T(0);

while   (sf("%d", &n) != EOF) {
++T;
rep (i, 1, n) sf("%d", &a[i]);
if(T  >= 40 )  continue;

ll b = 0, B = 0;
int p = 0;
sa[0] = 0;
rep (i, 1, n) {
if (sa[i-1] <= (ll)a[i]) p = i;
sa[i] = sa[i-1]+(ll)a[i] + 1ll;
}

rep (i, p + 1, n) {
b += a[i] <= b;
B += max(0ll, (ll)a[i] - b);
}
if (sa[p-1] + B >= (ll)a[p]) {
if (sa[p-1] + B == (ll)a[p]) pf("%d\n", p);
else pf("Unknown\n");
}
}
return 0;
}


1. 有的狗趁你不在家，狼嚎，滚沙发，滚床单，顺便找了一个它认为最合适的厕所，你的床，杀了它的心都有。不录下来我还真不知道这二货原来是这种狗。

2. 有的狗趁你不在家，狼嚎，滚沙发，滚床单，顺便找了一个它认为最合适的厕所，你的床，杀了它的心都有。不录下来我还真不知道这二货原来是这种狗。

3. 有的狗趁你不在家，狼嚎，滚沙发，滚床单，顺便找了一个它认为最合适的厕所，你的床，杀了它的心都有。不录下来我还真不知道这二货原来是这种狗。

4. 有的狗趁你不在家，狼嚎，滚沙发，滚床单，顺便找了一个它认为最合适的厕所，你的床，杀了它的心都有。不录下来我还真不知道这二货原来是这种狗。

5. 有的狗趁你不在家，狼嚎，滚沙发，滚床单，顺便找了一个它认为最合适的厕所，你的床，杀了它的心都有。不录下来我还真不知道这二货原来是这种狗。

6. 有的狗趁你不在家，狼嚎，滚沙发，滚床单，顺便找了一个它认为最合适的厕所，你的床，杀了它的心都有。不录下来我还真不知道这二货原来是这种狗。

7. 有的狗趁你不在家，狼嚎，滚沙发，滚床单，顺便找了一个它认为最合适的厕所，你的床，杀了它的心都有。不录下来我还真不知道这二货原来是这种狗。

8. 有的狗趁你不在家，狼嚎，滚沙发，滚床单，顺便找了一个它认为最合适的厕所，你的床，杀了它的心都有。不录下来我还真不知道这二货原来是这种狗。

9. 有的狗趁你不在家，狼嚎，滚沙发，滚床单，顺便找了一个它认为最合适的厕所，你的床，杀了它的心都有。不录下来我还真不知道这二货原来是这种狗。

10. 有的狗趁你不在家，狼嚎，滚沙发，滚床单，顺便找了一个它认为最合适的厕所，你的床，杀了它的心都有。不录下来我还真不知道这二货原来是这种狗。

11. 有的狗趁你不在家，狼嚎，滚沙发，滚床单，顺便找了一个它认为最合适的厕所，你的床，杀了它的心都有。不录下来我还真不知道这二货原来是这种狗。