【题解】test

1
2


1136 A Delayed Palindrome

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
const int mxn = 1e5 + 5;
char s[mxn], t[mxn];

void add(char *s, char *t)
{
int len=strlen(s), p=0;
for(int i=0; i<len; i++){
int x = s[i]-'0' + t[i]-'0' + p;
p = x / 10;
s[i] = x % 10 + '0';
}
if(p)
s[len++]='1';
s[len]='\0';
reverse(s, s+len);
}

int main()
{
scanf("%s", s);

int num = 0;
while(1)
{
reverse_copy(s, s+strlen(s), t);
if(strcmp(s, t) == 0){
printf("%s is a palindromic number.\n", s);
break;
}
printf("%s + %s = ", s, t);
add(s, t);
printf("%s\n", s);
if(++num >= 10){
printf("Not found in 10 iterations.\n");
break;
}
}
return 0;
}
const int mxn = 1e5 + 5;
char s[mxn], t[mxn];

void add(char *s, char *t)
{
int len=strlen(s), p=0;
for(int i=0; i<len; i++){
int x = s[i]-'0' + t[i]-'0' + p;
p = x / 10;
s[i] = x % 10 + '0';
}
if(p)
s[len++]='1';
s[len]='\0';
reverse(s, s+len);
}

int main()
{
scanf("%s", s);

int num = 0;
while(1)
{
reverse_copy(s, s+strlen(s), t);
if(strcmp(s, t) == 0){
printf("%s is a palindromic number.\n", s);
break;
}
printf("%s + %s = ", s, t);
add(s, t);
printf("%s\n", s);
if(++num >= 10){
printf("Not found in 10 iterations.\n");
break;
}
}
return 0;
}
// 水题重复

1137 Final Grading

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
const int inf = 0x3f3f3f3f;
const int mxn = 1e5 + 5;

struct P{
string name;
int gp, gm, gf, sum, f;
P():gm(-1), gf(-1), sum(0){}
}a[mxn];

map<string, int> mp;

int main()
{
int p, n, m, num=1;
scanf("%d %d %d", &p, &n, &m);
for(int i=0; i<p; i++){
string s; int t;
cin >> s >> t;
if(mp[s] == 0 && t >= 200){
mp[s] = num;
a[num].name = s;
a[num].gp = t;
num++;
}
}
for(int i=0; i<n; i++){
string s; int t;
cin >> s >> t;
int x = mp[s];
if(x){
a[x].gm = t;
a[x].sum = t;
}
}
int ans = 0;
for(int i=0; i<m; i++){
string s; int t;
cin >> s >> t;
int x = mp[s];
if(x){
a[x].gf = t;
if(t < a[x].gm)
a[x].sum = (int)(0.6*t + 0.4*a[x].gm + 0.5);
else
a[x].sum = t;

if(a[x].sum>=60){
a[x].f = 1;
ans++;
}
}
}
sort(a+1, a+num+1, [](const P &a, const P &b){
if(a.f != b.f) return a.f > b.f;
if(a.sum != b.sum) return a.sum > b.sum;
return a.name < b.name;
});
for(int i=1; i<=ans; i++){
printf("%s %d %d %d %d\n", a[i].name.c_str(), a[i].gp, a[i].gm, a[i].gf, a[i].sum);
}

return 0;
}
// 水题

1138 Postorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int inf = 0x3f3f3f3f;
const int mxn = 1e5 + 5;

int in[mxn], pre[mxn], flag;

void solve(int l, int r, int rt){
if(l > r || flag) return;
int i=l;
while(in[i]!=pre[rt]) i++;
solve(l, i-1, rt+1);
solve(i+1, r, rt+1+i-l);
if(flag == 0){
printf("%d\n", in[i]);
flag = 1;
}
}

int main()
{
int n; scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &pre[i]);
for(int i=1; i<=n; i++)
scanf("%d", &in[i]);

solve(1, n, 1);
return 0;
}
// 树的遍历

1140 Look-and-say Sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
string s; int n, j;
cin >> s >> n;

for (int k=1; k<n; k++)
{
string t;
for (int i=0; i<s.length(); i=j)
{
for (j=i; j<s.length() && s[j]==s[i]; j++);
t += s[i] + to_string(j - i);
}
s = t;
}
printf("%s\n", s.c_str());

