# Codeforces Round #556 (Div. 2)

## A. Stock Arbitraging

time limit per test1 second memory limit per test256 megabytes

Welcome to Codeforces Stock Exchange! We’re pretty limited now as we currently allow trading on one stock, Codeforces Ltd. We hope you’ll still be able to make profit from the market!

In the morning, there are 𝑛n opportunities to buy shares. The 𝑖i-th of them allows to buy as many shares as you want, each at the price of 𝑠𝑖si bourles.

In the evening, there are 𝑚m opportunities to sell shares. The 𝑖i-th of them allows to sell as many shares as you want, each at the price of 𝑏𝑖bi bourles. You can’t sell more shares than you have.

It’s morning now and you possess 𝑟r bourles and no shares.

What is the maximum number of bourles you can hold after the evening?Input

The first line of the input contains three integers 𝑛,𝑚,𝑟n,m,r (1≤𝑛≤301≤n≤30, 1≤𝑚≤301≤m≤30, 1≤𝑟≤10001≤r≤1000) — the number of ways to buy the shares on the market, the number of ways to sell the shares on the market, and the number of bourles you hold now.

The next line contains 𝑛n integers 𝑠1,𝑠2,…,𝑠𝑛s1,s2,…,sn (1≤𝑠𝑖≤10001≤si≤1000); 𝑠𝑖si indicates the opportunity to buy shares at the price of 𝑠𝑖si bourles.

The following line contains 𝑚m integers 𝑏1,𝑏2,…,𝑏𝑚b1,b2,…,bm (1≤𝑏𝑖≤10001≤bi≤1000); 𝑏𝑖bi indicates the opportunity to sell shares at the price of 𝑏𝑖bibourles.Output

Output a single integer — the maximum number of bourles you can hold after the evening.
Examplesinput

3 4 11
4 2 5
4 4 5 4

output

26

input

2 2 50
5 7
4 2

output

50

Note

In the first example test, you have 1111 bourles in the morning. It’s optimal to buy 55 shares of a stock at the price of 22 bourles in the morning, and then to sell all of them at the price of 55 bourles in the evening. It’s easy to verify that you’ll have 2626 bourles after the evening.

In the second example test, it’s optimal not to take any action.

#### 签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
const int maxn=(int)1e6+100;
int a,b,re,num;
int main(){
int n,m,r;
cin>>n>>m>>r;
rep(i,1,n) cin>>a[i],re[i]=r%a[i],num[i]=r/a[i];
rep(i,1,m) cin>>b[i];
int res=0;
rep(i,1,n) rep(j,1,m){
int ans=0;
ans=b[j]*num[i]+re[i];
res=max(res,ans);
}
cout<<max(res,r)<<endl;
}


## B. Tiling Challenge

time limit per test2 seconds memory limit per test256 megabytes

One day Alice was cleaning up her basement when she noticed something very curious: an infinite set of wooden pieces! Each piece was made of five square tiles, with four tiles adjacent to the fifth center tile:

By the pieces lay a large square wooden board. The board is divided into 𝑛2n2 cells arranged into 𝑛n rows and 𝑛n columns. Some of the cells are already occupied by single tiles stuck to it. The remaining cells are free.

Alice started wondering whether she could fill the board completely using the pieces she had found. Of course, each piece has to cover exactly five distinct cells of the board, no two pieces can overlap and every piece should fit in the board entirely, without some parts laying outside the board borders. The board however was too large for Alice to do the tiling by hand. Can you help determine if it’s possible to fully tile the board?Input

The first line of the input contains a single integer 𝑛n (3≤𝑛≤503≤n≤50) — the size of the board.

The following 𝑛n lines describe the board. The 𝑖i-th line (1≤𝑖≤𝑛1≤i≤n) contains a single string of length 𝑛n. Its 𝑗j-th character (1≤𝑗≤𝑛1≤j≤n) is equal to “.” if the cell in the 𝑖i-th row and the 𝑗j-th column is free; it is equal to “#” if it’s occupied.

