a,b개의 빨강, 파랑 타일이 주어진다.
이 두개를 잘 섞어서 다음 조건을 만족할 때 둘레의 길이의 최소값을 구하는 문제다.
1. 둘다 모두 써야한다.
2. 어느 한 부분만 돌출되어도 안되고 중간이 비어서도 안되며 정확히 꽉찬 직사각형 형태를 이뤄야 한다.
3. 두 색 중 반드시 하나는 직사각형 내부에서 직사각형 형태를 띄고 있어야 한다.
사각형의 특성상 같은 타일 개수를 사용했을 때 정사각형일 때가 가장 둘레의 길이가 적다.
a혹은 b가지고 그 직사각형 내부에서 직사각형을 형성할 수 있는지 확인하면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <iostream> #include <algorithm> #include <math.h> using namespace std; typedef long long ll; ll a, b, s; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> a >> b; s = a + b; if (a > b) swap(a, b); ll i = sqrt(s); ll ans = 2e17; for (; i >= 1; --i) if ((s%i) == 0) { ll r = sqrt(a), f = 0; r = min(r, i); for (ll j = r; j >= 1; --j) { if ((a%j) == 0 && j <= i && (a / j) <= (s / i)) { cout << (i * 2 + (s / i) * 2); return 0; } } if (!f) { r = sqrt(b); r = min(r, i); for (ll j = r; j >= 1; --j) { if ((b%j) == 0 && j <= i && (b / j) <= (s / i)) { cout << (i * 2 + (s / i) * 2); return 0; } } } } return 0; } | cs |
'codeforces > #506 div3' 카테고리의 다른 글
| D. Concatenated Multiples (0) | 2018.08.29 |
|---|---|
| C. Maximal Intersection (0) | 2018.08.29 |
| B. Creating the Contest (0) | 2018.08.29 |
| A. Many Equal Substrings (0) | 2018.08.29 |