296 - Safebreaker

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
DemonCris
New poster
Posts: 25
Joined: Sun Feb 24, 2002 2:00 am
Location: Taiwan

Post by DemonCris » Thu Feb 28, 2002 2:21 pm

Is there any strange input?

I think
1314 1419 -> 2/1
1115 5011 -> 1/2
0013 3009 -> 1/2
0000 0100 -> 3/0
9999 2314 -> 0/0
1201 0490 -> 0/1

Am I wrong ???

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Fri Mar 01, 2002 8:11 am

Don't know. Could you please post your input and output in the form specified in the problem? I'd like to help you, but I won't convert it when you already have it.

Stefan

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Sat Mar 02, 2002 6:05 pm

Yes, from a cursory visual examination, I believe your cases are correct. If you want me to help you with this problem, post code.

TaChung
New poster
Posts: 2
Joined: Wed Mar 06, 2002 2:00 am

Post by TaChung » Wed Mar 06, 2002 6:52 pm

I can't find my bug in this program.
Please help me~ thanks~^^

#include <stdio.h>
#include <stdlib.h>

int rangenum[10000][4];
char r0,r1,r2,r3;
int guessnum[4];
int range;

void create(void)
{
int i,j,k,l;
int m=0;

for (i=0 ; i<10 ; i++) {
for (j=0 ; j<10 ; j++) {
for (k=0 ; k<10 ; k++) {
for (l=0 ; l<10 ; l++) {
rangenum[m][0]=i;
rangenum[m][1]=j;
rangenum[m][2]=k;
rangenum[m][3]=l;
m++;
}
}
}
}
}

int del(int num)
{
int temp;
temp = range - 1;
rangenum[num][0] = rangenum[temp][0];
rangenum[num][1] = rangenum[temp][1];
rangenum[num][2] = rangenum[temp][2];
rangenum[num][3] = rangenum[temp][3];

range = range - 1;

return num -1;
}

int checknum(int in , int out)
{
int i , j , num , A , B , k , m , l;
int record1[10] = {0,0,0,0,0,0,0,0,0,0};
int record2[10] = {0,0,0,0,0,0,0,0,0,0};

for (num=0 ; num<range ; num++) {
A = B = 0;
for (i=0 ; i<4 ; i++){
for (j=0 ; j<4 ; j++){
if (guessnum==rangenum[num][j] && (i==j)){
A++;
guessnum=-1;
rangenum[num][j]=-1;
}
}
}

for (i=0 ; i<4 ; i++){
if (guessnum!=-1) {
k = guessnum;
record1[k]++;
}
}

for (j=0 ; j<4 ; j++){
if (rangenum[num][j]!=-1) {
m = rangenum[num][j];
record2[m]++;
}
}

for (l=0 ; l<10 ; l++) {
if ((record1[l]>0) && (record2[l]>0)) {
if (record1[l]<=record2[l])
B = B + record1[l];
else
B = B + record2[l];
}
else
;
}

if ((A==in) && (B==out))
;
else
num = del(num);
}

return range;
}

int main()
{
int count , num , i , j , in , out , ans , temp;
char no;

while (scanf("%d" , &count)!=EOF) {
for (i=0 ; i<count ; i++) {
range = 10000;
create();
scanf("%d" , &num);
for (j=0 ; j<num ; j++) {
scanf("n%c%c%c%c %d%c%d",&r0,&r1,&r2,&r3,&in,&no,&out);
guessnum[0] = r0-48;
guessnum[1] = r1-48;
guessnum[2] = r2-48;
guessnum[3] = r3-48;

/*printf("%d%d%d%d %d/%dn",guessnum[0],guessnum[1],guessnum[2],guessnum[3],in,out);*/
ans = checknum(in , out);
/*printf("ans is %dn",ans);*/
}
printf("ans is %dn",ans);

if (ans==1) {
temp = range-1;
printf("%d%d%d%dn" , rangenum[temp][0] , rangenum[temp][1] , rangenum[temp][2] , rangenum[temp][3]);
}
else if (ans<1)
printf("impossiblen");
else
printf("indeterminaten");
}
}
}

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Thu Mar 07, 2002 7:16 am

Please use

Code: Select all

 
so I can test your code. Thanks!

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Thu Mar 07, 2002 7:31 am

Here is a small hint. You need to CLEAR record1 and record2 in the for loop.

A= = B = 0;
for (i=0 ; i<4 ; i++){
for (j=0 ; j<4 ; j++){
if (guessnum==rangenum[num][j] && (i==j)){
A++;
guessnum=-1;
rangenum[num][j]=-1;
}
}
}

<INSERT THIS>
for (i=0 ; i<10 ; i++){
record1=0;
record2=0;
}
<INSERT THIS>

for (i=0 ; i<4 ; i++){
if (guessnum!=-1) {
k = guessnum;
record1[k]++;
}
}

There are lots of other bugs too. Don't use character strings to attack this problem. Very inefficient. Here is how I did it:

Code: Select all

#include <stdio.h>

