본문 바로가기

문제 풀이/Codeforces

Codeforces Round #640 (Div. 4)

 

A - Sum of Round Numbers

 

Problem - A - Codeforces

 

codeforces.com

양의 정수 \(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<intint> 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

 

Problem - B - Codeforces

 

codeforces.com

양의 정수 \(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<intint> 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

 

Problem - C - Codeforces

 

codeforces.com

정수 \(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<intint> 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

 

Problem - D - Codeforces

 

codeforces.com

\(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<intint> 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

 

Problem - E - Codeforces

 

codeforces.com

길이 \(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<intint> 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, 0sizeof cnt);
        memset(isUsed, 0sizeof 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

 

Problem - F - Codeforces

 

codeforces.com

정수 \(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<intint> 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

 

Problem - G - Codeforces

 

codeforces.com

인접한 두 수의 차이가 모두 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<intint> 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