# Codeforces Round #496 (Div. 3)（模拟+map+思维）

## A. Tanya and Stairways（模拟）

• time limit per test：1 second
• memory limit per test：256 megabytes

Little girl Tanya climbs the stairs inside a multi-storey building. Every time Tanya climbs a stairway, she starts counting steps from 1 to the number of steps in this stairway. She speaks every number aloud. For example, if she climbs two stairways, the first of which contains 3 steps, and the second contains 4 steps, she will pronounce the numbers 1,2,3,1,2,3,4.

You are given all the numbers pronounced by Tanya. How many stairways did she climb? Also, output the number of steps in each stairway.

The given sequence will be a valid sequence that Tanya could have pronounced when climbing one or more stairways.

### Input

The first line contains nn (1≤n≤1000) — the total number of numbers pronounced by Tanya.

The second line contains integers a1,a2,…,an (1≤ai≤1000) — all the numbers Tanya pronounced while climbing the stairs, in order from the first to the last pronounced number. Passing a stairway with x steps, she will pronounce the numbers 1,2,…,x in that order.

The given sequence will be a valid sequence that Tanya could have pronounced when climbing one or more stairways.

### Output

In the first line, output t — the number of stairways that Tanya climbed. In the second line, output t numbers — the number of steps in each stairway she climbed. Write the numbers in the correct order of passage of the stairways.

### Examples

7
1 2 3 1 2 3 4
2
3 4 
4
1 1 1 1
4
1 1 1 1 
5
1 2 3 4 5
1
5 
5
1 2 1 2 1
3
2 2 1 

### 传送门

http://codeforces.com/contest/1005/problem/A

### 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int a[maxn];
int ans[maxn];

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)
ans[i] = 1;
int sum = 0;
for (int i = 1; i <= n; ++i)
{
if (a[i] == 1) // 1的数量
sum++;
else // 1后面的数字数量
ans[sum]++;
}
printf("%d\n", sum);
printf("%d", ans);
for (int i = 2; i <= sum; ++i)
printf(" %d", ans[i]);
return 0;
}

## B. Delete from the Left（模拟）

• time limit per test：1 second
• memory limit per test：256 megabytes

You are given two strings s and t. In a single move, you can choose any of two strings and delete the first (that is, the leftmost) character. After a move, the length of the string decreases by 1. You can't choose a string if it is empty.

For example:

• by applying a move to the string "where", the result is the string "here",
• by applying a move to the string "a", the result is an empty string "".

You are required to make two given strings equal using the fewest number of moves. It is possible that, in the end, both strings will be equal to the empty string, and so, are equal to each other. In this case, the answer is obviously the sum of the lengths of the initial strings.

Write a program that finds the minimum number of moves to make two given strings s and t equal.

### Input

The first line of the input contains ss. In the second line of the input contains tt. Both strings consist only of lowercase Latin letters. The number of letters in each string is between 1 and $2⋅10^5$, inclusive.

### Output

Output the fewest number of moves required. It is possible that, in the end, both strings will be equal to the empty string, and so, are equal to each other. In this case, the answer is obviously the sum of the lengths of the given strings.

### Examples

test
west
2
codeforces
yes
9
test
yes
7
b
ab
1

### Note

In the first example, you should apply the move once to the first string and apply the move once to the second string. As a result, both strings will be equal to "est".

In the second example, the move should be applied to the string "codeforces" 8 times. As a result, the string becomes "codeforces" → "es". The move should be applied to the string "yes" once. The result is the same string "yes" → "es".

In the third example, you can make the strings equal only by completely deleting them. That is, in the end, both strings will be empty.

In the fourth example, the first character of the second string should be deleted.

### 传送门

http://codeforces.com/contest/1005/problem/B

### 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
string s, t;
cin >> s >> t;
int ls = s.length(), lt = t.length();
int sum = 0, ans = ls + lt;
while (s[--ls] == t[--lt] && ls >= 0 && lt >= 0) // 记得大于等于0的条件
sum++;
printf("%d\n", ans - sum*2);
return 0;
}

## C. Summarize to the Power of Two（map）

• time limit per test：3 seconds
• memory limit per test：256 megabytes

