387 - A Puzzling Problem

All about problems in Volume 3. 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
pendryko
New poster
Posts: 3
Joined: Tue Oct 08, 2002 7:10 am

387, can you give me some test case?

Post by pendryko » Tue Oct 08, 2002 7:41 am

my brain is dump now, :(
help me please?

thanks..:)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Oct 08, 2002 8:03 am

What kind of algorithm do you use ?
I think, that this problem haven't any special cases - all depends from chosen algorithm ... I got accepted this problem first time when I try :-)

Domnik

pendryko
New poster
Posts: 3
Joined: Tue Oct 08, 2002 7:10 am

Post by pendryko » Wed Oct 09, 2002 4:07 am

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

int per;
int terpakai[100],se[100],b[100],k[100];
char x[100][100][100];
char hasil[100][100];

int masukan(){
int i,j,jtemp;
int p,q,p1,q1;
int curr,cek;
curr=1;
cek=1;
memset(&hasil,'0',sizeof(hasil));
for(i=0;i<4&&curr<=per&&cek;i++){
for(j=0;j<4&&curr<=per&&cek;j++){
if(hasil[j]=='0'){
jtemp=j;
if(x[se[curr]-1][0][0]!='1'){
for(p=0;p<k[se[curr]-1];p++){
if(x[se[curr]-1][0][p]=='0'){
jtemp--;
}
}
}
p1=i;
if(((p1+b[se[curr]-1]-1>=0)&&
(p1+b[se[curr]-1]-1<4))&&
((jtemp+k[se[curr]-1]-1>=0)&&
(jtemp+k[se[curr]-1]-1<4))){
cek=1;
for(p=0;p<b[se[curr]-1]&&cek;p++){
q1=jtemp;
for(q=0;q<k[se[curr]-1]&&cek;q++){
if(x[se[curr]-1][p][q]=='1'){
if (hasil[p1][q1]=='0'){
hasil[p1][q1]=se[curr]+48;
}else
cek=0;
}
q1++;
}
p1++;
}
}else{
cek=0;
}
curr++;
}
}
}
return cek;
}

int tulis(){
int i,j;
int cek;
cek = masukan();
for(i=0;i<4&&cek;i++){
for(j=0;j<4&&cek;j++){
if(hasil[j]=='0')
cek=0;
}
}
if (cek==1){
for(i=0;i<4;i++){
for(j=0;j<4;j++){
printf("%c",hasil[j]);
}
printf("\n");
}
per=0;
return 0;
}else
return 1;
}

void permutasi(int ya, int terpakai[100], int ke){
int i,n;
se[ke]=ya;
n=1;
if (ke==per){
n=tulis();
}
if(n==1){
for(i=1;i<=per;i++){
if(terpakai==0){
terpakai=1;
permutasi(i,terpakai,ke+1);
terpakai=0;
}
}
}
}

void mulai(){
int i,j;

memset(&terpakai,0,sizeof(terpakai));
for(j=1;j<=per;j++){
if(x[j-1][0][0]=='1'){
terpakai[j]=1;
permutasi(j,terpakai,1);
terpakai[j]=0;
}
}
if ((j>per)&&(per!=0)){
printf("No solution possible\n");
}
}


int main(){
int p,q,r,ktk,cek;
cek=0;
while((scanf("%d",&per)==1)&&(per!=0)){
if (cek==1)
printf("\n");
cek=1;
for(p=0;p<per;p++){
scanf("%d %d",&b[p],&k[p]);
getchar();
for(q=0;q<b[p];q++){
fgets(x[p][q],sizeof(x[p][q]),stdin);
}
}
ktk=0;
for(p=0;p<per;p++){
for(q=0;q<b[p];q++){
for(r=0;r<k[p];r++){
if(x[p][q][r]=='1')
ktk++;
}
}
}
if (ktk>=16){
mulai();
}else
printf("No solution possible\n");
}
return 0;
}

i use permutasi.
can we input the puzzle more than 5?
thanks. :wink:

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

387 - A Puzzling Problem

Post by pipo » Wed May 26, 2004 8:11 pm

hi..

well.... I got WA... first.. my code is right on example input and output..

also, I have tested some inputs.. as a result, the output is right..

but, when I submit my code, I got WA...