return 0;
}
// 水题重复

1141 PAT Ranking of Institutions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
typedef double DB;
const int mxn = 1e5 + 5;

struct P{
string s;
DB sum;
int num;
}a[mxn];

bool cmp(P a, P b)
{
if(a.sum != b.sum)
return a.sum > b.sum;
if(a.num != b.num)
return a.num < b.num;
return a.s < b.s;
}

int main()
{
int n; scanf("%d", &n);

map<string, int> mmp;
string x, y;
int cnt = 0;
DB t;

for (int i=0; i<n; i++)
{
cin >> x >> t >> y;
for(int j=0; j<y.length(); j++)
y[j] = tolower(y[j]);

if(mmp.count(y)==0)
{
mmp[y] = cnt++;
a[mmp[y]].s = y;
}

if(x.at(0) == 'B')
t /= 1.5;
else if(x.at(0) == 'T')
t *= 1.5;

a[mmp[y]].sum += t;
a[mmp[y]].num++;
}
for(int i=0; i<cnt; i++)
a[i].sum = floor(a[i].sum);

printf("%d\n", cnt);
sort(a, a+cnt, cmp);

int rank = 1;
for(int i=0; i<cnt; i++)
{
if(i && a[i-1].sum != a[i].sum)
rank = i+1;
printf("%d %s %.0lf %d\n", rank, a[i].s.c_str(), a[i].sum, a[i].num);
}

return 0;
}
// 水题重复

1142 Maximal Clique

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
const int inf = 0x3f3f3f3f;
const int mxn = 1e3 + 5;

int g[mxn][mxn];
int v[mxn], vis[mxn];

int main()
{
int n, m; scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++){
int u, v;
scanf("%d %d", &u, &v);
g[u][v] = 1;
g[v][u] = 1;
}
int k; scanf("%d", &k);
while(k--){
int t; scanf("%d", &t);
for(int i=0; i<t; i++){
scanf("%d", &v[i]);
vis[v[i]] = 1;
}
int isClq = 1;
for(int i=0; i<t; i++){
for(int j=i+1; j<t; j++){
if(g[v[i]][v[j]] == 0){
isClq = 0;
break;
}
}
if(isClq == 0) break;
}
if(isClq == 0){
printf("Not a Clique\n");
continue;
}
int isMax = 1;
for(int i=1; i<=n; i++){
if(vis[i]) continue;
int f = 1;
for(int j=0; j<t; j++){
if(g[i][v[j]] == 0){
f = 0;
break;
}
}
if(f) isMax = 0;
if(isMax == 0) break;
}
if(isMax){
printf("Yes\n");
}else{
printf("Not Maximal\n");
}
for(int i=0; i<t; i++)
vis[v[i]] = 0;
}
return 0;
}
// 最大团

1143 Lowest Common Ancestor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int inf = 0x3f3f3f3f;
const int mxn = 1e6 + 5;

map<int, int> mp;
int pre[mxn];

int main()
{
int n, m; scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++){
scanf("%d", &pre[i]);
mp[pre[i]] = i;
}
while(n--){
int u, v, id; scanf("%d %d", &u, &v);
for(int i=1; i<=m; i++){
id = pre[i];
if (u==id || v==id || (u<id)^(v<id)==1) break;
}
if (mp[u]==0 && mp[v]==0)
printf("ERROR: %d and %d are not found.\n", u, v);
else if (mp[u]==0 || mp[v]==0)
printf("ERROR: %d is not found.\n", (mp[u] ? v : u));
else if (u==id || v==id)
printf("%d is an ancestor of %d.\n", id, (u==id ? v : u));
else
printf("LCA of %d and %d is %d.\n", u, v, id);
}
return 0;
}
// 树的遍历 LCA 二叉搜索树

1144 The Missing Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int mxn = 1e6 + 5;

int a[mxn];

int main()
{
int n; scanf("%d", &n);
for(int i=0; i<n; i++){
int x; scanf("%d", &x);
if(x >= 0 && x < 100005)
a[x] = 1;
}
for(int i=1; i<=100005; i++){
if(a[i] == 0){
printf("%d\n", i);
break;
}
}
return 0;
}
// 水题

