UVALLive 7511 Multiplication Table(数学シミュレーション問題)
数字の行列をあげる不確定な数字を表し、このサブマトリクスが乗算表に存在する可能性があるかどうかを尋ねる.
題目の分析:すべて疑問符は明らかにできて、ただ1つの数字の列挙の約数と数字の座標は比較して、2つの数字に等しいことを上回って、それとも列挙の約数は残りの数字と一致するかどうかを判断します
題目の分析:すべて疑問符は明らかにできて、ただ1つの数字の列挙の約数と数字の座標は比較して、2つの数字に等しいことを上回って、それとも列挙の約数は残りの数字と一致するかどうかを判断します
#include
#include
#include
int const MAX = 1005;
double const EPS = 1e-10;
struct NUM
{
int x, y, val;
}num[MAX * MAX];
char s[MAX][9];
int main()
{
int T, n, m;
scanf("%d", &T);
for(int ca = 1; ca <= T; ca ++)
{
printf("Case #%d: ", ca);
int cnt = 0;
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
scanf("%s", s[j]);
if(s[j][0] != '?')
{
num[cnt].x = i + 1;
num[cnt].y = j + 1;
sscanf(s[j], "%d", &num[cnt ++].val);
}
}
}
if(cnt == 0)
{
printf("Yes
");
continue;
}
if(cnt == 1)
{
bool f = false;
int x_, y_;
for(int i = 1; !f && i <= (int)sqrt(num[0].val * 1.0); i++)
{
if(num[0].val % i == 0)
{
x_ = i;
y_ = num[0].val / i;
if((num[0].x <= x_ && num[0].y <= y_) || (num[0].y <= x_ && num[0].x <= y_))
f = true;
}
}
printf("%s
", f ? "Yes" : "No");
continue;
}
int x1, y1;
bool f = false;
for(int i = 1; !f && i <= (int)sqrt(num[0].val * 1.0); i++)
{
if(num[0].val % i == 0)
{
x1 = i;
y1 = num[0].val / i;
if(x1 >= num[0].x && y1 >= num[0].y)
{
if((x1 + num[1].x - num[0].x) * (y1 + num[1].y - num[0].y) == num[1].val)
{
bool f2 = true;
for(int j = 2; f2 && j < cnt; j++)
if((x1 + num[j].x - num[0].x) * (y1 + num[j].y - num[0].y) != num[j].val)
f2 = false;
if(f2)
f = true;
}
}
if(y1 >= num[0].x && x1 >= num[0].y)
{
if((y1 + num[1].x - num[0].x) * (x1 + num[1].y - num[0].y) == num[1].val)
{
bool f2 = true;
for(int j = 2; f2 && j < cnt; j++)
if((y1 + num[j].x - num[0].x) * (x1 + num[j].y - num[0].y) != num[j].val)
f2 = false;
if(f2)
f = true;
}
}
}
}
printf("%s
", f ? "Yes" : "No");
}
}