(2020년 12월 18일에 작성한 글입니다.)
Dashboard - Codeforces Round #690 (Div. 3) - Codeforces
codeforces.com
A.
그냥.. 잘 출력하면 된다
N이 홀수일 때는 마지막에 중앙에 있는 값 출력해줘야되고
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int i;
cin >> T;
while (T--) {
cin >> N;
vector<int> arr(N + 5);
for (i = 0; i < N; i++) {
cin >> arr[i];
}
for (i = 0; i < N / 2; i++) {
cout << arr[i] << ' ' << arr[N - 1 - i] << ' ';
}
if (N % 2 == 1) {
cout << arr[N / 2];
}
cout << '\n';
}
return 0;
}
B.
이걸
두 번이나 틀리다니
ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
2020 Kick Start Round G에서 1번 문제 생각났다.
흠
여튼
처음에 틀린 이유는
처음에는 string 안에 2020이 있기만 하면 일단 YES인줄 알았는데 아니다.
있더라도 맨 앞이나 맨 뒤에 있어야 한다.
중간에 있으면, 문제에서 말하는 "작업"을 두 번 해야되는거니까.
그런 맥락에서 생각해보면
YES인 경우는
...2020
2...020
20...20
202...0
2020...
이거다.
이걸 잘 체크해주면 되는데
왜 때문인지 두 번째 제출에서 틀렸고
그냥 처음부터 다시 짜서 맞았다..
void YES() {
cout << "YES" << '\n';
}
void NO() {
cout << "NO" << '\n';
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
string s, check = "2020";
int i, j;
bool flag;
cin >> T;
while (T--) {
cin >> N;
cin >> s;
flag = true;
for (i = 0; i < 4; i++) {
if (s[i] != check[i]) {
flag = false;
break;
}
}
if (flag) {
YES();
continue;
}
flag = true;
for (i = N - 4; i < N; i++) {
if (s[i] != check[i - (N - 4)]) {
flag = false;
break;
}
}
if (flag) {
YES();
continue;
}
if (s[0] != '2' || s[N - 1] != '0') {
NO();
continue;
}
if (s[1] == '0' && s[2] == '2') {
YES();
continue;
}
if(s[1] == '0' && s[N-2] == '2'){
YES();
continue;
}
if(s[N-3] == '0' && s[N-2] == '2'){
YES();
continue;
}
NO();
}
return 0;
}
C.
흠... 이것도 처음에 틀렸다
문제에서, 가장 작은 걸 찾는거기 때문에
자릿수가 작을 수록 큰 수를 넣는 게 중요하고
자릿수 자체가 작아야 한다.
그래서 x를 9부터 1까지 내려가면서
합 중 남아있는 값이 x보다 크면
string에 x를 넣고,
아니면 남아있는 값을 넣고 종료
그러고 난 후에 string 뒤집어줬다.
그리고 애초에 N > 45면 불가능한 경우고.
처음에는...뭔가 착각해서 아예 잘못 풀었다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int i;
cin >> T;
while (T--) {
cin >> N;
if (N > 45) {
cout << -1 << '\n';
continue;
}
string ans = "";
for (i = 9; i >= 1 && N > 0; i--) {
if (N / 10 == 0 && N <= i) {
ans += N + '0';
break;
}
if (N >= i) {
ans += i + '0';
N -= i;
}
}
reverse(ans.begin(), ans.end());
cout << ans << '\n';
}
return 0;
}
D.
prefix sum을 만들어놓고
가장 처음 숫자부터, i번째 까지의 수의 합 s가 전체 합의 약수라면...
그리고 그 뒤로 s * 2, s * 3, ..., 전체 합까지 모두 prefix sum 중에 있다면
이건 가능한 경우인거다.
각 뭉터기의 합이 s라는거니까!
예를 들어
3 1 6 6 2 라면
prefix sum은
3 4 10 16 18 인데
3은 18의 배수니까 일단 가능한 경우다.
그 후에 6, 9, 12, 15 모두 등장해야 되는데
그렇지 않기 때문에 이건 불가능한 경우.
1 2 2 1이라면
prefix sum은
1 3 5 6
1은 6의 약수인데,
이후에 2, 3, 4, 5 모두 나와야하는데 안 나온다.
따라서 1은 안 되는 경우고
3은 3, 6이 등장하기 때문에 가능한 경우.
이런 식으로 한 다음에,
뭉터기 개수는 (전체 합) / s 이기 때문에
답은 N - (전체 합) / s
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
ll ans;
int i, j;
cin >> T;
while (T--) {
cin >> N;
vector<ll> arr(N + 5, 0);
for (i = 1; i <= N; i++) {
cin >> arr[i];
arr[i] += arr[i - 1];
}
ans = N - 1;
for (i = 1; i <= N; i++) {
if (arr[i] * 2 > arr[N]) {
break;
}
if (arr[N] % arr[i] == 0) {
bool flag = true;
for (j = 2; j <= arr[N] / arr[i]; j++) {
if (!binary_search(arr.begin() + i, arr.begin() + N + 1, arr[i] * j)) {
flag = false;
break;
}
}
if (flag) {
ans = min(ans, N - arr[N] / arr[i]);
}
}
}
cout << ans << '\n';
}
return 0;
}
E1.
K, M이 정해져 있기 때문에
단순 구현 문제였다
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
ll ans;
int i, j;
cin >> T;
while (T--) {
cin >> N;
vector<ll> arr(N + 5, 0);
for (i = 1; i <= N; i++) {
cin >> arr[i];
arr[i] += arr[i - 1];
}
ans = N - 1;
for (i = 1; i <= N; i++) {
if (arr[i] * 2 > arr[N]) {
break;
}
if (arr[N] % arr[i] == 0) {
bool flag = true;
for (j = 2; j <= arr[N] / arr[i]; j++) {
if (!binary_search(arr.begin() + i, arr.begin() + N + 1, arr[i] * j)) {
flag = false;
break;
}
}
if (flag) {
ans = min(ans, N - arr[N] / arr[i]);
}
}
}
cout << ans << '\n';
}
return 0;
}