M_sea

洛谷4160 [SCOI2009]生日快乐
LuoguBZOJ分析还是写个题解吧qwq$n$很小,爆搜即可。每一块的长最小为$x/k$,宽最小为$y/k$,每...
扫描右侧二维码阅读全文
11
2019/01

洛谷4160 [SCOI2009]生日快乐

Luogu

BZOJ

分析

还是写个题解吧qwq

$n$很小,爆搜即可。

每一块的长最小为$x/k$,宽最小为$y/k$,每次切的长度一定是$x/k$或$y/k$的倍数。

然后就没了啊。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

inline double dfs(double x,double y,int k) {
    if (k==1) return max(x,y)*1.0/min(x,y);
    double ans=2e14,mx=x/k,my=y/k;
    for (re int i=1;i<=k/2;++i) {
        double t1=max(dfs(mx*i,y,i),dfs(x-mx*i,y,k-i));
        double t2=max(dfs(x,my*i,i),dfs(x,y-my*i,k-i));
        ans=min(ans,min(t1,t2));
    }
    return ans;
}

int main() {
    int x=read(),y=read(),n=read();
    printf("%.6lf\n",dfs(x,y,n));
    return 0;
}
最后修改:2019 年 01 月 11 日 02 : 49 PM

发表评论