10813 - Traditional BINGO

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

Moderator: Board moderators

rubendv
New poster
Posts: 9
Joined: Mon Mar 15, 2004 10:23 pm

Post by rubendv » Tue Mar 01, 2005 7:07 pm

Thanks Larry.

Although I corrected my program, I still got WA.
Tell me another thing:

If I am on a particular game instance "i", and I reach BINGO in less than the 75 numbers, the other numbers that didn't came out count in the next game instance "i + 1"?

Thanks in advance

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue Mar 01, 2005 7:16 pm

No, they don't. Each game is independent.
If only I had as much free time as I did in college...

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

Post by Larry » Thu Mar 03, 2005 6:23 pm

Remeber to read in all 75 numbers, regardless of if you won or not.

watershed
New poster
Posts: 13
Joined: Thu Aug 05, 2004 9:14 am

10813-WA

Post by watershed » Wed Jul 20, 2005 5:29 am

Code: Select all

#include<stdio.h>
int grid[5][5]={0};  // BINGO card
bool mark[5][5];
int call[75];
void clear()
{
    int i, j;
    for(i=0; i<5; ++i)
        for(j=0; j<5; ++j)
            mark[i][j] = false;
    mark[2][2] = true;  // free space
}
void input()
{
    int i, j;
    for(i=0; i<2; ++i)
        for(j=0; j<5; ++j)
            scanf("%d",&grid[i][j]);
    scanf("%d%d%d%d",&grid[2][0],&grid[2][1],&grid[2][3],&grid[2][4]);
    for(i=3; i<5; ++i)
        for(j=0; j<5; ++j)
            scanf("%d",&grid[i][j]);
    for(i=0; i<75; ++i)
        scanf("%d",&call[i]);
}
int bingo(int y, int x)
{
    int i, j, verify = 0;
    for(i=0; i<5; ++i)		// Vertical
        if( mark[i][x] == true ) ++verify;
    if( verify == 5 ) return 1;

    verify = 0;
    for(j=0; j<5; ++j)		// Horizontal
        if( mark[y][j] == true ) ++verify;
    if( verify == 5 ) return 1;

    if( x == y ) {          // Diagonal 1
        verify = 0;
        for(i=0, j=0; i<5; ++i, ++j)
            if( mark[i][j] == true ) ++verify;
        if( verify == 5 ) return 1;
    }
                            // Diagonal 2
    if((x==4 && y==0) || (x==3 && y==1) || (x==1 && y==3) || (x==0 && y==4)) {
        verify = 0;
        for(i=4, j=0; j<5; --i, ++j)
            if( mark[i][j] == true ) ++verify;
        if( verify == 5 ) return 1;		
    }
    return 0;
}
int compute()
{
    int i, j, k;
    for(k=0; k<75; ++k) {
        for(i=0; i<5; ++i)
            for(j=0; j<5; ++j)
                if( grid[i][j] == call[k] ) { // find bingo number, mark it
                    mark[i][j] = true;
                    if( bingo(i,j) ) return call[k];
                }
    }
}
main()
{
    int n;
    scanf("%d",&n);
    for(; n>0; --n) {
        clear();
        input();
        printf("BINGO after %d numbers announced\n",compute());
	}
}

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10813-WA

Post by Martin Macko » Fri Jul 29, 2005 7:29 am

watershed wrote:

Code: Select all

int compute()
{
     ...
                    if( bingo(i,j) ) return call[k];
     ...
}
You shouldn't write the last announced number, but it's order.

Soarer
New poster
Posts: 14
Joined: Wed Nov 09, 2005 8:17 pm

Post by Soarer » Sat Nov 19, 2005 11:05 am

can anyone give me some more io? thanks.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » Mon Nov 21, 2005 4:28 pm

Soarer wrote:can anyone give me some more io? thanks.
I also think htl's input set is incorrect just like sumankar's comment.
My AC code outputs different result from ibrahim's one.

And following is other i/o.
Input :

Code: Select all

