A - Sum of Round Numbers
양의 정수 \(n\)이 주어진다.
어떤 양의 정수가 가장 큰 자리수를 제외한 숫자가 모두 0일 때, 이 정수를 round라고 한다.
\(n\)을 가장 적은 수의 round의 합으로 나타내야 한다.
당연하게도 모든 자리수의 숫자들을 분리하면 답이다.
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
vector <int> ans;
int n; cin >> n;
if (n / 10000) ans.push_back(n / 10000 * 10000);
n %= 10000;
if (n / 1000) ans.push_back(n / 1000 * 1000);
n %= 1000;
if (n / 100) ans.push_back(n / 100 * 100);
n %= 100;
if (n / 10) ans.push_back(n / 10 * 10);
n %= 10;
if (n) ans.push_back(n);
cout << ans.size() << '\n';
for (int it : ans) cout << it << ' ';
cout << '\n';
}
}
|
B - Same Parity Summands
양의 정수 \(n\)과 \(k\)가 주어진다.
\(n\)을 \(k\)개의 홀수 또는 \(k\)개의 짝수의 합으로 나타낼 수 있는지 여부를 판별하고, 가능하다면 그 해를 출력해야 한다.
\(n\)을 \(k-1\)개의 1 + 홀수 또는 \(k-1\)개의 2 + 짝수 형태로 나타낼 수 있는지 확인해보면 된다.
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
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
ll n, k; cin >> n >> k;
if (n >= k && (n - k + 1) % 2 == 1)
{
cout << "YES\n";
for (int i = 0; i < k - 1; i++) cout << "1 ";
cout << n - k + 1;
cout << '\n';
continue;
}
if (n >= 2 * k && (n - 2 * k + 2) % 2 == 0)
{
cout << "YES\n";
for (int i = 0; i < k - 1; i++) cout << "2 ";
cout << n - 2 * k + 2;
cout << "\n";
continue;
}
cout << "NO\n";
}
}
|
C - K-th Not Divisible by n
정수 \(n\)과 \(k\)가 주어진다.
\(n\)으로 나눠떨어지지 않는 \(k\)번째 수를 출력해야 한다.
\(k\)가 최대 \(10^9\)이므로 하나하나 확인하는 방법으로는 시간초과에 걸리게 된다.
연속된 수 \(n\)개마다 \(n\)의 배수가 아닌 수가 \(n-1\)개씩 존재한다.
따라서 다음과 같은 식으로 \(O(1)\)에 답을 찾을 수 있다.
$$\left\lfloor \frac{k-1}{n-1} \right\rfloor \times n + (k-1) \bmod (n-1) + 1$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
ll n, k; cin >> n >> k;
k--;
ll ans = k / (n - 1) * n + k % (n - 1) + 1;
cout << ans << '\n';
}
}
|
D - Alice, Bob and Candies
\(n\)개의 사탕이 있다.
이 사탕의 크기는 각각 \(a_i\)이다.
Alice는 사탕을 왼쪽에서부터, Bob은 오른쪽에서 부터 차례대로 사탕을 먹눈더,
각각의 차례마다 두 사람은 현재 먹는 사탕의 크기의 합이 상대가 먹은 사탕의 크기의 합보다 크면서, 가장 적은 개수의 사탕을 먹어야 한다.
모든 사탕을 먹고 난 후에 두 사람이 총 사탕을 먹은 횟수와, Alice가 먹은 사탕의 크기의 합, Bob이 먹은 사탕의 크기의 합을 출력해야 한다.
단순 구현 문제이므로, 해설은 없다.
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
int a[1001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
int ans1 = 0, ans2 = 0;
int lptr = 0, rptr = n - 1;
int last = 0;
int cnt = 0;
while (lptr <= rptr)
{
int cur = 0;
while (lptr <= rptr)
{
cur += a[lptr++];
if (cur > last) break;
}
ans1 += cur;
last = cur;
cnt++;
if (lptr > rptr) break;
cur = 0;
while (lptr <= rptr)
{
cur += a[rptr--];
if (cur > last) break;
}
ans2 += cur;
last = cur;
cnt++;
}
cout << cnt << ' ' << ans1 << ' ' << ans2 << '\n';
}
}
|
E - Special Elements
길이 \(n\)인 수열 \(a\)가 주어진다.
어떤 수열의 원소 \(a_i\)가 길이 2이상의 연속된 원소의 합으로 나타내어질 수 있다면, 이 원소를 특별한 원소라고 한다.
수열이 주어지면, 특별한 원소의 개수를 출력해야 한다.
단, 메모리는 최대 \(O(n)\)까지만 사용할 수 있다.
모든 부분 수열의 합을 \(O(n^2)\)에 확인할 수 있다.
\(a_i\)가 최대 \(n\)이므로, \(1 \le i \le n\)에 대하여, 부분 수열의 합이 \(i\)가 되는 경우가 존재하는지 저장함으로써 \(O(n)\)의 메모리만 사용하여 문제를 해결할 수 있다.
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
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
int a[8001];
int cnt[8001];
bool isUsed[8001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
memset(cnt, 0, sizeof cnt);
memset(isUsed, 0, sizeof isUsed);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
cnt[a[i]]++;
}
int ans = 0;
for (int i = 0; i < n; i++)
{
int sum = a[i];
for (int j = i + 1; j < n; j++)
{
sum += a[j];
if (sum > n) break;
if (cnt[sum] && !isUsed[sum])
{
ans += cnt[sum];
isUsed[sum] = 1;
}
}
}
cout << ans << '\n';
}
}
|
F - Binary String Reconstruction
정수 \(n_0, n_1, n_2\)가 주어진다.
다음 조건에 맞는 이진 문자열을 출력해야 한다.
문자열의 모든 길이 2의 부분 문자열에 대해,
1의 개수가 0개인 것이 \(n_0\)개,
1의 개수가 1개인 것이 \(n_1\)개,
1의 개수가 2개인 것이 \(n_2\)개 존재한다.
주어지는 입력에 대해 답이 무조건 존재함이 보장된다.
다양한 풀이가 있을 수 있는데,
본인은 0을 \(n_0+1\)개, 1을 \(n_1+1\)개 나열한다음, 나머지를 010101... 로 채웠다.
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
39
40
41
42
43
44
45
46
47
48
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
int n0, n1, n2; cin >> n0 >> n1 >> n2;
string ans;
if (n0)
{
ans += '0';
for (int i = 0; i < n0; i++) ans += '0';
}
if (n2)
{
if (!ans.empty()) n1--;
ans += '1';
for (int i = 0; i < n2; i++) ans += '1';
}
if (n1)
{
if (ans.empty()) ans += '0';
for (int i = 0; i < n1; i++)
{
if (ans.back() == '0') ans += '1';
else ans += '0';
}
}
cout << ans << '\n';
}
}
|
G - Special Permutation
인접한 두 수의 차이가 모두 2 이상 4 이하인 \(n\)길이의 순열을 하나 찾아야 출력해야한다.
불가능하다면 -1을 출력한다.
역시 다양한 풀이가 존재한다.
우선 \(n\)이 4보다 작다면 조건을 만족하는 순열은 존재하지 않는다.
\(\{1,4,2,6,3,5\}\) 순서대로 6개의 수를 반복하면 수열을 계속 늘릴 수 있게 된다.
위의 규칙으로 수를 쭉 써내려가다가 남아 있는 수가 9개 이하가 되면 "끝내기 수열"을 미리 만들어둔 다음 그 순서대로 남은 수들을 출력했다.
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
39
40
41
42
43
44
45
46
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int last[6][10] =
{
{3,1,4,2},
{1,4,2,5,3},
{1,4,2,6,3,5},
{1,4,2,6,3,5,7},
{1,4,2,6,8,5,3,7},
{1,4,2,6,8,5,3,7,9}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
int n; cin >> n;
if (n < 4)
{
cout << "-1\n";
continue;
}
int c = 0;
while (n >= 10)
{
for (int i = 0; i < 6; i++) cout << c * 6 + last[2][i] << ' ';
c++;
n -= 6;
}
for (int i = 0; i < n; i++) cout << c * 6 + last[n - 4][i] << ' ';
cout << '\n';
}
}
|
'문제 풀이 > Codeforces' 카테고리의 다른 글
Codeforces Round #642 (Div. 3) (0) | 2020.05.15 |
---|---|
Codeforces Round #641 (Div. 1, Div. 2) (0) | 2020.05.13 |
Codeforces Round #639 (Div. 1, Div. 2) (0) | 2020.05.08 |
Codeforces Round #638 (Div. 2) (0) | 2020.05.04 |
Educational Codeforces Round 86 (0) | 2020.04.27 |