UVA 618 - Doing Windows(数论)

2020-11-18 06:18

阅读:787

标签:style   blog   http   color   io   2014   

题目链接:618 - Doing Windows

题意:给定一个大小不能变的屏幕,和四个大小可以变的窗口,变化要保持长宽比,问这四个窗口能不能调整后全部放下正好填满屏幕,不能重叠
思路:情况一共就几种:4个叠一起,3个叠一起+一个,2个和2个,一个和两个叠一起在一个,把这几种情况全判断了就可以了,判断过程利用gcd,lcm可以求边长。
代码:
#include 
#include 

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 = 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 


UVA 618 - Doing Windows(数论),搜素材,soscw.com

UVA 618 - Doing Windows(数论)

标签:style   blog   http   color   io   2014   

原文地址:http://blog.csdn.net/accelerator_/article/details/24634197


评论


亲,登录后才可以留言!