433 - Bank (Not Quite O.C.R.)

[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]

[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

[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.

[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

[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.

[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

[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

[..]

how about this?

Code: Select all

1
 _  _  _  _  _  _  _  _  _
| || || || || || || || || |
|_||_||_||_||_||_||_||_||_|

Code: Select all

000000000

[emotional blind]

my program is write with your input.
and still get wrong answer.

[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

[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!

[Jan]

Your algorithm is correct.

[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
 _  _  _  _  _  _  _  _  _
|_|  ||_||_||_||_||_||_||_|
|_|  ||_||_||_||_||_||_||_|
  
  |
  |
 _  _  _  _  _  _  _  _
|_|  ||_||_||_||_||_||_|
|_|  ||_||_||_||_||_||_|_

Output:

Code: Select all

878888888
failure
failure

I think u have found the error......

[Jan]

Try the input output set I posted on this url..

http://online-judge.uva.es/board/viewto ... hlight=433

Hope it helps...

[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.

Code: Select all

CUT

Thanks