时间限制: 1 Sec 内存限制: 128 MB
题目描述
Bingo is a game of chance played by a group of players. Each player has his or her own bingo card with a 5-by-5 grid of numbers. Each number appears at most once per card. The bingo caller calls out a sequence of randomly drawn numbers, and the players mark the numbers that appear on their card as they are called out. The winner is the player that completes a line of five marked numbers (horizontally, vertically or diagonally) on his or her card. The winning player then yells “bingo” and the game ends.
You have been volunteering with a local youth group and have been running bingo games for the children. They love bingo, but every time two or more kids yell “bingo” at the same time, a spirited “disagreement” breaks out. You’ve created a slightly modified version of bingo (in the hopes of introducing fewer ties): the cards are 5-by-5 grids with a number from 1 to 3000 in each of the 25 cells, and a winner is only declared when a player has 5 numbers in a row. Note that in this new game, players cannot win via columns or diagonals.
Alas, these changes did not eliminate ties or the subsequent disagreements. To prevent further disagreements, you’ve decided to analyze the sets of cards to determine if there is any possibility that a tie (where two kids can yell bingo at the same time) can occur. Write a program that takes a collection of bingo cards and determines if there is any possible sequence of numbers that could be called so that the game ends, and a tie between two or more players occurs, when the last number in the sequence is called.
For example, consider the following two bingo cards:
Then this set of two cards could result in a tie if the sequence of numbers called was ：40 61 64 10 57 49 11 31 25
This sequence would result in the card on the left completing the third row and the card on the right completing the fourth row when the number 25 is called.
输入
The first line of the input is an integer n (2≤n≤100), the number of bingo cards. After the first line are the n bingo cards, each separated from the next by a blank line of input.
Each bingo card consists of five lines of input. Each line consists of five integers in the range from 1 to 3000. The numbers on each bingo card are unique.
输出
If no ties are possible between any two cards, output “no ties”. Otherwise, output the two numbers a and b (1≤a<b≤n) identifying the two cards for which a tie could occur, where the cards are numbered from 1 to n in the order that they appear in the input. If multiple pairs of cards can tie, output the pair with the smallest a, breaking any remaining ties with the smallest b.
样例输入
2
3 29 45 56 68
1 19 43 50 72
11 25 40 49 61
9 23 31 58 63
4 27 42 54 71
14 23 39 59 63
8 17 35 55 61
15 26 42 53 71
10 25 31 57 64
6 20 44 52 68
样例输出
1 2
暴力大模拟
两个相等确实可以一起叫bingo，但其他八个可能会使得其他的情况有人提前叫bingo了，所以要check一下
#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
struct node
{
int numbers[6][6];
}card[110];
void getacard(int n){
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
scanf("%d",&card[n].numbers[i][j]);
}
}
}
int n;
bool check(int i,int j,int x,int y,int val1,int val2){
map<int,bool>mmap;
for(int o=1;o<=5;o++){
if(card[i].numbers[x][val1]!=card[i].numbers[x][o])
mmap[card[i].numbers[x][o]]=true;
if(card[j].numbers[y][val2]!=card[j].numbers[y][o])
mmap[card[j].numbers[x][o]]=true;
}
if(mmap.size()<5)return true;
for(int a=0;a<n;a++){
for(int b=1;b<=5;b++){
int cnt=0;
for(int c=1;c<=5;c++){
if(mmap[card[a].numbers[b][c]])cnt++;
}
if(cnt==5) return false;
}
}
return true;
}
bool judge(int i,int j,int x,int y){
int val1=0,val2=0;
for(val1=1;val1<=5;val1++){
for(val2=1;val2<=5;val2++){
if(card[i].numbers[x][val1]==card[j].numbers[y][val2]){
if(check(i,j,x,y,val1,val2))
return true;
}
}
}
return false;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) getacard(i);
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
for(int x=1;x<=5;x++){
for(int y=1;y<=5;y++){
if(judge(i,j,x,y)){
printf("%d %d\n",i+1,j+1);
return 0;
}
}
}
}
}
printf("no ties\n");
return 0;
}
Moriarty Yang 