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[35],b[35],re[35],num[35];
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[55][55];
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[0][i-1]-'a']); if(j) dp[i][j][k]=min(dp[i][j][k],Next[dp[i][j-1][k]+1][s[1][j-1]-'a']); if(k) dp[i][j][k]=min(dp[i][j][k],Next[dp[i][j][k-1]+1][s[2][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][27],dp[255][255][255];
string s[3],str;
void get_next(){
	dp[0][0][0]=-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[3],mx[3];
		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[0],mx[0]) rep(j,mi[1],mx[1]) rep(k,mi[2],mx[2]){
				dp[i][j][k]=len;
				if(i) dp[i][j][k]=min(dp[i][j][k],Next[dp[i-1][j][k]+1][s[0][i-1]-'a']);
				if(j) dp[i][j][k]=min(dp[i][j][k],Next[dp[i][j-1][k]+1][s[1][j-1]-'a']);
				if(k) dp[i][j][k]=min(dp[i][j][k],Next[dp[i][j][k-1]+1][s[2][k-1]-'a']);
			}
		} 
		else s[id].pop_back();
		puts(dp[s[0].length()][s[1].length()][s[2].length()]<len?"YES":"NO");
	}
}

 

订阅评论
提醒
0 评论
内联反馈
查看所有评论