USACO - 2주차

이기훈·2021년 1월 10일
0

Odometer

문제

범위 X, Y가 주어지는데, X ~ Y 사이에 숫자가 총 2개로만 만들어진 수에서 한 개는 1번만 사용한 수들의 개수를 구하는 문제

  • Ex) 33323(YES) 110(YES) 9779(NO)

해결

총 2개로만 사용할 수 있으므로, 0 ~ 9 2개를 뽑아서 그것으로만 이룰 수 있는 수를 만들면 된다.

0을 사용하는 경우, 0을 시작에 사용하는 부분만 따로 처리가 필요하다. 또 두번째 수 사용 유무에 대해서만 체크를 해주면 된다. X가 100부터 시작하므로, 첫번째 수 사용 유무는 필요가 없다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll l, r;
int ans = 0;

// 현재 값 : x , 첫번째 값, 두번째 값, 두번째 수 사용 유무
void go(ll x, ll y, ll z, bool f) {
    if (x > r) return;
    if (x >= l && f) {
        ans += 1;
    }
    if (y != 0)
        go(x * (ll)10 + y, y, z, f);
    else {
        if (x != 0) {
            go(x * (ll)10 + y, y, z, f);
        }
    }

    if (!f) {
        if (z == 0) {
            if (x != 0)
                go(x * (ll)10 + z, y, z, true);
        } else
            go(x * (ll)10 + z, y, z, true);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> l >> r;

    for (int i = 0; i <= 9; i++) {
        for (int j = 0; j <= 9; j++) {
            if (i == j) continue;
            go(0, i, j, false);
        }
    }

    cout << ans << '\n';
}

Fair Photography

문제

소가 N마리 X축 위에 유니크하게 있고, 각자 G, H라는 이름을 가지고 있다. 여기서 사진을 찍어야하는데 G와 H가 홀로 나오거나 G와 H가 동등하게 나오도록 사진을 찍는 거리를 구하는 문제

G가 홀로 나오는 경우 G G G G

H가 홀로 나오는 경우 H H H H

G와 H가 동등하게 나오는 경우 G H G H

설명

G와 H가 홀로 나오는 경우는 연속으로 G 또는 H가 나오는 개수를 구해주면 되므로 O(N)만에 해결이 가능하다.

G와 H가 동등하게 나오는 경우는 G를 1, H를 -1로 두었을 때, 연속된 부분합이 0을 찾는 문제로 변형이 가능

구간합을 먼저 구해준다.

P구간 합
00
11
20
31
42
51
62

0을 찾는 문제에서 규칙이 있는데, P[x] - P[y] = 0이 0이 되는 구간이다. 예를들어 10에서 왼쪽으로 0이 되는 가장 긴 위치를 찾을려면 P[1]을 찾으면 된다. P[10] = 1, P[1] = 1 이므로, P[10] - P[1] = 0이 되기 때문에 이 성질을 이용하여 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

map<int, int> m;
map<int, bool> check;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    vector<pair<int, int>> v;
    for (int i = 0; i < n; i++) {
        int x;
        char y;
        cin >> x >> y;
        if (y == 'G')
            v.push_back({x, 1});
        else
            v.push_back({x, -1});
    }

    sort(v.begin(), v.end());
    int sum = 0;
    int ans = 0;
    check[0] = true;
    m[0] = -1;
    int s = 0;
    for (int i = 0; i < n; i++) {
        s = 1;
        while (i + s < n && v[i + s].second == v[i].second) {
            s += 1;
        }
        ans = max(ans, v[i + s - 1].first - v[i].first);
        i += (s - 1);
    }

    for (int i = 0; i < n; i++) {
        sum += v[i].second;
        if (!check[sum]) {
            check[sum] = true;
            m[sum] = i;
        } else {
            ans = max(ans, v[i].first - v[m[sum] + 1].first);
        }
    }
    cout << ans << '\n';
}

Ceil Divisions

문제

https://codeforces.com/contest/1469/problem/D

길이가 N인 배열이 주어지고, A[i] = i (i = 1, 2,..., n)라고 가정할 때, 두 개의 원소(x, y)를 선택해 A[x] = ceil(A[x] / A[y]) 로 바꿀 수 있다고 가정할 경우 n - 1개의 원소를 1로, 1개의 원소를 2로 만드는 방법 n + 5번 이하로 하는 방법을 구하시오.

입력 : 4

1 2 3 4

1. x = 3, y = 4

  • A[3] = ceil(3 / 4) = 1, A = [1, 2, 1, 4]

2. x = 4, y = 2

  • A[4] = ceil(4 / 2) = 2, A = [1, 2, 1, 2]

3. x = 4, y = 2 ->

  • A[4] = ceil(2 / 2) = 1, A = [1, 2, 1, 1]

풀이

2, 4, 16, 256, 65536, N만을 남겨두고 나머지를 전부 1로 만든다.

그러면 A = [1, 2, 1, 4, 1, ..., N] 형태가 되고, 우리는 2, 4, 16, ..., N에서 가장 큰 수를 가장 작은 수로 2번 나눠 1를 만들면 된다.

N = 17이라고 가정,

2, 4, 16, 17을 제외한 나머지를 전부 1로 만든다. (17을 y로 잡으면 전부 1로 만들 수 있다.)

17을 16으로 2번 나눈다. (17/16) = 2, (2/ 16) = 1

16을 4로 2번 나눈다. (16/4) = 4, (4/4) = 1

... (반복)

A = [1, 2, 1, 1, 1, ..., 1] 형태로 만들 수 있다.

그러면 N + 5번이하로 모든 수들을 조건에 맞게 만들 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int d[200001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;
    d[2] = 1;
    d[4] = 1;
    d[16] = 1;
    d[256] = 1;
    d[65536] = 1;
    while (t--) {
        int n;
        cin >> n;
        vector<int> ans;
        ans.push_back(2);
        if (4 < n) ans.push_back(4);
        if (16 < n) ans.push_back(16);
        if (256 < n) ans.push_back(256);
        if (65536 < n) ans.push_back(65536);
        ans.push_back(n);

        vector<pair<int, int>> v;
        for (int i = n - 1; i > 1; i--) {
            if (d[i]) continue;
            v.push_back({i, n});
        }

        for (int i = ans.size() - 1; i > 0; i--) {
            if (ans[i] > n) continue;
            v.push_back({ans[i], ans[i - 1]});
            v.push_back({ans[i], ans[i - 1]});
        }
        cout << (int)v.size() << '\n';
        for (int i = 0; i < v.size(); i++) {
            cout << v[i].first << ' ' << v[i].second << '\n';
        }
    }
}

0개의 댓글