第二十七次codeforces竞技结束 #288 Div 2
Problems # Name A Pasha and Pixels standard input/output 2 s, 256 MB x3234 B Anton and currency you all know standard input/output 0.5 s, 256 MB x2848 C Anya and Ghosts standard input/output 2 s, 256 MB x1671 这次出了前三题,原为第三位的Av
Problems
# | Name | ||
---|---|---|---|
A |
Pasha and Pixels
standard input/output 2 s, 256 MB |
x3234 | |
B |
Anton and currency you all know
standard input/output 0.5 s, 256 MB |
x2848 | |
C |
Anya and Ghosts
standard input/output 2 s, 256 MB |
x1671 |
这次出了前三题,原为第三位的Avator加了100来分变成第二了,这下终于三个ID都1650+了,可喜可贺,希望能多撑几天吧……
A. Pasha and Pixels
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Pasha loves his phone and also putting his hair up... But the hair is now irrelevant.
Pasha has installed a new game to his phone. The goal of the game is following. There is a rectangular field consisting of n row with mpixels in each row. Initially, all the pixels are colored white. In one move, Pasha can choose any pixel and color it black. In particular, he can choose the pixel that is already black, then after the boy's move the pixel does not change, that is, it remains black. Pasha loses the game when a 2?×?2 square consisting of black pixels is formed.
Pasha has made a plan of k moves, according to which he will paint pixels. Each turn in his plan is represented as a pair of numbers iand j, denoting respectively the row and the column of the pixel to be colored on the current move.
Determine whether Pasha loses if he acts in accordance with his plan, and if he does, on what move the 2?×?2 square consisting of black pixels is formed.
Input
The first line of the input contains three integers n,?m,?k (1?≤?n,?m?≤?1000, 1?≤?k?≤?105) — the number of rows, the number of columns and the number of moves that Pasha is going to perform.
The next k lines contain Pasha's moves in the order he makes them. Each line contains two integers i and j (1?≤?i?≤?n, 1?≤?j?≤?m), representing the row number and column number of the pixel that was painted during a move.
Output
If Pasha loses, print the number of the move when the 2?×?2 square consisting of black pixels is formed.
If Pasha doesn't lose, that is, no 2?×?2 square consisting of black pixels is formed during the given k moves, print 0.
Sample test(s)
input
2 2 4 1 1 1 2 2 1 2 2
output
4
input
2 3 6 2 3 2 2 1 3 2 2 1 2 1 1
output
5
input
5 3 7 2 3 1 2 1 1 4 1 3 1 5 3 3 2
output
0
给你一个n*m的棋盘,每次你走到的格子都会被涂黑,接下来有k步,每一步都告诉你我这步走的是哪一个格子(Row/Col坐标),要求输出在第几步时第一次出现了2X2的黑色正方形,如果走完了都没出现,则输出0。
看了看数据范围,似乎……模拟完全无压呢
我们就真的给一个棋盘,每走一步我们就把这个格子 mp[a][b]=1 标记一下,然后找左上右上左下右下,这四个2X2的正方形是不是全黑,是的话输出然后return,不是的话就继续咯~
Code:
#include#include #include #include #include #include #include #include using namespace std; #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a) b; } int mp[1002][1002]={0}; bool judge(int r,int c) { if(mp[r-1][c]==1) { if(mp[r][c-1]==1) { if(mp[r-1][c-1]==1)return true; } if(mp[r][c+1]==1) { if(mp[r-1][c+1]==1)return true; } } if(mp[r+1][c]==1) { if(mp[r][c-1]==1) { if(mp[r+1][c-1]==1)return true; } if(mp[r][c+1]==1) { if(mp[r+1][c+1]==1)return true; } } return false; } int main() { int n,m,k; cin>>n>>m>>k; for(int i=1;i
B. Anton and currency you all know
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Berland, 2016. The exchange rate of currency you all know against the burle has increased so much that to simplify the calculations, its fractional part was neglected and the exchange rate is now assumed to be an integer.
Reliable sources have informed the financier Anton of some information about the exchange rate of currency you all know against the burle for tomorrow. Now Anton knows that tomorrow the exchange rate will be an even number, which can be obtained from the present rate by swapping exactly two distinct digits in it. Of all the possible values that meet these conditions, the exchange rate for tomorrow will be the maximum possible. It is guaranteed that today the exchange rate is an odd positive integer n. Help Anton to determine the exchange rate of currency you all know for tomorrow!
Input
The first line contains an odd positive integer n — the exchange rate of currency you all know for today. The length of number n's representation is within range from 2 to 105, inclusive. The representation of n doesn't contain any leading zeroes.
Output
If the information about tomorrow's exchange rate is inconsistent, that is, there is no integer that meets the condition, print ?-?1.
Otherwise, print the exchange rate of currency you all know against the burle for tomorrow. This should be the maximum possible number of those that are even and that are obtained from today's exchange rate by swapping exactly two digits. Exchange rate representation should not contain leading zeroes.
Sample test(s)
input
527
output
572
input
4573
output
3574
input
1357997531
output
-1
给一个很长的数字,至少两位数,最多10的五次方位的一个奇数,让你调换其中两个数位,将其变为可变的各种选择中最大的偶数并输出,如果做不到则输出-1。
很显然,最后一位决定了奇偶,所以调换的两位中确定了一位是末位,然后,做不到的意思就是数字中没有偶数数字,特例排除后我们来考虑如何最大。
因为数字太大,所以我们不能直接加减甚至无法记录最大值,但是我们在纸上写一写就能发现,很明显调换后与调换前的差一定是一个 A99999...999B 的数,而AB作为一个两位数来看就是两个调换位调换前后的两位数的差,即 10*B+A-10*A-B=9*(B-A) ,连9我们都不必要了…… 我们就简单的通过正负(zf)、9的个数(digit)和差值(sub)来记录就可以啦~ 话说我为啥要把正负提出来!!! 直接正负和差值用一个int不就可以了么!我真傻……真的……
Code:
#include
推荐阅读
-
第二十次codeforces竞技结束 #276 Div 2
-
第一次codeforces竞技结束 #238 Div 2
-
第二十次codeforces竞技结束 #276 Div 2
-
第七次codeforces竞技结束 #258 Div 2
-
第一次codeforces竞技结束 #238 Div 2
-
第二十七次codeforces竞技结束 #288 Div 2
-
第七次codeforces竞技结束 #258 Div 2
-
第二十次codeforces竞技结束 #276 Div 2_html/css_WEB-ITnose
-
第二十八次codeforces竞技结束 #291 Div 2
-
第三十五次codeforces竞技结束 #483 Div 2