A sequence a1,a2,…,an is called good if, for each element aiai, there exists an element ajaj (i≠j) such that ai+aj is a power of two (that is, $2^d$ for some non-negative integer d).

For example, the following sequences are good:

• [5,3,11](for example, for a1=5 we can choose a2=3. Note that their sum is a power of two. Similarly, such an element can be found for a2 and a3),
• [1,1,1,1023],
• [7,39,89,25,89],
• [].

Note that, by definition, an empty sequence (with a length of 0) is good.

For example, the following sequences are not good:

• (for a1=16, it is impossible to find another element aj such that their sum is a power of two),
• [4,16](for a1=4, it is impossible to find another element aj such that their sum is a power of two),
• [1,3,2,8,8,8](for a3=2, it is impossible to find another element aj such that their sum is a power of two).

You are given a sequence a1,a2,…,an. What is the minimum number of elements you need to remove to make it good? You can delete an arbitrary set of elements.

### Input

The first line contains the integer nn (1≤n≤120000) — the length of the given sequence.

The second line contains the sequence of integers a1,a2,…,an($1≤a_i≤10^9$).

### Output

Print the minimum number of elements needed to be removed from the given sequence in order to make it good. It is possible that you need to delete all nn elements, make it empty, and thus get a good sequence.

### Examples

6
4 7 1 5 4 9
1
5
1 2 3 4 5
2
1
16
1
4
1 1 1 1023
0

### Note

In the first example, it is enough to delete one element a4=5. The remaining elements form the sequence [4,7,1,4,9], which is good.

### 传送门

http://codeforces.com/contest/1005/problem/C

### 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 120010;
int a[maxn];
int sum;
map <int, int> M;

int main()
{
for (int i = 0; i <= 30; ++i) // 打表
sum[i] = 1 << i;
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
if (!M.count(a[i])) // 查看是否存在返回1和0
M[a[i]] = 1;
else
M[a[i]]++;
}
int ans = 0, i, j;
for (i = 0; i < n; ++i)
{
for (j = 0; j <= 30; ++j)
{
int tmp = sum[j] - a[i];
if (tmp == a[i]) // 相等时，看该数是否超过两个
{
if (M[tmp] >= 2)
break;
}
else
{
if (M[tmp]) // 看是否存在
break;
}
}
if (j == 31) // 如果没有找到
ans++;
}
printf("%d\n", ans);
return 0;
}

## D. Polycarp and Div 3（思维）

• time limit per test：3 seconds
• memory limit per test：256 megabytes

Polycarp likes numbers that are divisible by 3.

He has a huge number s. Polycarp wants to cut from it the maximum number of numbers that are divisible by 3. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after m such cuts, there will be m+1 parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by 3.

For example, if the original number is s=3121, then Polycarp can cut it into three parts with two cuts: 3|1|21. As a result, he will get two numbers that are divisible by 3.

Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.

What is the maximum number of numbers divisible by 3 that Polycarp can obtain?

### Input

The first line of the input contains a positive integer ss. The number of digits of the number ss is between 11 and $2⋅10^5$, inclusive. The first (leftmost) digit is not equal to 0.

### Output

Print the maximum number of numbers divisible by 3 that Polycarp can get by making vertical cuts in the given number s.

### Examples

3121
2
6
1
1000000000000000000000000000000000
33
201920181
4

### Note

In the first example, an example set of optimal cuts on the number is 3|1|21.

In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by 3.

In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and 33 digits 0. Each of the 3333digits 0 forms a number that is divisible by 3.

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers 00, 99, 201 and 81 are divisible by 3.

### 传送门

http://codeforces.com/contest/1005/problem/D

### 题解

1.当前数字模3为0
2.现有的数字之和模3为0（当前正在处理的）
3.有三个数字了一定可以做到模3为0

### 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
string s;
cin >> s;
int l = s.length();
int sum = 0, ans = 0, n = 0, tmp;
for (int i = 0; i < l; ++i)
{
tmp = (s[i] - '0') % 3; // 考虑取余3后的情况
sum += tmp;
n++;
if (tmp == 0 || sum % 3 == 0 || n == 3) // 一个数，两个数，三个数
{
ans++;
sum = n = 0;
}
}
printf("%d\n", ans);
return 0;
}

The end.
2018-07-11 星期三