CodeForces Round #527 (Div3) D1. Great Vova Wall (Version 1)
http://codeforces.com/contest/1092/problem/D1
Vova's family is building the Great Vova Wall (named by Vova himself). Vova's parents, grandparents, grand-grandparents contributed to it. Now it's totally up to Vova to put the finishing touches.
The current state of the wall can be respresented by a sequence aa of nn integers, with aiai being the height of the ii-th part of the wall.
Vova can only use 2×12×1 bricks to put in the wall (he has infinite supply of them, however).
Vova can put bricks horizontally on the neighboring parts of the wall of equal height. It means that if for some ii the current height of part iiis the same as for part i+1i+1, then Vova can put a brick there and thus increase both heights by 1. Obviously, Vova can't put bricks in such a way that its parts turn out to be off the borders (to the left of part 11 of the wall or to the right of part nn of it).
The next paragraph is specific to the version 1 of the problem.
Vova can also put bricks vertically. That means increasing height of any part of the wall by 2.
Vova is a perfectionist, so he considers the wall completed when:
- all parts of the wall has the same height;
- the wall has no empty spaces inside it.
Can Vova complete the wall using any amount of bricks (possibly zero)?
The first line contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of parts in the wall.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the initial heights of the parts of the wall.
Print "YES" if Vova can complete the wall using any amount of bricks (possibly zero).
Print "NO" otherwise.
5
2 1 1 2 5
YES
3
4 5 3
YES
2
10 10
YES
3
1 2 3
NO
In the first example Vova can put a brick on parts 2 and 3 to make the wall [2,2,2,2,5][2,2,2,2,5] and then put 3 bricks on parts 1 and 2 and 3 bricks on parts 3 and 4 to make it [5,5,5,5,5][5,5,5,5,5].
In the second example Vova can put a brick vertically on part 3 to make the wall [4,5,5][4,5,5], then horizontally on parts 2 and 3 to make it [4,6,6][4,6,6] and then vertically on part 1 to make it [6,6,6][6,6,6].
In the third example the wall is already complete.
代码:
#include <bits/stdc++.h>
using namespace std; int N;
stack<int> s; int main() {
scanf("%d", &N);
for(int i = 0; i < N; i ++) {
int x;
scanf("%d", &x);
if(s.empty())
s.push(x);
else {
if(abs(s.top() - x) % 2)
s.push(x);
else s.pop();
}
} if(s.size() > 1) printf("NO\n");
else printf("YES\n");
return 0;
}
相邻的两个墙的高度差是 2 的倍数就可以了
最新文章
- Openfire的启动过程与session管理
- javaSE之Object及hashcode等相关知识
- WebKit渲染基础(转载 学习中。。。)
- 【oracle】oracle函数-数值函数
- 计算机网络-ip地址聚合后可用的地址数
- __unset()魔术方法 删除类内私有属性
- 使用OllyDbg从零开始Cracking CHM
- Object类可以接受引用类型
- CSS小全
- 三种方法,刷新 Android 的 MediaStore!让你保存的图片立即出现在相册里!
- Jeff Atwood质疑iPhone的单键设计
- memcache 和 redis 之间的区别
- golang 使用匿名结构体的问题
- HBase海量数据存储
- 源码分享篇:使用Python进行QQ批量登录
- 截取字符串中最后一个中文词语(MS SQL)
- if语句格式及流程
- Please restart this script from an administrative PowerShell
- 20155310 《Java程序设计》实验四 (Android程序设计)实验报告
- 监听Entity Framework生成的Sql语句