10504 - Hidden squares

All about problems in Volume 105. 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
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

10504 - Hidden squares

Post by saiqbal »

i don't understand the 2nd sample input. i found only 7 squares for B in the following grid, but sample output says there are 8.

Code: Select all

A	B	B	A
B	B	B	B
A	B	B	B
A	B	B	A
the squares i found for B are:

Code: Select all

1.
-	B	B	-
-	B	B	-
-	-	-	-
-	-	-	-

2.
-	-	-	-
-	B	B	-
-	B	B	-
-	-	-	-

3.
-	-	-	-
-	-	-	-
-	B	B	-
-	B	B	-

4.
-	-	-	-
-	-	B	B
-	-	B	B
-	-	-	-

5.
-	B	-	-
B	-	B	-
-	B	-	-
-	-	-	-

6.
-	-	B	-
-	B	-	B
-	-	B	-
-	-	-	-

7.
-	-	-	-
-	-	B	-
-	B	-	B
-	-	B	-
can someone please tell me where is the 8th square?

-sohel

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok »

- - B -
B - - -
- - - B
- B - -
-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal »

thanx.. that was really helpful :)

-sohel

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

10504-Can anyone give me some hint?

Post by sunhong »

I think about this problem for a long time. But I can't find good method to solve it. I'm afraid to get time limit excceed if I check every possible square. Can someone introduce how to solve it? Thank you!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Re: 10504-Can anyone give me some hint?

Post by little joey »

sunhong wrote:... I'm afraid to get time limit excceed if I check every possible square. ...
You'll never know if you don't try...

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen »

I have forgot which method I use for it.

But about O(n^4), pass it with not bad speed.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

Post by WR »

If the input consists of an 100 x 100 grid with just capital A's. How many squares are there?

My program returns 10551500.

Is that correct?

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k »

My AC program for 100 x 100 square of capital A's gives:

8332500 :-?


Wojciech

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

10504

Post by asif_rahman0 »

deleted
Last edited by asif_rahman0 on Sat May 26, 2007 11:28 pm, edited 1 time in total.

ThanhNhan
New poster
Posts: 15
Joined: Sun Aug 08, 2004 12:24 am

Post by ThanhNhan »

you need to check the bounds of the indexes for word[k+l-j][l-k+i]

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Post by x140l31 »

One question about this problem.

I had Wrong Answer:

Code: Select all

AC code

I think that the problem should be in the ooutput. I which order I have to write it?



In the input, after the "n lines" of the "square", what we have to do with the "letters"?
Sample Input

3

2

AAA

AAA

BAB

A <---- ?

B <---- ?




Sorry about my bad english '
Last edited by x140l31 on Tue May 15, 2007 1:21 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Check the cases caryfully. Hope these help.

Input:

Code: Select all

3
2 
AAA
AAA
BAB
B
A
4
2
ABBA
BBBB
ABBB
ABBA
A
B
0
Output:

Code: Select all

B 0
A 3

A 1
B 8
Ami ekhono shopno dekhi...
HomePage

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Post by x140l31 »

thx Jan :D I got AC

MrBlah
New poster
Posts: 2
Joined: Tue May 15, 2007 4:18 am
Location: Shilito

WA!

Post by MrBlah »

Code: Select all

#include <stdio.h>
#include <string.h>

int main (){
	int largo, x, y, q, p, n[26], cantletras, i, j, K;
	char w[101][101],a[26];

	while(scanf("%d", &largo)==1){
		if (largo <= 0 || largo > 100) return 0;

		getchar();
		scanf("%d", &cantletras);
		getchar();

		for (i=0;i<26;i++) n[i]=0;

		for (i=0;i<largo;i++){
			scanf("%s", w[i]);
			getchar();
			K = strlen(w[i]);
			w[i][K]='\0';
		}
		
		for (i=0;i<cantletras;i++){
			scanf("%c", &a[i]);
			getchar();
		}

		for (x=0; x<largo; x++)
		{
			for (y=0;y<largo;y++)
			{
				for (q=0; q<largo;q++)
				{
					for (p=1; p<largo; p++) 
					{
						if ( (x+p+q<largo) && (x+p+q-p<largo) && (x+p+q-p>=0) && (y-q>=0) && (y-q+p<largo) && (y-q+p>=0) && (y-q+p+q<largo) && (y-q+p+q>=0) && (w[x][y] == w[x+p][y-q]) && (w[x+p][y-q] == w[x+p+q][y-q+p]) && (w[x+p+q][y-q+p] == w[x+p+q-p][y-q+p+q]))
						{
							for (j=0; j<26; j++) 
							{
								if (a[j] == w[x][y])
								{
									++n[j];
									break;
								}
							}
						}
					}
				}
			}
		}
		
		for (j=0;j<cantletras;j++){
			printf("%c %d\n", a[j],n[j]);
		}
		printf("\n");
	}
	return 0;
}
I keep getting WA and i tested all the test casesin the board and got all of them right T_T WHY WA!??
ARG!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

You have to print a blank line between two consecutive cases, not after every case.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 105 (10500-10599)”