50013. Bingo

Problem Description

Write a program to play bingo. The bingo is played on a 8 by 8 grid. The grid has 8 rows (from 0 to 7, top to bottom) and eight columns (from 0 to 7, left to right). For example, this is a bingo board.

0010010000000100110001000111111100110100010001000100010000000100


A bingo board can be easily represented as a 64 bit unsigned long long integer. For example, the bingo board above can easily represented as the following binary number.

highbit                                                   lowbit   6         5         4         3         2         1         032109876543210987654321098765432109876543210987654321098765432100010010000000100110001000111111100110100010001000100010000000100


Now given a bingo board, please determine if you have a bingo. A board has a bingo if any of the following conditions is true.

1. The bingo board has all 1's in a row.
2. The bingo board has all 1's in a column.
3. The bingo board has all 1's in either diagonal.

You need to implement the following functions to determine if a given board has a bingo. The return value should be 0 if the board does not have a bingo. It should return 1 if the first condition is satisfied, 2 the second condition, 3 the third condition. If multiple conditions are satisfied, you should return the smallest one.

1int bingo(const unsigned long long int *board, int *rowColumn);


Also you need to set the rowColumn variable as the smallest row and column index if you have a bingo. If you have the third condition, you should set rowColumn to 0 for the diagonal from (0, 0) to (7, 7), and 1 for the diagonal from (0, 7) to (7, 0). Note that (0, 0) is the upper left corner of the board. If you have both, then set rowColumn to 0.

• 10pt. The board has exactly 8 1's, and all of them are in row 7.
• 10pt. The board has exactly 8 1's, and all of them are in the same row, which could be row 5, 6, or 7.
• 20pt. You only need to check the first bingo condition.
• 10pt. The board has exactly 8 1's, and all of them are in the same column, which could be column 5, 6, or 7. Note that solving this subtask does not guarantee that your solution can solve the first three subcases. However, this subtask will help you solve the task in identifying the second condition.
• 35pt. You only need to check the first and the second bingo conditions.
• 15pt. You need to check all bingo conditions.

Source codes

main.c

123456789101112#include <stdio.h>#include "bingo.h"int main(void){    unsigned long long int board;    int res = 0, rowColumn = 0;    scanf("%llu", &board);    res = bingo(&board, &rowColumn);    if(res == 0) printf("no\n");    else printf("%d %d\n", res, rowColumn);    return 0;}


bingo.h

int bingo(const unsigned long long int *board, int *rowColumn);


Sample Inputs and Outputs

Sample Board 1

0 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 01 1 1 1 1 1 1 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0


Sample Input 1

16711680


Sample Output 1

1 5


Sample Board 2

0 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 01 1 1 1 1 1 1 0


Sample Input 2

254


Sample Output 2

no


Hint

For detecting the first and the second bingo conditions we need to detect whether one rwo or column are full of 1's. For example, we need to following four patterns to detect row 0 and 7, and column 0 and 7.

1111111100000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000011111111 1000000010000000100000001000000010000000100000001000000010000000  0000000100000001000000010000000100000001000000010000000100000001


It is easy to construct the first and second pattern, which is simply 255. In order to construc the fourth pattern, we consider its binary form.

0000000100000001000000010000000100000001000000010000000100000001


It is easy to see that it can be construicted by taking an "or" on the following.

00000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000


It is easy then to construct the third pattern from this.