You can assume that the board contains at least one free cell.Output

Output YES if the board can be tiled by Alice’s pieces, or NO otherwise. You can print each letter in any case (upper or lower).
Examplesinput

3
#.#
...
#.#

output

YES

input

4
##.#
#...
####
##.#

output

NO

input

5
#.###
....#
#....
###.#
#####

output

YES

input

5
#.###
....#
#....
....#
#..##

output

NO

Note

The following sketches show the example boards and their tilings if such tilings exist:

#### 签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
const int maxn=(int)1e6+100;
int n;
char mp;
int main(){
cin>>n;
rep(i,1,n) scanf("%s",mp[i]+1);
int flag=1;
while(flag){
flag=0;
rep(i,1,n) rep(j,1,n) if(mp[i][j]=='.'){
if(mp[i][j-1]=='.'&&mp[i][j+1]=='.'&&mp[i+1][j]=='.'&&mp[i-1][j]=='.'){
flag=1;
mp[i][j]=mp[i+1][j]=mp[i-1][j]=mp[i][j+1]=mp[i][j-1]='#';
}
}
}
rep(i,1,n) rep(j,1,n) if(mp[i][j]=='.') return puts("NO"),0;
return puts("YES"),0;
}


## C. Prefix Sum Primes

time limit per test1 second memory limit per test256 megabytes

We’re giving away nice huge bags containing number tiles! A bag we want to present to you contains 𝑛n tiles. Each of them has a single number written on it — either 11 or 22.

However, there is one condition you must fulfill in order to receive the prize. You will need to put all the tiles from the bag in a sequence, in any order you wish. We will then compute the sums of all prefixes in the sequence, and then count how many of these sums are prime numbers. If you want to keep the prize, you will need to maximize the number of primes you get.

Can you win the prize? Hurry up, the bags are waiting!Input

The first line of the input contains a single integer 𝑛n (1≤𝑛≤2000001≤n≤200000) — the number of number tiles in the bag. The following line contains 𝑛n space-separated integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (𝑎𝑖∈{1,2}ai∈{1,2}) — the values written on the tiles.Output

Output a permutation 𝑏1,𝑏2,…,𝑏𝑛b1,b2,…,bn of the input sequence (𝑎1,𝑎2,…,𝑎𝑛)(a1,a2,…,an) maximizing the number of the prefix sums being prime numbers. If there are multiple optimal permutations, output any.
Examplesinput

5
1 2 1 2 1

output

1 1 1 2 2

input

9
1 1 2 1 1 1 2 1 1

output

1 1 1 2 1 1 1 2 1

Note

The first solution produces the prefix sums 1,2,3,5,71,2,3,5,7 (four primes constructed), while the prefix sums in the second solution are 1,2,3,5,6,7,8,10,111,2,3,5,6,7,8,10,11 (five primes). Primes are marked bold and blue. In each of these cases, the number of produced primes is maximum possible.

#### 签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
const int maxn=(int)2e5+100;
int n,f1,f2;
int main(){
cin>>n;
rep(i,1,n){
int x;scanf("%d",&x);
if(x==1) f1++;
else f2++;
}
if(f1&&f2){
printf("2 1 ");
f1--;f2--;
}
rep(i,1,f2) printf("2 ");
rep(i,1,f1) printf("1 ");
}


## D. Three Religions

time limit per test3 seconds memory limit per test256 megabytes

During the archaeological research in the Middle East you found the traces of three ancient religions: First religion, Second religion and Third religion. You compiled the information on the evolution of each of these beliefs, and you now wonder if the followers of each religion could coexist in peace.

The Word of Universe is a long word containing the lowercase English characters only. At each moment of time, each of the religion beliefs could be described by a word consisting of lowercase English characters.

The three religions can coexist in peace if their descriptions form disjoint subsequences of the Word of Universe. More formally, one can paint some of the characters of the Word of Universe in three colors: 11, 22, 33, so that each character is painted in at most one color, and the description of the 𝑖i-th religion can be constructed from the Word of Universe by removing all characters that aren’t painted in color 𝑖i.

