조건
1. 유저의 handle이 주어진다.
2. 최대 row 5, column 20 내에서 출력하고자 한다.
3. 딱 떨어지지 않는 부분은 asterisk *로 대체하는데 가장 많이 row별로 * 개수의 차이가 최대 1이어야 한다.
4. 가능한한 row가 작게 출력하려고 한다.
해법
3번이 좀 헷갈릴 수 있다.
예를들어 길이 43짜리 handle이 주어졌다고 하자.
row가 2면 col이 23이 되어 조건2 를 위반하므로 pass
row가 3이면 column이 15이므로 조건 2를 만족한다. 그리고 딱 떨어지게 출력하려고 하므로
채워야 하는 asterisk는 2개임을 알 수 있는데
3번 조건을 위반하는 경우는 (2,0,0) (0,2,0) (0,0,2) 이 세가지 경우이다.
만족하는 경우는 (1,1,0) (1,0,1) (0,1,1) 세가지 경우가 있다. 감이 슬슬 잡힌다.
asterisk를 최대한 uniform하게 분산시키라는 이야기이다. asterisk의 위치는 상관없다.
이것만 알면 이제 나머지는 구현이다.
분명 좀 더 깔끔하게 하는 방법이 있겠지만 급해서 마구잡이로 코딩했다.
#include <iostream> #include <queue> #include <map> #include <set> #include <vector> #include <string.h> #include <string> #include <algorithm> using namespace std; string s; int c[101]; char res[6][101]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> s; int len = s.length(); for (int i = 1; i < 101; ++i) c[i] = i; for (int i = 1; i < 101; ++i) c[i] += c[i - 1]; if (s.length() <= 20) { cout << "1 " << s.length() << '\n'; cout << s; return 0; } int llen = 0, ll = 0; for (int i = 2; i < 6; ++i) { llen = ((len + i - 1) / i); if (llen > 20) continue; int dif = llen * i - len; int rest = dif - (dif / i)*i; ll = i; for (int k = 0, j; k < i; ++k) { for (j = 0; j < dif / i; ++j) res[k][j] = '*'; if (rest) res[k][j] = '*', rest--; } break; } cout << ll << " " << llen << '\n'; for (int i = 0, x = 0, y = 0; i < len; ++i) { while (res[x][y] == '*') { y++; if (y == llen) y = 0, x++; } res[x][y] = s[i]; y++; if (y == llen) y = 0, x++; } for (int i = 0; i < ll; ++i) cout << res[i] << '\n'; return 0; } | cs |
'codeforces > #522 div2' 카테고리의 다른 글
| A. Kitchen Utensils (0) | 2018.11.19 |
|---|