A. 2048 Game
time limit per test1 second memory limit per test256 megabytes
You are playing a variation of game 2048. Initially you have a multiset ss of nn integers. Every integer in this multiset is a power of two.
You may perform any number (possibly, zero) operations with this multiset.
During each operation you choose two equal integers from ss, remove them from ss and insert the number equal to their sum into ss.
For example, if s={1,2,1,1,4,2,2}s={1,2,1,1,4,2,2} and you choose integers 22 and 22, then the multiset becomes {1,1,1,4,4,2}{1,1,1,4,4,2}.
You win if the number 20482048 belongs to your multiset. For example, if s={1024,512,512,4}s={1024,512,512,4} you can win as follows: choose 512512 and 512512, your multiset turns into {1024,1024,4}{1024,1024,4}. Then choose 10241024 and 10241024, your multiset turns into {2048,4}{2048,4} and you win.
You have to determine if you can win this game.
You have to answer qq independent queries.Input
The first line contains one integer qq (1≤q≤1001≤q≤100) – the number of queries.
The first line of each query contains one integer nn (1≤n≤1001≤n≤100) — the number of elements in multiset.
The second line of each query contains nn integers s1,s2,…,sns1,s2,…,sn (1≤si≤2291≤si≤229) — the description of the multiset. It is guaranteed that all elements of the multiset are powers of two.Output
For each query print YES if it is possible to obtain the number 20482048 in your multiset, and NO otherwise.
You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).
Exampleinput
6 4 1024 512 64 512 1 2048 3 64 512 2 2 4096 4 7 2048 2 2048 2048 2048 2048 2048 2 2048 4096
output
YES YES NO NO YES YES
Note
In the first query you can win as follows: choose 512512 and 512512, and ss turns into {1024,64,1024}{1024,64,1024}. Then choose 10241024 and 10241024, and ss turns into {2048,64}{2048,64} and you win.
In the second query ss contains 20482048 initially.
签到题，暴力模拟即可
#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
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x7fffffff;
int n;
ll a[maxn];
void solve(){
scanf("%d",&n);
int pos=0;
rep(i,1,n){
ll x;scanf("%lld",&x);
if(x<=2048) a[++pos]=x;
}
if(pos==1){
puts(a[1]==2048?"YES":"NO");return;
}
if(pos==0){puts("NO");return;}
rep(k,1,300){
sort(a+1,a+1+pos);
rep(i,2,pos){
if(a[i]==2048||a[i-1]==2048){puts("YES");return;}
if(a[i-1]==a[i]){
a[i]*=2;
a[i-1]=0;
}
if(a[i]==2048||a[i-1]==2048){puts("YES");return;}
}
}
puts("NO");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
B. Knights
time limit per test1 second memory limit per test256 megabytes
You are given a chess board with nn rows and nn columns. Initially all cells of the board are empty, and you have to put a white or a black knight into each cell of the board.
A knight is a chess piece that can attack a piece in cell (x2x2, y2y2) from the cell (x1x1, y1y1) if one of the following conditions is met:
- |x1−x2|=2|x1−x2|=2 and |y1−y2|=1|y1−y2|=1, or
- |x1−x2|=1|x1−x2|=1 and |y1−y2|=2|y1−y2|=2.
Here are some examples of which cells knight can attack. In each of the following pictures, if the knight is currently in the blue cell, it can attack all red cells (and only them).
A duel of knights is a pair of knights of different colors such that these knights attack each other. You have to put a knight (a white one or a black one) into each cell in such a way that the number of duels is maximum possible.Input
The first line contains one integer nn (3≤n≤1003≤n≤100) — the number of rows (and columns) in the board.Output
Print nn lines with nn characters in each line. The jj-th character in the ii-th line should be W, if the cell (ii, jj) contains a white knight, or B, if it contains a black knight. The number of duels should be maximum possible. If there are multiple optimal answers, print any of them.
Exampleinput
3
output
WBW BBB WBW
Note
In the first example, there are 88 duels:
- the white knight in (11, 11) attacks the black knight in (33, 22);
- the white knight in (11, 11) attacks the black knight in (22, 33);
- the white knight in (11, 33) attacks the black knight in (33, 22);
- the white knight in (11, 33) attacks the black knight in (22, 11);
- the white knight in (33, 11) attacks the black knight in (11, 22);
- the white knight in (33, 11) attacks the black knight in (22, 33);
- the white knight in (33, 33) attacks the black knight in (11, 22);
- the white knight in (33, 33) attacks the black knight in (22, 11).
奇偶交叉染色即可
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)3e5+100;
const int INF=0x7fffffff;
int main(){
int n;cin>>n;
rep(i,1,n){
rep(j,1,n) printf((i+j)%2?"W":"B");
puts("");
}
}
C. Perfect Team
time limit per test2 seconds memory limit per test256 megabytes
You may have already known that a standard ICPC team consists of exactly three members. The perfect team however has more restrictions. A student can have some specialization: coder or mathematician. She/he can have no specialization, but can't have both at the same time.
So the team is considered perfect if it includes at least one coder, at least one mathematician and it consists of exactly three members.
You are a coach at a very large university and you know that cc of your students are coders, mm are mathematicians and xx have no specialization.
What is the maximum number of full perfect teams you can distribute them into?
Note that some students can be left without a team and each student can be a part of no more than one team.
You are also asked to answer qq independent queries.Input
The first line contains a single integer qq (1≤q≤1041≤q≤104) — the number of queries.
Each of the next qq lines contains three integers cc, mm and xx (0≤c,m,x≤1080≤c,m,x≤108) — the number of coders, mathematicians and students without any specialization in the university, respectively.
Note that the no student is both coder and mathematician at the same time.Output
Print qq integers — the ii-th of them should be the answer to the ii query in the order they are given in the input. The answer is the maximum number of full perfect teams you can distribute your students into.
Exampleinput
6 1 1 1 3 6 0 0 0 0 0 1 1 10 1 10 4 4 1
output
1 3 0 0 1 3
Note
In the first example here are how teams are formed:
- the only team of 1 coder, 1 mathematician and 1 without specialization;
- all three teams consist of 1 coder and 2 mathematicians;
- no teams can be formed;
- no teams can be formed;
- one team consists of 1 coder, 1 mathematician and 1 without specialization, the rest aren't able to form any team;
- one team consists of 1 coder, 1 mathematician and 1 without specialization, one consists of 2 coders and 1 mathematician and one consists of 1 coder and 2 mathematicians.
签到
#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
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x7fffffff;
int n,a,b,c;
void solve(){
scanf("%d%d%d",&a,&b,&c);
printf("%d\n",min(min(a,b),(a+b+c)/3));
}
int main(){
int T;cin>>T;
while(T--) solve();
}
D. Make The Fence Great Again
time limit per test2 seconds memory limit per test256 megabytes
You have a fence consisting of nn vertical boards. The width of each board is 11. The height of the ii-th board is aiai. You think that the fence is great if there is no pair of adjacent boards having the same height. More formally, the fence is great if and only if for all indices from 22 to nn, the condition ai−1≠aiai−1≠ai holds.
Unfortunately, it is possible that now your fence is not great. But you can change it! You can increase the length of the ii-th board by 11, but you have to pay bibi rubles for it. The length of each board can be increased any number of times (possibly, zero).
Calculate the minimum number of rubles you have to spend to make the fence great again!
You have to answer qq independent queries.Input
The first line contains one integer qq (1≤q≤3⋅1051≤q≤3⋅105) — the number of queries.
The first line of each query contains one integers nn (1≤n≤3⋅1051≤n≤3⋅105) — the number of boards in the fence.
The following nn lines of each query contain the descriptions of the boards. The ii-th line contains two integers aiai and bibi (1≤ai,bi≤1091≤ai,bi≤109) — the length of the ii-th board and the price for increasing it by 11, respectively.
It is guaranteed that sum of all nn over all queries not exceed 3⋅1053⋅105.
It is guaranteed that answer to each query will not exceed 10181018.Output
For each query print one integer — the minimum number of rubles you have to spend to make the fence great.
Exampleinput
3 3 2 4 2 1 3 5 3 2 3 2 10 2 6 4 1 7 3 3 2 6 1000000000 2
output
2 9 0
Note
In the first query you have to increase the length of second board by 22. So your total costs if 2⋅b2=22⋅b2=2.
In the second query you have to increase the length of first board by 11 and the length of third board by 11. So your total costs if 1⋅b1+1⋅b3=91⋅b1+1⋅b3=9.
In the third query the fence is great initially, so you don't need to spend rubles.
每块木板最多上升两次，dp[i][j]表示第i块木板上升j次的答案
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)3e5+100;
const int INF=0x7fffffff;
int n;
ll a[maxn],b[maxn],dp[maxn][3];
void solve(){
scanf("%d",&n);
rep(i,1,n) rep(j,0,2) dp[i][j]=(ll)1e35;
rep(i,1,n) scanf("%lld%lld",&a[i],&b[i]);
dp[1][0]=0;dp[1][1]=b[1];dp[1][2]=2*b[1];
rep(i,2,n) rep(j,0,2) rep(k,0,2) if(a[i-1]+k!=a[i]+j)
dp[i][j]=min(dp[i][j],dp[i-1][k]+b[i]*j);
printf("%lld\n",min({dp[n][0],dp[n][1],dp[n][2]}));
}
int main(){
int T;cin>>T;
while(T--) solve();
}
E. Game With String
time limit per test3 seconds memory limit per test256 megabytes
Alice and Bob play a game. Initially they have a string s1,s2,…,sns1,s2,…,sn, consisting of only characters . and X. They take alternating turns, and Alice is moving first. During each turn, the player has to select a contiguous substring consisting only of characters . and replaces each of them with X. Alice must select a substing of length aa, and Bob must select a substring of length bb. It is guaranteed that a>ba>b.
For example, if s=s= ...X.. and a=3a=3, b=2b=2, then after Alice's move string can turn only into XXXX... And if it's Bob's turn and the string s=s= ...X.., then after Bob's move the string can turn into XX.X.., .XXX.. or ...XXX.
Whoever is unable to make a move, loses. You have to determine who wins if they both play optimally.
You have to answer qq independent queries.Input
The first line contains one integer qq (1≤q≤3⋅1051≤q≤3⋅105) — the number of queries.
The first line of each query contains two integers aa and bb (1≤b<a≤3⋅1051≤b<a≤3⋅105).
The second line of each query contains the string ss (1≤|s|≤3⋅1051≤|s|≤3⋅105), consisting of only characters . and X.
It is guaranteed that sum of all |s||s| over all queries not exceed 3⋅1053⋅105.Output
For each test case print YES if Alice can win and NO otherwise.
You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).
Exampleinput
3 3 2 XX......XX...X 4 2 X...X.X..X 5 3 .......X..X
output
YES NO YES
Note
In the first query Alice can select substring s3…s5s3…s5. After that ss turns into XXXXX...XX...X. After that, no matter what move Bob makes, Alice can make the move (this will be her second move), but Bob can't make his second move.
In the second query Alice can not win because she cannot even make one move.
In the third query Alice can choose substring s2…s6s2…s6. After that ss turns into .XXXXX.X..X, and Bob can't make a move after that.
贪心，将原字符串中的连续'.'分为三类： [b,a),[a,2b),[2b,+∞) ；
一、如果出现了type1，必输，因为最后总是b可以走，a不能走
二、type3出现次数大于1，必输，因为Bob可以选择任意一段，空出前b个之后再取b个，这样就出现了一段type1
三、type3没有，只有type2，也即每一段a或b只能走一步就不能再走了，那么输赢就只和奇偶性有关
四、type3的数量等于1，这时候我记录的长度 len 就是type2的长度，这时候需要分类讨论；
如果 \(a \ge 2 \cdot b\):这时候type1=0，type2=0，只有一段长为len的type3，a先手，贪心地去取，a的最优取法就是从中间取走a个，那么这个时候长度的最大值就是两边放两个\((b-1)\)，也即\((b-1) \cdot 2+a=a+2 \cdot b-2\)；
否则:需要考虑type2。有type2无非就是最后这段type3先手输赢的问题了，显然如果想要先手输，那么长度就控制在 [2a,a+3b-2] ，2a很好理解，后面那个上界是 (b-1)+a+(b-1)+b，即 a在中间取一段长度a，之后b总有一边可以选 并且选完之后a就不能走了；
那先手赢的话就只需要在上下界加个a和b变成 [3a,a+4b-2] 就好了，因为的一个人取走之后问题就变成了让第二个人先手输，变成了的一个情况
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)3e5+100;
const int INF=0x7fffffff;
char s[maxn];
void solve(){
int a,b;scanf("%d%d%s",&a,&b,s+1);
int n=strlen(s+1);
s[n+1]='X'; n++;
int tmp=0,len=-1;
int cnt0=0,cnt1=0,cnt2=0; //[b,a),[a,2b),[2b,+∞);
rep(i,1,n){
if(s[i]=='.') tmp++;
else{
if(tmp>=b){
if(tmp<a) cnt0++;
else if(tmp>=2*b) cnt2++,len=tmp;
else cnt1++;
} tmp=0;
}
}
if(cnt0||cnt2>=2) puts("NO");
else{
if(!cnt2) puts(cnt1&1?"YES":"NO"); //只有cnt1，即每次a和b只能走一步的情况
else{ //cnt2=1,长为len;
if(a>=2*b) puts(a+2*b-2>=len?"YES":"NO"); //cnt0=0,cnt1=0,即只有一段长为len的连续'.'
else{ //有cnt1
if(cnt1&1) puts((2*a<=len&&len<=a+3*b-2)?"YES":"NO"); //长为len,先手输 [2a,a+3b-2]->[2a,(b-1)+a+(b-1)+b];
else puts((a+2*b-2>=len||(3*a<=len&&len<=a+4*b-2))?"YES":"NO"); //长为len,先手赢 [3a,a+4b-2]上一种情况下加a和b
}
}
}
}
int main(){
int T;cin>>T;
while(T--) solve();
}
