【HDU 5579 2015上海競技区G】【スーパー大討論】Game of Arrays a[]+b[]+c[]一部の位置を1つ減らすことができ、状態が達成できるかどうか
Game of Arrays Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 14 Accepted Submission(s): 6
Problem Description
Tweek and Craig are good friends and always playing together. And they just invented a new game when doing their math homework.
First of all, they write three arrays
A ,
B , and
C , each with
N
numbers. Then on the black board, they write those arrays as
A+B=C
If the equation is satisfied, it means for each position
i
from
1
to
N , there are
Ai+Bi=Ci
holds.
Of course, this equation is not always satisfied at the very beginning.
Fortunately, for arrays
A ,
B
and
C , some numbers are
changeable , while other's are not. Those
changeable
numbers' positions are determined before the game begins.
During the game, Tweek and Craig will take turns, trying to change a number from an array. Tweek plays first.
In each turn, the player can choose a
changeable
number from an array, and substract it by one. However, no negative numbers should appear, so the chosen number cannot be
0
before substraction.
Tweek's goal is to make the equation satisfied during the game, while Craig's goal is to prevent it to happen.
The game ends when the equation is satisfied (a win for Tweek) or there are no possible moves but still
A+B≠C
(means there is
at least one
i∈[1,N] , where
Ai+Bi≠Ci , which is a win for Craig).
Given
A ,
B
and
C , and the position of
changeable
numbers for each array, your task is to determine the winner.
Input
First line contains an integer
T , which indicates the number of test cases.
Every test case begins with an integers
N , which is the length of array
A ,
B
and
C .
The
2nd
line and
3rd
line describe the array
A . The
2nd
line contains
N
intergers
A1 ,
A2 ,
⋯ ,
AN , indicating the elements in array
A . The
3rd
line contains
N intergers
u1 ,
u2 ,
⋯ ,
uN , and
ui
is
1
if
Ai
is
changeable , otherwise
ui
is
0 .
The
4th
line and
5th
line describe the array
B . The
4th
line contains
N
intergers
B1 ,
B2 ,
⋯ ,
BN , indicating the elements in array
B . The
5th
line contains
N intergers
v1 ,
v2 ,
⋯ ,
vN , and
vi
is
1
if
Bi
is
changeable ,otherwise
vi
is
0 .
The
6th
line and
7th
line describe the array
C . The
6th
line contains
N
intergers
C1 ,
C2 ,
⋯ ,
CN , indicating the elements in array
C . The
7th
line contains
N intergers
w1 ,
w2 ,
⋯ ,
wN , and
wi
is
1
if
Ci
is
changeable ,otherwise
wi
is
0 .
⋅
1≤T≤2000 .
⋅
for 75% data,
1≤N≤10 .
⋅
for 95% data,
1≤N≤50 .
⋅
for 100% data,
1≤N≤100 .
⋅
0≤Ai,Bi,Ci≤109 .
⋅
both
ui,vi,wi
is either
0
or
1 .
Output
For every test case, you should output "
Case #x: y", where
x
indicates the case number and counts from
1 , and
y
is the winner of the game.
Sample Input
3
2
4 3
1 1
4 4
0 1
5 5
0 0
2
4 4
1 1
4 4
0 0
5 5
0 0
2
4 4
1 1
4 4
0 0
4 4
0 0
Sample Output
Case #1: Tweek
Case #2: Craig
Case #3: Tweek
Source
2015 ACM/ICCCアジア区上海駅-再現試合(華東理工に感謝)
転載は必ず出典を明記してください.ありがとうございます~~.
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1,class T2>inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template <class T1,class T2>inline void gmin(T1 &a,T2 b){if(b<a)a=b;}
const int N=100+5,M=0,Z=1e9+7,ms63=1061109567;
int casenum,casei;
int a[N],b[N],c[N];
bool aa[N],bb[N],cc[N];
int weak[N],str[N];
int n;
bool match()
{
int step=1;//step==1
int weaknum=0;
LL strsum=0;
for(int i=1;i<=n;++i)
{
int tmp=abs(a[i]+b[i]-c[i]);
if(aa[i]==0&&bb[i]==0&&cc[i]==0)//000
{
//
if(a[i]+b[i]!=c[i])return 0;
}
if(aa[i]==1&&bb[i]==1&&cc[i]==1)//111
{
//
strsum+=tmp;
}
else if(aa[i]==1&&bb[i]==1&&cc[i]==0)//110
{
//
if(a[i]+b[i]<c[i])return 0;
//
if(c[i]==0)strsum+=tmp;
//
else weak[++weaknum]=tmp;
}
else if(aa[i]==0&&bb[i]==0&&cc[i]==1)//001
{
//
if(a[i]+b[i]>c[i])return 0;
//
if(a[i]==0&&b[i]==0)strsum+=tmp;
//
else weak[++weaknum]=tmp;
}
else if(aa[i]==1&&bb[i]==0&&cc[i]==0)//100
{
//
if(a[i]+b[i]<c[i])return 0;
//
if(b[i]==c[i])strsum+=tmp;
//
else weak[++weaknum]=tmp;
}
else if(aa[i]==1&&bb[i]==0&&cc[i]==1)//101
{
//
if(b[i]==0){strsum+=tmp;continue;}
//
if(b[i]>c[i])return 0;//c[] ， 。
if(a[i]+b[i]>c[i]+1)return 0;// Craig c[] 0，
if(a[i]+b[i]==c[i]+1)//
{
if(--step<0)return 0;
}
//
int tmp=c[i]-(a[i]+b[i]);
weak[++weaknum]=tmp;
}
}
if(weaknum==0)return 1;
else if(weaknum==1)
{
if(strsum<=weak[1]+1)return 1;
}
else if(weaknum==2)
{
int x=weak[1];
int y=weak[2];
if(strsum==0)
{
if(abs(x-y)==1)return 1;
}
else if(strsum==1)
{
if(abs(x-y)==0)return 1;
}
}
else// weaknum>2 ， 。 ， 。
{
LL sum=strsum;
for(int i=1;i<=weaknum;++i)sum+=abs(weak[i]);
if(sum<=1)return 1;
}
return 0;
}
int main()
{
scanf("%d",&casenum);
for(casei=1;casei<=casenum;++casei)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)scanf("%d",&aa[i]);
for(int i=1;i<=n;++i)scanf("%d",&b[i]);
for(int i=1;i<=n;++i)scanf("%d",&bb[i]);
for(int i=1;i<=n;++i)scanf("%d",&c[i]);
for(int i=1;i<=n;++i)scanf("%d",&cc[i]);
for(int i=1;i<=n;++i)
{
if(a[i]==0&&aa[i]==1)aa[i]=0;
if(b[i]==0&&bb[i]==1)bb[i]=0;
if(c[i]==0&&cc[i]==1)cc[i]=0;
if(aa[i]==0&&bb[i]==1)
{
swap(a[i],b[i]);
swap(aa[i],bb[i]);
}
}
printf("Case #%d: %s
",casei,match()?"Tweek":"Craig");
}
return 0;
}
/*
【trick&& 】
1， ， 138 5 ， 5 AC， 348 。 10.
D ， 。
2 ， AC， 。
， 。 ， 。
，B ， 1 ；G ， 3 。
G ， ， 。
D ， ， 。
2， ， ， AC ！
WA ， debug AC T_T！
3A， 5A， 1A ！
3， ！
【 】
a[],b[],c[]， [0,1e9] 。
-1 ， ， 。
（ aa[], aa[i]==1， a[i] ；==0 ）
Tweek ，Tweek ， a[]+b[]=c[]， 。
Craig ，Craig ， a[]+b[]=c[]， 。
【 】
【 】
p a[p] b[p] c[p]， 8 。
， 6 。
， AC 。
： ——
1， ：{010}->{100}，{011}->{101}
2， ：if(aa[i]==1&&a[i]==0)aa[i]=0 bool
： ， ——
1， ， aa[p]==bb[p]==cc[p]==0， if(a[p]+b[p]!=c[p])return 0;
2， ， ， ， a[p]+b[p]=c[p]。
， 0， ， 。
3， ， a[p]+b[p]=c[p]， ， 。
4， ， ， 0 。
str[]， weak[]。
strnum weaknum， strsum weaksum。
——
1，weaknum==0 ， yes
2，weaknum==1 ，weaksum ， strsum 1。 。
3，weaknum==2 ，strsum 0 1，
strsum 0 ， weak[] 1
strsum 1 ， weak[] 0
4，weaknum>2 ， 1， 。
aa[] bb[] cc[]
1 0 1
b[]==0 。
b[]>0 ，
aa[]+bb[]>cc[]+1
aa[]+bb[]==cc[]+1 ，
weak[] -1， step
aa[]+bb[]<cc[] ， 。
， 。
（ ， ， ， ）， ，
！
TwT！ >_<！
=w=， ， 。
【 】
input
3
1 1 1
1 1 1
1 1 1
1 1 1
2 2 2
1 1 1
output
Tweek
*/#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<iostream>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1,class T2>inline void gmax(T1 &a,T2 b){if(b>a)a=b;}
template <class T1,class T2>inline void gmin(T1 &a,T2 b){if(b<a)a=b;}
const int N=100+5,M=0,Z=1e9+7,ms63=1061109567;
int casenum,casei;
int a[N],b[N],c[N];
int aa[N],bb[N],cc[N];
int weak[N],str[N];
int n;
bool match()
{
//
bool nowIcan=1;
for(int i=1;i<=n;++i)if(a[i]+b[i]!=c[i])nowIcan=0;
if(nowIcan==1)return 1;
int step=1;//step
int strnum=0;
int weaknum=0;
for(int i=1;i<=n;++i)
{
int tmp=abs((a[i]+b[i])-c[i]);
if(aa[i]==0&&bb[i]==0&&cc[i]==0)//000
{
//
if(a[i]+b[i]!=c[i])return 0;
}
if(aa[i]==1&&bb[i]==1&&cc[i]==1)//111
{
//
int tmp=abs(a[i]+b[i]-c[i]);
if(tmp)str[++strnum]=tmp;
}
else if(aa[i]==1&&bb[i]==1&&cc[i]==0)//110
{
//
if(a[i]+b[i]<c[i])return 0;
int tmp=a[i]+b[i]-c[i];
//
if(c[i]==0)
{
if(tmp)str[++strnum]=tmp;
}
//
else
{
weak[++weaknum]=tmp;
}
}
else if(aa[i]==0&&bb[i]==0&&cc[i]==1)//001
{
//
if(a[i]+b[i]>c[i])return 0;
int tmp=c[i]-(a[i]+b[i]);
//
if(a[i]==0&&b[i]==0)
{
if(tmp)str[++strnum]=tmp;
}
//
else
{
weak[++weaknum]=tmp;
}
}
else if(aa[i]==1&&bb[i]==0&&cc[i]==0)//100
{
//
if(a[i]+b[i]<c[i])return 0;
int tmp=a[i]+b[i]-c[i];
//
if(b[i]==c[i])
{
if(tmp)str[++strnum]=tmp;
}
//
else
{
weak[++weaknum]=tmp;
}
}
else if(aa[i]==1&&bb[i]==0&&cc[i]==1)//101
{
//
if(b[i]==0)
{
int tmp=abs(a[i]-c[i]);
if(tmp)str[++strnum]=tmp;
continue;
}
//
if(b[i]>c[i])return 0;//c[] ， 。
if(a[i]+b[i]>c[i]+1)return 0;// c[] 0
if(a[i]+b[i]==c[i]+1)//
{
if(--step<0)return 0;
else --a[i];
}
//
int tmp=c[i]-(a[i]+b[i]);
weak[++weaknum]=tmp;
}
}
LL strsum=0;for(int i=1;i<=strnum;++i)strsum+=str[i];
LL weaksum=0;for(int i=1;i<=weaknum;++i)weaksum+=weak[i];
LL totsum=strsum+weaksum;
if(step==1)//
{
if(totsum<=1)return 1;//
if(weaknum==0)return 1;
if(weaknum==1)
{
if(strsum<=weaksum+1)return 1;
else return 0;
}
else if(weaknum==2)
{
int x=weak[1];
int y=weak[2];
if(strsum==0)
{
if(abs(x-y)==1)return 1;
else return 0;
}
else if(strsum==1)
{
if(abs(x-y)==0)return 1;
else return 0;
}
else return 0;
}
else return 0;
}
else //
{
if(totsum==0)return 1;//
if(weaknum==0)return 1;
if(weaknum==1)
{
if(strsum<=weaksum)return 1;
else return 0;
}
else if(weaknum==2)
{
int x=weak[1];
int y=weak[2];
if(strsum==0)
{
if(abs(x-y)==0)return 1;
else return 0;
}
else return 0;
}
else return 0;
}
}
void fre()
{
freopen("c://test//input.in","r",stdin);
freopen("c://test//output.out","w",stdout);
}
int main()
{
scanf("%d",&casenum);
for(casei=1;casei<=casenum;++casei)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)scanf("%d",&aa[i]);
for(int i=1;i<=n;++i)scanf("%d",&b[i]);
for(int i=1;i<=n;++i)scanf("%d",&bb[i]);
for(int i=1;i<=n;++i)scanf("%d",&c[i]);
for(int i=1;i<=n;++i)scanf("%d",&cc[i]);
for(int i=1;i<=n;++i)
{
if(a[i]==0&&aa[i]==1)aa[i]=0;
if(b[i]==0&&bb[i]==1)bb[i]=0;
if(c[i]==0&&cc[i]==1)cc[i]=0;
if(aa[i]==0&&bb[i]==1)
{
swap(a[i],b[i]);
swap(aa[i],bb[i]);
}
}
printf("Case #%d: %s
",casei,match()?"Tweek":"Craig");
}
return 0;
}