QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#544970 | #7858. Basic Equation Solving | XfJbUhpyzgaW# | WA | 322ms | 3948kb | C++14 | 3.6kb | 2024-09-02 21:21:54 | 2024-09-02 21:21:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
char ch[100],a[15][100],b[15][100],op[15];
int len[15],val[256];
int n,ans=0;
void dfs(int x,int i){
if (i>len[x]) ++x,i=1;
if (x>n){
int res=1;
for (char i='A';i<='Z';++i) if (val[i]==-1) res=10ll*res%mod;
(ans+=res)%=mod;
// printf("%d\n",res);
return;
}
if (op[x]=='<'){
if (val[a[x][i]]!=-1 && val[b[x][i]]!=-1){
if (val[a[x][i]]<val[b[x][i]]) dfs(x+1,1);
else if (val[a[x][i]]==val[b[x][i]]){
if (i==len[x]) return;
dfs(x,i+1);
}
else return;
}
else if (val[a[x][i]]!=-1 && val[b[x][i]]==-1){
for (int v=val[a[x][i]]+1;v<=9;++v){
val[b[x][i]]=v;
dfs(x,len[x]+1);
val[b[x][i]]=-1;
}
if (i!=len[x]){
val[b[x][i]]=val[a[x][i]];
dfs(x,i+1);
val[b[x][i]]=-1;
}
}
else if (val[a[x][i]]==-1 && val[b[x][i]]!=-1){
for (int v=0;v<val[b[x][i]];++v){
val[a[x][i]]=v;
dfs(x,len[x]+1);
val[a[x][i]]=-1;
}
if (i!=len[x]){
val[a[x][i]]=val[b[x][i]];
dfs(x,i+1);
val[a[x][i]]=-1;
}
}
else{
for (int va=0;va<=9;++va)
for (int vb=va;vb<=9;++vb)
if (va<vb){
val[a[x][i]]=va,val[b[x][i]]=vb;
dfs(x,len[x]+1);
val[a[x][i]]=val[b[x][i]]=-1;
}
else if (i!=len[x]){
val[a[x][i]]=val[b[x][i]]=va;
dfs(x,i+1);
val[a[x][i]]=val[b[x][i]]=-1;
}
}
}
else if (op[x]=='='){
if (val[a[x][i]]!=-1 && val[b[x][i]]!=-1){
if (val[a[x][i]]==val[b[x][i]]) dfs(x,i+1);
else return;
}
else if (val[a[x][i]]!=-1 && val[b[x][i]]==-1){
val[b[x][i]]=val[a[x][i]];
dfs(x,i+1);
val[b[x][i]]=-1;
}
else if (val[a[x][i]]==-1 && val[b[x][i]]!=-1){
val[a[x][i]]=val[b[x][i]];
dfs(x,i+1);
val[a[x][i]]=-1;
}
else{
for (int v=0;v<=9;++v){
val[a[x][i]]=val[b[x][i]]=v;
dfs(x,i+1);
val[a[x][i]]=val[b[x][i]]=-1;
}
}
}
}
int main(){
//freopen("b.in","r",stdin);
scanf("%d",&n);
for (int i=1;i<=n;++i){
scanf("%s",ch+1);
int la=0,lb=0,it=1,L=strlen(ch+1);
while (ch[it]!='<' && ch[it]!='>' && ch[it]!='=') a[i][++la]=ch[it++];
op[i]=ch[it++];
while (it<=L) b[i][++lb]=ch[it++];
len[i]=max(la,lb);
if (la<len[i]){
for (int j=len[i];j>=len[i]-la+1;--j) a[i][j]=a[i][j-(len[i]-la)];
for (int j=len[i]-la;j>=1;--j) a[i][j]='0';
}
if (lb<len[i]){
for (int j=len[i];j>=len[i]-lb+1;--j) b[i][j]=b[i][j-(len[i]-lb)];
for (int j=len[i]-lb;j>=1;--j) b[i][j]='0';
}
if (op[i]=='>') {
op[i] = '<';
swap(a[i], b[i]);
}
}
for (int i=0;i<256;++i) val[i]=-1;
for (int i=0;i<=9;++i) val['0'+i]=i;
dfs(1,1);
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3948kb
input:
1 P=NP
output:
766136394
result:
ok single line: '766136394'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
1 2000CNY>3000USD
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3944kb
input:
4 AB>CD E<A BC>FF EF>F1
output:
23645065
result:
ok single line: '23645065'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2 BC>DD BD<EA
output:
27271695
result:
ok single line: '27271695'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
3 CE>ED CC>BA BB<AC
output:
426829091
result:
ok single line: '426829091'
Test #6:
score: -100
Wrong Answer
time: 322ms
memory: 3864kb
input:
10 KG<EI EJ>DA EB<IH EB>JG KF<CF JC>FC IC<BJ FI>HH KD>AH AE>GJ
output:
80219740
result:
wrong answer 1st lines differ - expected: '87744507', found: '80219740'