🐷大肚肚
CF-53B普及+/提高

博客照片

2.0s💾 256MB

📋 题目描述

某博客的照片上传功能为:对于一张原照片,系统会裁剪其中的一个矩形部分上传,这个矩形部分被称为 “ 上传矩形 ” 。上传矩形的高宽比的合法取值范围为 0.80.81.251.25。另外,上传矩形至少要有一条边的长度等于 2x2^xxx 为整数 )且各边长度都为正整数。现在给出原照片的高度 hh 和宽度 ww ,请你求出一个最大面积合法上传矩形,并给出它的高和宽 。

📥 输入格式

仅有一行包含两个整数 hhww ( 1h,w1091\le h,w\le 10^9 ) ,分别表示原照片的高和宽。

📤 输出格式

仅有一行包含两个整数,分别表示上传矩形的高和宽,如果有多个答案,则输出高最大的那一个。

📝 样例 1

输入
2 1
输出
1 1

📝 样例 2

输入
2 2
输出
2 2

📝 样例 3

输入
5 5
输出
5 4

📚 来源

💡 题目讲解

1

理解题意

h×wh \times w 的原照片里裁剪一个矩形,满足三个条件:

① 高宽比在 [0.8,1.25][0.8, 1.25] 之间 — 即 0.81.250.8 \le \frac{高}{宽} \le 1.25。不能太扁,也不能太窄。

② 至少一条边是 2x2^x — 即 1, 2, 4, 8, 16, ... 中的某个数。只要高或宽中有一个就行。

③ 边长不超过原照片 — 高 h\le h,宽 w\le w

🎯 找面积最大的合法裁剪。面积相同选高最大的。


用样例 1(h=2,w=1h=2, w=1)试试:

原照片 2×1。可能的 2^x 边长:1, 2。

尝试以哪边 = 2^x另一边检查
高=1,宽=1高=1(=2⁰)=min(w,1.25×1)=1宽 = \min(w, 1.25 \times 1) = 10.81/11.250.8 \le 1/1 \le 1.25
高=2,宽=1高=2(=2¹)0.8×2=1.6宽 \ge 0.8 \times 2 = 1.6,但 w=1w=1
高=1,宽=2宽=2(=2¹)=2>w=1宽=2 > w=1

只有 1×1 合法 → 答案 "1 1" ✅。

1 / 5