首页 > 代码库 > HDU4951:Multiplication table
HDU4951:Multiplication table
Problem Description
Teacher Mai has a multiplication table in base p.
For example, the following is a multiplication table in base 4:
* 0 1 2 3
0 00 00 00 00
1 00 01 02 03
2 00 02 10 12
3 00 03 12 21
But a naughty kid maps numbers 0..p-1 into another permutation and shuffle the multiplication table.
For example Teacher Mai only can see:
1*1=11 1*3=11 1*2=11 1*0=11
3*1=11 3*3=13 3*2=12 3*0=10
2*1=11 2*3=12 2*2=31 2*0=32
0*1=11 0*3=10 0*2=32 0*0=23
Teacher Mai wants you to recover the multiplication table. Output the permutation number 0..p-1 mapped into.
It‘s guaranteed the solution is unique.
For example, the following is a multiplication table in base 4:
0 00 00 00 00
1 00 01 02 03
2 00 02 10 12
3 00 03 12 21
But a naughty kid maps numbers 0..p-1 into another permutation and shuffle the multiplication table.
For example Teacher Mai only can see:
3*1=11 3*3=13 3*2=12 3*0=10
2*1=11 2*3=12 2*2=31 2*0=32
0*1=11 0*3=10 0*2=32 0*0=23
Teacher Mai wants you to recover the multiplication table. Output the permutation number 0..p-1 mapped into.
It‘s guaranteed the solution is unique.
Input
There are multiple test cases, terminated by a line "0".
For each test case, the first line contains one integer p(2<=p<=500).
In following p lines, each line contains 2*p integers.The (2*j+1)-th number x and (2*j+2)-th number y in the i-th line indicates equation i*j=xy in the shuffled multiplication table.
Warning: Large IO!
For each test case, the first line contains one integer p(2<=p<=500).
In following p lines, each line contains 2*p integers.The (2*j+1)-th number x and (2*j+2)-th number y in the i-th line indicates equation i*j=xy in the shuffled multiplication table.
Warning: Large IO!
Output
For each case, output one line.
First output "Case #k:", where k is the case number counting from 1. The following are p integers, indicating the permutation number 0..p-1 mapped into.
First output "Case #k:", where k is the case number counting from 1. The following are p integers, indicating the permutation number 0..p-1 mapped into.
Sample Input
4 2 3 1 1 3 2 1 0 1 1 1 1 1 1 1 1 3 2 1 1 3 1 1 2 1 0 1 1 1 2 1 3 0
Sample Output
Case #1: 1 3 2 0可以发现,0对应的情况下,这行的所有数字都相同其他数字则看第一位,假设有n种不同的情况,对应的数字就是n1的情况要对应0做特殊处理用G++超时,用C++才过,因为一个细节没有注意,WA了几次,纠错花了很久。。。#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define up(i,x,y,z) for(i=x;i<=y;i+=z) #define mem(a,b) memset(a,b,sizeof(a)) #define w(x) while(x) int n,a[505][1005],i,j,vis[505],ans[505],cas=1; int main() { w((scanf("%d",&n),n)) { up(i,0,n-1,1) up(j,0,2*n-1,1) scanf("%d",&a[i][j]); up(i,0,n-1,1) { up(j,1,2*n-1,1) { if(a[i][j]!=a[i][j-1]) break; } if(j==2*n) { ans[0]=i; break; } } up(i,0,n-1,1) { int cnt=0; mem(vis,0); up(j,0,2*n-1,2) { if(!vis[a[i][j]]) { vis[a[i][j]]=1; cnt++; } } if(cnt==1&&ans[0]!=i) ans[1]=i; else if(cnt!=1)ans[cnt]=i; } printf("Case #%d:",cas++); up(i,0,n-1,1) printf(" %d",ans[i]); printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。