5
1 16 31 46 61
2 17 32 47 62
3 18    48 63
4 19 34 49 64
5 20 35 50 65
75 74 73 72 71 70 69 68 67 66
60 59 58 57 56 55 54 53 52 51
45 44 43 42 41 40 39 38 37 36
30 29 28 27 26 25 24 23 22 21
15 14 13 12 11 10  9  8  7  6
 1 17 31 47 61 63 49 65 35 19
 5  3 16 46  2 32 62 18 48  4
34 64 20 50 33
1 16 31 46 61
2 17 32 47 62
3 18    48 63
4 19 34 49 64
5 20 35 50 65
75 74 73 72 71 70 69 68 67 66
60 59 58 57 56 55 54 53 52 51
45 44 43 42 41 40 39 38 37 36
30 29 28 27 26 25 24 23 22 21
15 14 13 12 11 10  9  8  7  6
61 46 31 16  2 17 32 47 63 48
 3  4 34 49 65 20  5 19 64 35
50 18 63  1 33
1 16 31 46 61
2 17 32 47 62
3 18    48 63
4 19 34 49 64
5 20 35 50 65
75 74 73 72 71 70 69 68 67 66
60 59 58 57 56 55 54 53 52 51
45 44 43 42 41 40 39 38 37 36
30 29 28 27 26 25 24 23 22 21
15 14 13 12 11 10  9  8  7  6
61 46 31 16  2 17 32 47 63 48
 3  4 34 49 65 20  5 35 64 19
50 18 63  1 33
1 16 31 46 61
2 17 32 47 62
3 18    48 63
4 19 34 49 64
5 20 35 50 65
75 74 73 72 71 70 69 68 67 66
60 59 58 57 56 55 54 53 52 51
45 44 43 42 41 40 39 38 37 36
30 29 28 27 26 25 24 23 22 21
15 14 13 12 11 10  9  8  7  6
61 46 31 16  2 17 32 47 63 48
 3  4 34 49 65 20  5  1 64 19
50 18 63 35 33
1 16 31 46 61
2 17 32 47 62
3 18    48 63
4 19 34 49 64
5 20 35 50 65
75 74 73 72 71 70 69 68 67 66
60 59 58 57 56 55 54 53 52 51
45 44 43 42 41 40 39 38 37 36
30 29 28 27 26 25 24 23 22 21
15 14 13 12 11 10  9  8  7  6
61 46 31 16  2 17 32 47 63 48
 3  4 34 49 65 20  5 33 18 19
50 64 63 35  1
Output :

Code: Select all

BINGO after 58 numbers announced
BINGO after 68 numbers announced
BINGO after 68 numbers announced
BINGO after 68 numbers announced
BINGO after 69 numbers announced
Best regards.

User avatar
rafagiu
New poster
Posts: 12
Joined: Sat Sep 24, 2005 8:30 pm

Post by rafagiu » Mon Dec 12, 2005 4:30 pm

Hello everyone,

I have two more test cases for the friends in need. :D

Since I wasn't able to get AC until my program could solve these both test cases, I think they might be useful. They include some extreme values which your program should be ready to deal with.

Enjoy! :wink:

Input:

Code: Select all

2

 1 16 31 46 61
 2 20 32 47 66
11 17    55 71
 4 18 36 56 72
10 19 40 50 65
 1  2  3 61 16  6  7  8  9 10
11 12 13 14  5 31 17 18 19 46
21 22 23 24 25 26 20 28 29 30
15 32 33 34 35 36 37 38 39 40
41 42 43 44 45 27 47 48 49 50
51 52 53 54 55 56 57 58 59 60
 4 62 63 64 65 66 67 68 69 70
71 72 73 74 75

 1 20 31 47 61
 2 21 32 46 62
 3 17    48 63
 4 16 33 49 64
15 19 34 50 65
 1  2  3 75  5  6  7  8  9 10
11 12 13 14 15 16 74 18 19 20
21 22 23 24 25 26 27 28 29 30
71 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 73 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
31 72 49 17  4
Output:

Code: Select all

BINGO after 20 numbers announced
BINGO after 61 numbers announced
[/code]

xintactox
New poster
Posts: 14
Joined: Thu Dec 01, 2005 3:17 pm
Location: Brazil

Thanks tan_Yui!

Post by xintactox » Tue Dec 27, 2005 2:18 pm