please tell some examples to me about input and output...

I dont know why I got WA...

If the reason is,

If a count of pieces is more than 10, I know why I got WA.

but, Is a count of pieces is more than 10 ?

If it is, how the output is shown ?

If this reason was that I got WA, I only suspend this reason...

If this reason isn't, I really dont know why I got WA..

please show some examples of input and output to me. [/cpp]

bleed1979
New poster
Posts: 8
Joined: Thu Oct 08, 2009 5:34 am

Re: WA 387

Post by bleed1979 » Sat Nov 07, 2009 3:44 pm

1.I think use DFS is so easy to solve this problem.
2.Normal cases are not hard for coding. I give 2 critical test cases.
Input

Code: Select all

2
4 4
1111
1111
1111
1111
1 1
1
1
1 1
1
0
Output

Code: Select all

No solution possible

No solution possible
Every piece has to be used.
Judge World - problem solving is a routine.
http://bleed1979.myweb.hinet.net

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

Re: WA 387

Post by hpjhc » Wed May 21, 2014 2:55 pm

Why WA?

Code: Select all

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#include<assert.h>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;

int n;
int row[5], col[5], vis[5], grid[5][5];
char s[5][5][5];
bool dfs(int r, int c)
{
	int temp[5][5];
	if (r == 4){
		for (int i = 0; i < n; i++){
			if (!vis[i])
				return false;
		}
		return true;
	}
	if (c == 4)
		return dfs(r + 1, 0);
	memcpy(temp, grid, sizeof(grid));
	for (int i = 0; i < n; i++)
	{
		if (vis[i])
			continue;
		if (grid[r][c] == 0 && s[i][0][0] == '1')
		{
			if (r + row[i] - 1 >= 4 || c + col[i] - 1 >= 4)
				continue;
			for (int j = 0; j < row[i]; j++)
			{
				for (int k = 0; k < col[i]; k++){
					if (s[i][j][k] == '1' && grid[r + j][c + k])
						goto next;
				}
			}
			for (int j = 0; j < row[i]; j++)
			{
				for (int k = 0; k < col[i]; k++){
					if (s[i][j][k] == '1')
						grid[r + j][c + k] = i + 1;
				}
			}
			vis[i] = 1;
			if (dfs(r, c))
				return true;
			vis[i] = 0;
			memcpy(grid, temp, sizeof(grid));
		}
		else if (grid[r][c] && s[i][0][0] == '0')
		{
			if (r + row[i] - 1 >= 4 || c + col[i] - 1 >= 4)
				continue;
			for (int j = 0; j < row[i]; j++)
			{
				for (int k = 0; k < col[i]; k++){
					if (s[i][j][k] == '1' && grid[r + j][c + k])
						goto next;
				}
			}
			for (int j = 0; j < row[i]; j++)
			{
				for (int k = 0; k < col[i]; k++){
					if (s[i][j][k] == '1')
						grid[r + j][c + k] = i + 1;
				}
			}
			vis[i] = 1;
			if (dfs(r, c))
				return true;
			vis[i] = 0;
			memcpy(grid, temp, sizeof(grid));
		}
	next:;
	}
	if (grid[r][c])
		return dfs(r, c + 1);
	return false;
}
int main(void)
{
	int p = 1;
	while (scanf("%d", &n), n)
	{
		if (p > 1)
			puts("");
		for (int i = 0; i < n; i++){
			scanf("%d%d", &row[i], &col[i]);
			for (int j = 0; j < row[i]; j++)
				scanf("%s", s[i][j]);
		}
		memset(vis, 0, sizeof(vis));
		memset(grid, 0, sizeof(grid));
		if (dfs(0, 0)){
			for (int i = 0; i < 4; i++){
				for (int j = 0; j < 4; j++)
					printf("%d", grid[i][j]);
				puts("");
			}
		}
		else
			puts("No solution possible");
		p++;
	}
	return 0;
}
Last edited by hpjhc on Thu May 22, 2014 3:46 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: WA 387

Post by brianfry713 » Wed May 21, 2014 8:20 pm

Try input:

Code: Select all

2
4 4
1010
0101
1010
0101
4 4
0101
1010
0101
1010
0
My AC code prints:

Code: Select all

1212
2121
1212
2121
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 3 (300-399)”