The religions however evolve. In the beginning, each religion description is empty. Every once in a while, either a character is appended to the end of the description of a single religion, or the last character is dropped from the description. After each change, determine if the religions could coexist in peace.Input

The first line of the input contains two integers 𝑛,𝑞n,q (1≤𝑛≤1000001≤n≤100000, 1≤𝑞≤10001≤q≤1000) — the length of the Word of Universe and the number of religion evolutions, respectively. The following line contains the Word of Universe — a string of length 𝑛n consisting of lowercase English characters.

Each of the following line describes a single evolution and is in one of the following formats:

• + 𝑖i 𝑐c (𝑖∈{1,2,3}i∈{1,2,3}, 𝑐∈{𝚊,𝚋,…,𝚣}c∈{a,b,…,z}: append the character 𝑐c to the end of 𝑖i-th religion description.
• – 𝑖i (𝑖∈{1,2,3}i∈{1,2,3}) – remove the last character from the 𝑖i-th religion description. You can assume that the pattern is non-empty.

You can assume that no religion will have description longer than 250250 characters.Output

Write 𝑞q lines. The 𝑖i-th of them should be YES if the religions could coexist in peace after the 𝑖i-th evolution, or NO otherwise.

You can print each character in any case (either upper or lower).
Examplesinput

6 8
abdabc
+ 1 a
+ 1 d
+ 2 b
+ 2 c
+ 3 a
+ 3 b
+ 1 c
- 2

output

YES
YES
YES
YES
YES
YES
NO
YES

input

6 8
abbaab
+ 1 a
+ 2 a
+ 3 a
+ 1 b
+ 2 b
+ 3 b
- 1
+ 2 z

output

YES
YES
YES
YES
YES
NO
YES
NO

Note

In the first example, after the 6th evolution the religion descriptions are: ad, bc, and ab. The following figure shows how these descriptions form three disjoint subsequences of the Word of Universe:

#### 稍微暴力一点，用dp[i][j][k]表示三个串分别匹配到i,j,k的时候组成的子序列的最后一个字符在str中的位置，如果dp[len1][len2]][len3]>=n则输出NO状态转移方程为：if(i) dp[i][j][k]=min(dp[i][j][k],Next[dp[i-1][j][k]+1][s[i-1]-'a']); if(j) dp[i][j][k]=min(dp[i][j][k],Next[dp[i][j-1][k]+1][s[j-1]-'a']); if(k) dp[i][j][k]=min(dp[i][j][k],Next[dp[i][j][k-1]+1][s[k-1]-'a']);

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
const int maxn=(int)1e5+100;
int len,q,Next[maxn],dp;
string s,str;
void get_next(){
dp=-1;
rep(i,0,25) Next[len][i]=Next[len+1][i]=len;
dep(pos,len-1,0) rep(i,0,25)
Next[pos][i]=(str[pos]==i+'a'?pos:Next[pos+1][i]);
}
int main(){
ios::sync_with_stdio(0);
cin>>len>>q>>str;
get_next();
while(q--){
char op;int id;
int mi,mx;
cin>>op>>id; id--;
if(op=='+'){
char t;cin>>t;
s[id]+=t;
rep(i,0,2) mi[i]=0,mx[i]=s[i].length();
mi[id]=mx[id];
rep(i,mi,mx) rep(j,mi,mx) rep(k,mi,mx){
dp[i][j][k]=len;
if(i) dp[i][j][k]=min(dp[i][j][k],Next[dp[i-1][j][k]+1][s[i-1]-'a']);
if(j) dp[i][j][k]=min(dp[i][j][k],Next[dp[i][j-1][k]+1][s[j-1]-'a']);
if(k) dp[i][j][k]=min(dp[i][j][k],Next[dp[i][j][k-1]+1][s[k-1]-'a']);
}
}
else s[id].pop_back();
puts(dp[s.length()][s.length()][s.length()]<len?"YES":"NO");
}
}