void main()
{
	int i,j,l,m,n,a,b,c,T,x,y,z,M[10],N[10];
	bool X[10000];	
	char A[10],B[10];
	scanf("%dn",&m);
	for(i=0;i<m;i++)
	{
		scanf("%dn",&n);
		for(j=0;j<10000;j++)
			X[j]=true;
		T=10000;
		for(j=0;j<n;j++)
		{
			scanf("%d %d/%d",&a,&b,&c);
			for(l=0;l<10000;l++)
			{
				if(X[l])
				{
					sprintf(A,"%.4d",a);			
					sprintf(B,"%.4d",l);
					y=0;
					z=0;
					for(x=0;x<10;x++)
					{
						M[x]=0;
						N[x]=0;
					}
					for(x=0;x<4;x++)
					{
						if(A[x]==B[x])
						{
							y++;
						}
						else
						{
							M[A[x]-'0']++;
							N[B[x]-'0']++;
						}
					}
					for(x=0;x<10;x++)
					{
						if(M[x]>0&&N[x]>0)
						{
							if(M[x]>N[x])
							{
								z+=N[x];
							}
							else
							{
								z+=M[x];
							}
						}
					}
					if(y!=b||z!=c)
					{
						X[l]=false;
						T--;
					}
				}
			}
		}
		if(T==0)
		{
			printf("impossiblen");
		}
		else if(T==1)
		{
			for(j=0;j<10000;j++)
			{
				if(X[j])
				{
					printf("%.4dn",j);
					break;
				}
			}
		}
		else
		{
			printf("indeterminaten");
		}
	}
}
It is late here, if you need more help, I will look over your code tomorrow night. Good luck.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

296 - Safebreaker

Post by Larry » Mon Feb 17, 2003 2:47 am

Can someone post some input/output? I used a brute force algorithm, but gets WA somehow..

Rossi
New poster
Posts: 20
Joined: Thu Mar 21, 2002 2:00 am
Location: Bangladesh

Post by Rossi » Mon Feb 17, 2003 9:05 am

when the output is 0 do u print 0000 ? (result must have 4 digits, if there are less then 4 pad with 0 in the left).

It is the only cause I can think of.
Rossi

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Feb 17, 2003 4:11 pm

You're right. I forgot about that, thanks! :D

But do you have some sample input anyhow? I still get WA..

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Feb 17, 2003 4:28 pm

Nevermind, I forgot to toggle a flag.. silly mistake, got AC now, but thanks anyhow!

Just curious though, what's a good approach other than brute force to this problem?

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

help 296

Post by Hisoka » Sun May 11, 2003 3:10 pm

Hello........

I always got WA for this problem, but I cannot found where is my mistake. can you check my code ?? :cry:
[c]/* @begin_of_source_code */
#include <stdio.h>
#include <string.h>

char cek_node[10000];

void proses(int number, int a, int b)
{
int i,j,k,yesa,yesb,cek[4];
int in[4],out[4];
for(j=3,i=0;i<4;i++,j--){
in[j]=number%10;
number/=10;
}
for(k=0;k<10000;k++)
if(!cek_node[k]){
number=k;
for(j=3,i=0;i<4;i++,j--){
cek[j]=0;
out[j]=number%10;
number/=10;
}
for(i=yesa=0;i<4;i++)
if(in==out){
cek=1;
yesa++;
}
for(i=yesb=0;i<4;i++)
if(in!=out)
for(j=0;j<4;j++)
if(!cek[j]&&i!=j)
if(in==out[j]){
yesb++;
cek[j]=1;
}
if(yesa!=a||yesb!=b) cek_node[k]=1;
}
}

void main()
{
char in[9];
int i,n,banyak,number,a,b;
scanf("%d",&banyak);
while(banyak--){
scanf("%d\n",&n);
memset(cek_node,0,sizeof(cek_node));
while(n--){
gets(in);
sscanf(in,"%d %d/%d",&number,&a,&b);
proses(number,a,b);
}
for(i=n=0;i<10000;i++){
if(!cek_node){
number=i;
n++;
}
if(n==2){ puts("indeterminate"); break; }
}
if(n==1) printf("%04d\n",number);
else
if(!n) puts("impossible");
}
}
/* @end_of_source_code */[/c]
Thanks for help....... :)
Last edited by Hisoka on Sun May 11, 2003 7:00 pm, edited 2 times in total.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Sun May 11, 2003 5:04 pm

hmmm... it's not easy to create good sample input for this problem. but one thing that can trap you is just like this :
when the result
3326
if you guess 4303 you got 1/1 not 1/2.
Kalo mau kaya, buat apa sekolah?

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Sun May 11, 2003 6:49 pm

hello titid.......

Thanks for your help. I think my program if number is 3326 and guest 4303 I will got 1/1 not 1/2. but if guest 4003 I will got WA, because I will produce 0/2 not 0/1, because I cannot use break. I got WA for this problem 3 time.

Thank you very much.......

bye... :D

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Mar 15, 2006 1:28 am

I don't know if it can be solved other than brute force.

Post Reply

Return to “Volume 2 (200-299)”