Page 1 of 2
Help:433 (WA)
Posted: Wed Aug 14, 2002 1:09 pm
by yeung
Who can help me?
I try n times,but ...
[pascal]
type
ntype=array [0..8] of byte;
const
fi='';
fo='';
num:array [0..9] of ntype=((0,1,0,1,0,1,1,1,1),(0,0,0,0,0,1,0,0,1),
(0,1,0,0,1,1,1,1,0),(0,1,0,0,1,1,0,1,1),
(0,0,0,1,1,1,0,0,1),(0,1,0,1,1,0,0,1,1),
(0,1,0,1,1,0,1,1,1),(0,1,0,0,0,1,0,0,1),
(0,1,0,1,1,1,1,1,1),(0,1,0,1,1,1,0,1,1));
var
f1,f2:text;
p,task,tot,v,u,q,time:integer;
data:array [0..8] of ntype;
d,ok:array [0..8] of byte;
procedure readdata;
var
i,j:byte;
x:char;
begin
fillchar(data,sizeof(data),0);
time:=0;
for i:=0 to 2 do
begin
j:=0;
while (j<=26)and(not eoln(f1)) do
begin
read(f1,x);
if x<>' '
then data[j div 3,i*3+(j mod 3)]:=1;
inc(j);
end;
readln(f1);
end;
end;
function check(a,b:ntype):boolean;
var
i:byte;
begin
check:=false;
for i:=0 to 8 do
if a<>b
then exit;
check:=true;
end;
function get(x:ntype):byte;
var
i:byte;
begin
for i:=0 to 9 do
if check(num,x)
then begin get:=i;exit;end;
get:=255;
end;
procedure process;
var
i:byte;
begin
tot:=0;
for i:=0 to 8 do
begin q:=d*(9-i);tot:=tot+q;end;
if tot mod 11=0
then begin inc(time);ok:=d;end;
end;
procedure change(v:byte);
var
i:byte;
begin
for i:=0 to 8 do
if data[v,i]=0
then begin
data[v,i]:=1;
d[v]:=get(data[v]);
if d[v]<>255 then process;
data[v,i]:=0;
end;
d[v]:=get(data[v]);
end;
procedure solve;
var
i:byte;
begin
u:=0;
for i:=0 to 8 do
begin
d:=get(data);
if d=255
then begin inc(u);v:=i;end;
end;
case u of
0:begin
process;
if time=0
then for i:=0 to 8 do
change(i);
end;
1:change(v);
end;
case time of
0:writeln(f2,'failure');
1:begin
for i:=0 to 8 do
write(f2,ok);
writeln(f2);
end;
else writeln(f2,'ambiguous');
end;
end;
begin
assign(f1,fi);
assign(f2,fo);
rewrite(f2);
reset(f1);
readln(f1,task);
for p:=1 to task do
begin
readdata;
solve;
end;
close(f1);
close(f2);
end.
[/pascal]
433 - Bank (Not Quite O.C.R.)
Posted: Wed Jun 04, 2003 8:25 am
by Dominik Michniewski
Could anyone tell me , what am I doing wrong? I think, that this problem is easy.
My algorithm is:
1. Read input number and convert it to bit patterns (I'm sure that this part is correct... )
2. Check if number is correct - if YES - end work with this case and print number
3. For each digit in number try:
- if is valid digit => change it to other digit (see below)
- if is invalid pattern => try to add some parts (probably more than 1) and check correctness of number
4. print ambigous if number of solutions is greater than 1, failure when 0 and number in other case
Is this algorithm correct ? I can send us my code, if anyone can check it.
I change digits in this way 0->8,1->347890,2->8,3->89,4->89,5->689,6->8,7->3890,9->8. 8 is unchangeable (see problem description)
I try to add only one segment to incorrect digit too (and to other digits), but I still got WA.
Could anyone help me in solving this problem ?
Best regards
DM
Posted: Wed Jun 04, 2003 2:52 pm
by the LA-Z-BOy
at most one digit is garbled
do you consider this case?
that means if more than one digits are garbled then
failure,
if exactly one digit is garbled then try to change the garbled digit only, don't touch the ungarbled ones,
if no digits are garbled then try every digit with every possible outcome of that digit (as you stated... 0->8,1->347890.....).
ps. i add more than one segments...
some line-segments may be missing.
Posted: Thu Jun 05, 2003 7:44 am
by Dominik Michniewski
Yes I consider this case (I think). I use two tables - in one I have digits as in input, and i other I have "correct" digits. So if more than one digit is garbled, such number never be correct (excluding case in which are more than one way to create correct number - it's ambiguous
).
Can I send you my code ? I cannot find mistake , maybe you could help me ?
Best regards
DM
Posted: Thu Jun 05, 2003 6:19 pm
by the LA-Z-BOy
So if more than one digit is garbled, such number never be correct (excluding case in which are more than one way to create correct number - it's ambiguous ).
it seems unclear to me... i just know one thing about garbled ones.. whenever more than one garbled digits, the number case
must be
failure as the problem statement says. Better watch your code... you better send it to me.
Posted: Fri Jun 06, 2003 7:39 am
by Dominik Michniewski
I wrote wrong words ...
I want to write, than sometimes number which have all digits correct have more than one correct solution - and it's ambiguous, not failure ... Sorry for my mistake
I send me code to you - maybe you found error in my code. Thanks in advance
DM
critical input output of 433
Posted: Mon Dec 13, 2004 8:27 am
by emotional blind
i need some critical input and output of 433
i can send my code also
it get wrong answer
i dont know why
plz help me
Posted: Mon Dec 13, 2004 2:59 pm
by ..
how about this?
Code: Select all
1
_ _ _ _ _ _ _ _ _
| || || || || || || || || |
|_||_||_||_||_||_||_||_||_|
Posted: Wed Dec 15, 2004 10:17 am
by emotional blind
my program is write with your input.
and still get wrong answer.
problem 433
Posted: Wed Jan 12, 2005 6:54 am
by emotional blind
my program gets wrong answer
is there any critical input/output
for which my program does not work properly
plz help me
here is my code
Code: Select all
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char seg[3][29];
int p[9][9];
int segment[10][9]={
0, 1, 0, 1, 0, 1, 1, 1, 1,
0, 0, 0, 0, 0, 1, 0, 0, 1,
0, 1, 0, 0, 1, 1, 1, 1, 0,
0, 1, 0, 0, 1, 1, 0, 1, 1,
0, 0, 0, 1, 1, 1, 0, 0, 1,
0, 1, 0, 1, 1, 0, 0, 1, 1,
0, 1, 0, 1, 1, 0, 1, 1, 1,
0, 1, 0, 0, 0, 1, 0, 0, 1,
0, 1, 0, 1, 1, 1, 1, 1, 1,
0, 1, 0, 1, 1, 1, 0, 1, 1
};
int digit(int n);
int take(int n);
int make(int pos, int n);
int main(void)
{
int num, i, j,nDigit, pos, way, total, len,k , val, point;
int q[9];
char snum[20];
gets(snum);
num=atoi(snum);
while(num--){
for(i=0;i<3;i++){
gets(seg[i]);
len=strlen(seg[i]);
for(j=len;j<27;j++)seg[i][j]=' ';
seg[i][27]='\0';
}
nDigit=0;
for(i=0;i<9;i++){
if(!digit(i)){
pos=i;
nDigit++;
}
}
if(nDigit>1)printf("failure\n");
else if(nDigit==1){
for(i=0;i<9;i++){
q[i]=take(i);
}
total=0;
for(i=0;i<9;i++){
if(i==pos)continue;
else total+=q[i]*(9-i);
}
way=0;
for(i=0;i<10;i++){
if(make(pos,i)){
if((total+i*(9-pos))%11 == 0){
way++;
q[pos]=i;
}
}
}
if(way==0)printf("failure\n");
else if(way==1){
for(i=0;i<9;i++)
printf("%d",q[i]);
printf("\n");
}
else printf("ambiguous\n");
}
else{
for(i=0;i<9;i++){
q[i]=take(i);
}
way=0;
total=0;
for(i=0;i<9;i++){
total+=q[i]*(9-i);
}
if(total%11 == 0){
way++;
}
for(j=0;j<9;j++)
for(i=0;i<10;i++){
if(make(j,i) && q[j]!=i){
if((total+i*(9-j)-q[j]*(9-j))%11 == 0){
way++;
val=i;
point=j;
}
}
}
if(way==0)printf("failure\n");
else if(way==1){
q[point]=val;
for(i=0;i<9;i++)
printf("%d",q[i]);
printf("\n");
}
else printf("ambiguous\n");
}
}
return 0;
}
int digit(int n)
{
char c;
int i, j, d;
for(i=0;i<9;i++){
c=seg[i/3][n*3 + i%3];
if(c==' '||c=='\0')p[n][i]=0;
else p[n][i]=1;
}
d=0;
for(i=0;i<10;i++){
d=1;
for(j=0; j<9; j++){
if(p[n][j]!=segment[i][j]){
d=0;
}
}
if(d)return d;
}
return d;
}
int take(int n)
{
int i,j;
for(i=0;i<10;i++){
for(j=0;j<9;j++){
if(p[n][j]!=segment[i][j])
break;
}
if(j==9)return i;
}
return -1;
}
int make(int pos, int n)
{
int i;
for(i=0;i<9;i++){
if(p[pos][i]==segment[n][i] || segment[n][i]);
else return 0;
}
return 1;
}
thanks
Posted: Fri May 13, 2005 12:28 am
by Emilio
Hi!
I have a trouble with this problem. I think that my algorithm is correct but I get WA.
I describe my algorithm here, if anyone see any incorrect step, please say me it.
1- I see each number (for a case)
if two or more numbers ar garbled => failure, step 1
if all numbers are correct and comply the condition said in the problem's specification => print all the numbers, step 1
if one number is garbled => step 2
if all numbers are correct but not comply the condition said in the problem's specification => step 3
2- I try all the posibilities for the garbled number, add bars. Step 4
3- I try transform all numbers in others. Step 4
4-
if I found 0 numbers that comply the condition said in the problem's specification => failure, step 1
if I found 1 number that comply the condition said in the problem's specification => print all the numbers that comply the condition, step 1
if I found 2 or more numbers that comply the condition said in the problem's specification => ambiguous, step 1
--------------------------------------------------------------------------------
Thanks, in advance!
Posted: Tue Jul 26, 2005 9:25 pm
by Jan
Your algorithm is correct.
Posted: Tue Jul 26, 2005 9:53 pm
by Jan
Your code is almost ok.
But I have found one error so far...
Just try the input output set...
Input:
Code: Select all
3
_ _ _ _ _ _ _ _ _
|_| ||_||_||_||_||_||_||_|
|_| ||_||_||_||_||_||_||_|
|
|
_ _ _ _ _ _ _ _
|_| ||_||_||_||_||_||_|
|_| ||_||_||_||_||_||_|_
I think u have found the error......
Posted: Tue Jul 26, 2005 9:56 pm
by Jan
Try the input output set I posted on this url..
http://online-judge.uva.es/board/viewto ... hlight=433
Hope it helps...
Posted: Fri Aug 12, 2005 2:58 pm
by Emilio
Hi Jan,
I can't encounter any bug. I have tested my code with your test case and my output is correct.
I post here my code.
If anyone can say me what is my bug, I will be very grateful.
Thanks