1145 Hashing - Average Search Time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const int inf = 0x3f3f3f3f;
const int mxn = 1e5+ 5;

bool isPrime(int n)
{
if(n < 2) return 0;
if(n == 2 || n == 3) return 1;
if(n % 6 != 1 && n % 6 != 5) return 0;

int m = (int)sqrt(n);
for(int i=5; i<=m; i+=6){
if(n%i==0 || n%(i+2)==0)
return 0;
}
return 1;
}

int h[mxn];

int main()
{
int s, n, m;
scanf("%d %d %d", &s, &n, &m);
while(!isPrime(s)) s++;
for(int i=0; i<n; i++){
int x; scanf("%d", &x);
int f = 1;
for(int j=0; j<=s; j++){
int pos = (x+j*j) % s;
if(h[pos] == 0){
h[pos] = x;
f = 0;
break;
}
}
if(f) printf("%d cannot be inserted.\n", x);
}
int ans = 0;
for(int i=0; i<m; i++){
int x; scanf("%d", &x);
for(int j=0; j<=s; j++){
ans++;
int pos = (x+j*j) % s;
if(h[pos]==x || h[pos]==0) break;
}
}
printf("%.1lf\n", 1.0*ans/m);
return 0;
}
// 哈希冲突

1146 Topological Order

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
const int inf = 0x3f3f3f3f;
const int mxn = 1e5+ 5;

struct E{
int to, next;
}e[mxn];

int H[mxn], tot;

void add(int from, int to){
e[tot] = {to, H[from]};
H[from] = tot++;
}

void graph_init(int n){
for(int i=1; i<=n; i++)
H[i] = -1;
tot = 0;
}

int in[mxn], t[mxn];

int main()
{
int n, m; scanf("%d %d", &n, &m);
graph_init(n);
for(int i=0; i<m; i++){
int u, v; scanf("%d %d", &u, &v);
add(u, v);
in[v]++;
}
int nf=0, k;
scanf("%d", &k);
for(int cs=0; cs<k; cs++)
{
for(int i=1; i<=n; i++) t[i] = in[i];
int f = 1;
for(int i=1; i<=n; i++){
int u; scanf("%d", &u);
if(t[u]) f = 0;
for(int j=H[u]; ~j; j=e[j].next)
t[e[j].to]--;
}
if(f == 0){
if(nf) printf(" ");
else nf = 1;
printf("%d", cs);
}
}
printf("\n");
return 0;
}
// 拓扑序

1147 Heaps

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#define ls ((rt)<<1)
#define rs ((rt)<<1|1)
const int inf = 0x3f3f3f3f;
const int mxn = 1e3 + 5;

int a[mxn];
void dfs(int rt, int m){
if(rt > m) return;
dfs(ls, m);
dfs(rs, m);
printf("%d%c", a[rt], (rt==1 ? '\n' : ' '));
}

int main()
{
int n, m; scanf("%d %d", &n, &m);
while(n--){
for(int i=1; i<=m; i++)
scanf("%d", &a[i]);
int ismx = 1, ismi = 1;
for(int i=2; i<=m; i++){
if(a[i/2] > a[i]) ismi = 0;
if(a[i/2] < a[i]) ismx = 0;
}
if(ismx){
printf("Max Heap\n");
}else if(ismi){
printf("Min Heap\n");
}else{
printf("Not Heap\n");
}
dfs(1, m);
}

return 0;
}
// 树的遍历

1148 Werewolf - Simple Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define Sg(u) ((u) > eps ? 1 : ((u) < -eps ? -1 : 0))
#define Abs(u) (Sg(u) >= 0 ? (u) : -(u))
const DB eps = 1e-8;

const int mxn = 1e5 + 5;

int a[mxn], ok[mxn], lie[mxn];

int main()
{
int n; scanf("%d", &n);

for (int i=1; i<=n; i++)
scanf("%d", &a[i]);

for(int i=1; i<=n; i++)
{
for(int j=i+1; j<=n; j++)
{
for(int k=1; k<=n; k++)
ok[k] = 1;
ok[i] = ok[j] = -1;

int num = 0;
for(int k=1; k<=n; k++)
{
if(a[k] * ok[Abs(a[k])] < 0)
lie[num++] = k;
}

if(num == 2 && ok[lie[0]] + ok[lie[1]] == 0)
{
printf("%d %d\n", i, j);
return 0;
}
}
}
printf("No Solution\n");

return 0;
}
// 水题重复

