首页 > 代码库 > UVA 618 - Doing Windows(数论)
UVA 618 - Doing Windows(数论)
题目链接:618 - Doing Windows
题意:给定一个大小不能变的屏幕,和四个大小可以变的窗口,变化要保持长宽比,问这四个窗口能不能调整后全部放下正好填满屏幕,不能重叠
思路:情况一共就几种:4个叠一起,3个叠一起+一个,2个和2个,一个和两个叠一起在一个,把这几种情况全判断了就可以了,判断过程利用gcd,lcm可以求边长。
代码:
#include <stdio.h> #include <string.h> long long gcd(long long a, long long b) { if (b == 0) return a; return gcd(b, a % b); } long long lcm(long long a, long long b) { return a / gcd(a, b) * b; } struct Win { long long x, y; bool scanf_() { scanf("%lld%lld", &x, &y); if (x == 0 || y == 0) return false; long long t = gcd(x, y); x /= t; y /= t; return true; } void swap() { long long t = x; x = y; y = t; } } win, w[4]; bool check1(Win a, Win b, Win c, Win d) { long long sum = 0; if (win.y % a.y) return false; sum += win.y / a.y * a.x; if (win.y % b.y) return false; sum += win.y / b.y * b.x; if (win.y % c.y) return false; sum += win.y / c.y * c.x; if (win.y % d.y) return false; sum += win.y / d.y * d.x; if (sum != win.x) return false; return true; } bool check(Win a, Win b, Win c, long long wx, long long wy) { if (wy <= wx / a.x * a.y) return false; long long yy = wy - wx / a.x * a.y; long long sum = 0; if (yy % b.y) return false; sum += yy / b.y * b.x; if (yy % c.y) return false; sum += yy / c.y * c.x; if (sum != wx) return false; return true; } bool judge3(Win a, Win b, Win c, long long wx, long long wy) { if (check(a, b, c, wx, wy) || check(b, a, c, wx, wy) || check(c, a, b, wx, wy)) return true; return false; } bool judge2(Win a, Win b, Win c, long long wx, long long wy) { if (judge3(a, b, c, wx, wy)) return true; a.swap(); b.swap(); c.swap(); if (judge3(a, b, c, wy, wx)) return true; return false; } bool check2(Win a, Win b, Win c, Win d) { long long sum = 0; if (win.x % d.x) return false; long long wy = win.x / d.x * d.y; if (wy >= win.y) return false; long long yy = win.y - wy; if (judge2(a, b, c, win.x, yy)) return true; if (yy % a.y) return false; sum += yy / a.y * a.x; if (yy % b.y) return false; sum += yy / b.y * b.x; if (yy % c.y) return false; sum += yy / c.y * c.x; int flag = 0; if (sum == win.x) flag = 1; return flag; } bool check3(Win a, Win b, Win c, Win d) { long long sum = 0; long long wy = lcm(a.y, b.y); if (wy >= win.y) return false; sum += wy / a.y * a.x; sum += wy / b.y * b.x; if (win.x % sum) return false; if (win.y <= win.x / sum * wy) return false; long long yy = win.y - win.x / sum * wy; sum = 0; if (yy % c.y) return false; sum += yy / c.y * c.x; if (yy % d.y) return false; sum += yy / d.y * d.x; if (win.x != sum) return false; return true; } bool judge() { if (check1(w[0], w[1], w[2], w[3])) return true; if (check2(w[0], w[1], w[2], w[3]) || check2(w[0], w[1], w[3], w[2]) || check2(w[0], w[3], w[2], w[1]) || check2(w[3], w[1], w[2], w[0])) return true; if (check3(w[0], w[1], w[2], w[3]) || check3(w[0], w[2], w[1], w[3]) || check3(w[0], w[3], w[1], w[2])) return true; return false; } bool solve() { if (judge()) return true; win.swap(); for (long long i = 0; i < 4; i++) w[i].swap(); if (judge()) return true; return false; } int main() { long long cas = 0; while (~scanf("%lld%lld", &win.x, &win.y) && win.x || win.y) { for (long long i = 0; i < 4; i++) w[i].scanf_(); printf("Set %lld: %s\n", ++cas, solve()? "Yes":"No"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。