Your sample input/output helped me a lot!

Thank you!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 10813 - Traditional BINGO

Post by Shahidul.CSE » Tue Jul 22, 2014 7:59 pm

I am in doubt for some matter in this problem, such as-
  • 1)I didn't understand this,
    A player may mark the centre FREE SPACE at any time.
    2)For center free space, 2 diagonals, C3 and R3 contain only four numbers. So how can be match 5 times? and why should I check for these four case?
    3)I only checked for r1,r2,r4,r5,c1,c2,c4,c5 , but having WA.
Hereis my code:

Code: Select all

Code removed after being Accepted !
Last edited by Shahidul.CSE on Wed Jul 23, 2014 7:24 am, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10813 - Traditional BINGO

Post by lbv » Tue Jul 22, 2014 9:00 pm

Shahidul.CSE wrote:I am in doubt for some matter in this problem, such as-
  • 1)I didn't understand this,
    A player may mark the centre FREE SPACE at any time.
It means exactly what those words typically mean. That is, a player can mark the centre space at any point in time (before the first turn, after the first turn, after the second, etc.) At any time. See the test cases below.

Shahidul.CSE wrote:
  • 2)For center free space, 2 diagonals, C3 and R3 contain only four numbers. So how can be match 5 times? and why should I check for these four case?
The center space is a sort of "wildcard". It is as any other space, in the sense that you can mark it, and a game is won when you mark 5 in any row, column or diagonal, but what makes the center space special is the rule explained in the previous point.

You should check for C3, and R3 and the two main diagonals because each of these form valid bingos when their 5 spaces are marked.

Shahidul.CSE wrote:
  • 3)I only checked for r1,r2,r4,r5,c1,c2,c4,c5 , but having WA.
I'm not sure if I understand your approach, but notice that merely ignoring the center space is not enough. Each BINGO has to be from 5 spaces from the same row, column or diagonal.

Try the test cases posted in previous messages. Here's a couple more:

Input

Code: Select all

2

1 16 31 46 61
2 17 32 47 62
3 18    48 63
4 19 34 49 64
5 20 35 50 65
 3 18 48 63 61 31 46 16  2 32
47 62  1 17 49 65  4 19 34 64
 5 20 35 50  6  7  8  9 10 11
12 13 14 15 21 22 23 24 25 26
27 28 29 30 33 36 37 38 39 40
41 42 43 44 45 51 52 53 54 55
56 57 58 59 60 66 67 68 69 70
71 72 73 74 75

1 16 31 46 61
2 17 32 47 62
3 18    48 63
4 19 34 49 64
5 20 35 50 65
 3 18 48 61 63 31 46 16  2 32
47 62  1 17 49 65  4 19 34 64
 5 20 35 50  6  7  8  9 10 11
12 13 14 15 21 22 23 24 25 26
27 28 29 30 33 36 37 38 39 40
41 42 43 44 45 51 52 53 54 55
56 57 58 59 60 66 67 68 69 70
71 72 73 74 75
Output

Code: Select all

BINGO after 4 numbers announced
BINGO after 5 numbers announced
Last edited by lbv on Wed Jul 23, 2014 7:56 am, edited 1 time in total.

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 10813 - Traditional BINGO

Post by Shahidul.CSE » Tue Jul 22, 2014 10:30 pm

Now I have changed my code as bellow:

Code: Select all

    Code removed after being Accepted !

Last edited by Shahidul.CSE on Wed Jul 23, 2014 7:22 am, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10813 - Traditional BINGO

Post by lbv » Tue Jul 22, 2014 11:16 pm

Shahidul.CSE wrote:Now I have changed my code as bellow: (..)
But my code doesn't work properly.
In this line:

Code: Select all

if(r1==5||r2==5||r3==5||r4==5||r5==5||c1==5||c2==5||c3==5||c4==5||c5||d1==5||d2==5)
what happened to the condition for c5?

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 10813 - Traditional BINGO

Post by Shahidul.CSE » Wed Jul 23, 2014 7:20 am

Thank you, got Accepted !! :D
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

Post Reply

Return to “Volume 108 (10800-10899)”