1149 Dangerous Goods Packaging

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const int mxn = 1e5 + 5;

int a[mxn];

int main()
{
int n, m;
scanf("%d %d", &n, &m);

map<int, vector<int> > mmp;

for (int i=0; i<n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
mmp[x].push_back(y);
mmp[y].push_back(x);
}

while (m--)
{
memset(a, 0, sizeof a);
int k; scanf("%d", &k);

vector<int> v(k);
for (int i=0; i<k; i++)
{
scanf("%d", &v[i]);
a[v[i]] = 1;
}

int f = 0;
for (int i=0; i<v.size(); i++)
{
for (int j=0; j<mmp[v[i]].size(); j++)
{
if (a[mmp[v[i]][j]])
{
f = 1;
break;
}
}
if(f) break;
}
printf("%s\n", f ? "No" :"Yes");
}

return 0;
}
// 水题重复

1150 Travelling Salesman Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const int inf = 0x3f3f3f3f;
const int mxn = 1e3 + 5;

int g[mxn][mxn];
int a[mxn];

int main()
{
int n, m; scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++){
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
g[u][v] = w;
g[v][u] = w;
}
int ans = inf, id = 0;
int k; scanf("%d", &k);
for(int cs=1; cs<=k; cs++)
{
int num; scanf("%d", &num);
set<int> s;
for(int i=0; i<num; i++){
scanf("%d", &a[i]);
s.insert(a[i]);
}
int f = 1, sum = 0;
for(int i=0; i<num-1; i++){
if(g[a[i]][a[i+1]] == 0) f = 0;
sum += g[a[i]][a[i+1]];
}
if(f && a[0]==a[num-1] && s.size()==n){
if(num == n+1)
printf("Path %d: %d (TS simple cycle)\n", cs, sum);
else
printf("Path %d: %d (TS cycle)\n", cs, sum);
if(ans > sum)
ans = sum, id = cs;
}else if(f){
printf("Path %d: %d (Not a TS cycle)\n", cs, sum);
}else{
printf("Path %d: NA (Not a TS cycle)\n", cs);
}
}
printf("Shortest Dist(%d) = %d\n", id, ans);

return 0;
}
// 水题

1151 LCA in a Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const int inf = 0x3f3f3f3f;
const int mxn = 1e6 + 5;

map<int, int> mp;
int in[mxn], pre[mxn];

void solve(int l, int r, int rt, int u, int v){
if(l > r) return;
int id = mp[pre[rt]], a = mp[u], b = mp[v];
if(a < id && b < id){
solve(l, id-1, rt+1, u, v);
}else if(a > id && b > id){
solve(id+1, r, rt+1+id-l, u, v);
}else if(a == id){
printf("%d is an ancestor of %d.\n", u, v);
}else if(b == id){
printf("%d is an ancestor of %d.\n", v, u);
}else if((a < id) ^ (b < id) == 1){
printf("LCA of %d and %d is %d.\n", u, v, in[id]);
}
}

int main()
{
int n, m; scanf("%d %d", &n, &m);
for(int i=1; i<=m; i++){
scanf("%d", &in[i]);
mp[in[i]] = i;
}
for(int i=1; i<=m; i++)
scanf("%d", &pre[i]);

while(n--){
int u, v; scanf("%d %d", &u, &v);
if(mp[u]==0 && mp[v]==0){
printf("ERROR: %d and %d are not found.\n", u, v);
}else if(mp[u]==0 || mp[v]==0){
printf("ERROR: %d is not found.\n", mp[u] ? v : u);
}else{
solve(1, m, 1, u, v);
}
}
return 0;
}

// 树的遍历 LCA

1152 Google Recruitment

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const int mxn = 1e5 + 5;
char s[mxn];

bool isPrime(int n)
{
if (n == 0 || n == 1) return 0;
if (n == 2 || n == 3) return 1;
if (n % 6 != 1 && n % 6 != 5) return 0;

int m = sqrt(n);
for (int i = 5; i <= m; i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return 0;
}
return 1;
}

int main()
{
int L, K;
scanf("%d %d %s", &L, &K, s);

int f = 1;
for(int i=0; i<=L-K; i++)
{
int t; char a[15];
memset(a, 0, sizeof a);
strncpy(a, s+i, K);
sscanf(a, "%d", &t);
if(isPrime(t))
{
printf("%s\n", a);
f = 0;
break;
}
}

if(f)
printf("404\n");

return 0;
}
// 水题重复

1153 Decode Registration Card of PAT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
const int mxn = 1e4 + 5;

struct P{
char s[20];
int x, t;

bool operator < (const P &x) const
{
if(t != x.t)
return t > x.t;
return strcmp(s, x.s) < 0;
}
}a[mxn], ans[mxn];

struct P2{
int s, cnt;

bool operator < (const P2 &x) const
{
if(cnt != x.cnt)
return cnt > x.cnt;
return s < x.s;
}
}b[mxn];

int idx[mxn];

int main()
{
int n, m;
scanf("%d %d", &n, &m);

for(int i=0; i<n; i++){
scanf("%s %d", a[i].s, &a[i].t);
sscanf(a[i].s+1, "%3d", &a[i].x);
}
sort(a, a+n);

for(int cs=1; cs<=m; cs++)
{
int c; char g[10];
scanf("%d %s", &c, g);
printf("Case %d: %d %s\n", cs, c, g);

int num=0, sum=0;
if(c == 1)
{
for(int i=0; i<n; i++)
{
if(a[i].s[0] == g[0]){
printf("%s %d\n", a[i].s, a[i].t);
num++;
}
}
if(num == 0)
printf("NA\n");
continue;
}

if(c == 2)
{
for(int i=0; i<n; i++)
{
if(strncmp(a[i].s+1, g, 3) == 0)
sum += a[i].t, num++;
}
if(num)
printf("%d %d\n", num, sum);
else
printf("NA\n");
continue;
}

if(c == 3)
{
for(int i=0; i<n; i++)
{
if(strncmp(a[i].s+4, g, 6) == 0)
{
int x = a[i].x;
if(idx[x] == 0){
idx[x] = ++num;
b[idx[x]].s = x;
}
b[idx[x]].cnt++;
}
}
if(num)
{
sort(b+1, b+num+1);
for(int i=1; i<=num; i++)
{
printf("%03d %d\n", b[i].s, b[i].cnt);
b[i].cnt = idx[b[i].s] = 0;
}
}
else
printf("NA\n");
}
}

return 0;
}
// 水题重复

1154 Vertex Coloring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int inf = 0x3f3f3f3f;
const int mxn = 1e6 + 5;

int a[mxn], u[mxn], v[mxn];

int main()
{
int n, m; scanf("%d %d", &n, &m);
for(int i=0; i<m; i++){
scanf("%d %d", &u[i], &v[i]);
}
int k; scanf("%d", &k);
while(k--){
set<int> s;
for(int i=0; i<n; i++){
scanf("%d", &a[i]);
s.insert(a[i]);
}
int f = 1;
for(int i=0; i<m; i++){
if(a[u[i]] == a[v[i]]){
f = 0;
break;
}
}
if(f){
printf("%d-coloring\n", s.size());
}else{
printf("No\n");
}
}
return 0;
}
// 水题

1155 Heap Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#define ls ((rt)<<1)
#define rs ((rt)<<1|1)
const int inf = 0x3f3f3f3f;
const int mxn = 1e6 + 5;

int a[mxn];
int p[mxn], num;

void dfs(int rt, int n){
if(ls > n && rs > n){
if(rt <= n)
for(int i=0; i<num; i++){
printf("%d%c", p[i], (i==num-1 ? '\n' : ' '));
}
return ;
}
p[num++] = a[rs];
dfs(rs, n);
num--;

p[num++] = a[ls];
dfs(ls, n);
num--;
}

int main()
{
int n; scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
}
p[num++] = a[1];
dfs(1, n);

int ismx = 1, ismi = 1;
for(int i=2; i<=n; i++){
if(a[i/2] < a[i]) ismx = 0;
if(a[i/2] > a[i]) ismi = 0;
}
if(ismx)
printf("Max Heap\n");
else if(ismi)
printf("Min Heap\n");
else
printf("Not Heap\n");

return 0;
}
// 树的遍历
_/_/_/_/_/ EOF _/_/_/_/_/