A. LL

문제 설명: 입력된 문자열이 대소문자 구분 없이 "lovelive"와 정확히 일치하는지 판별하는 문제입니다. 문자열 길이는 최대 100이며, 입력은 최대 100개의 그룹으로 제공됩니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string input;
    while (getline(cin, input)) {
        transform(input.begin(), input.end(), input.begin(), ::tolower);
        if (input == "lovelive") cout << "yes\n";
        else cout << "no\n";
    }
    return 0;
}

B. 이상한 덧셈

문제 설명: 두 개의 10진수를 더하되, 각 자리에서의 합이 10을 넘어도 올림을 하지 않고 10으로 나눈 나머지만 결과로 취합니다. 입력은 최대 1000개의 그룹이며, A, B는 10^9 이하입니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string numA, numB;
    while (cin >> numA >> numB) {
        reverse(numA.begin(), numA.end());
        reverse(numB.begin(), numB.end());
        int maxLen = max(numA.length(), numB.length());
        vector<int> result(maxLen, 0);
        for (int i = 0; i < maxLen; ++i) {
            int digitA = (i < numA.length()) ? numA[i] - '0' : 0;
            int digitB = (i < numB.length()) ? numB[i] - '0' : 0;
            result[i] = (digitA + digitB) % 10;
        }
        reverse(result.begin(), result.end());
        int start = 0;
        while (start < maxLen && result[start] == 0) ++start;
        if (start == maxLen) cout << "0\n";
        else {
            for (int i = start; i < maxLen; ++i) cout << result[i];
            cout << "\n";
        }
    }
    return 0;
}

C. 핸드폰 꺼내기

문제 설명: a개의 iPhone X와 b개의 Galaxy S8이 있을 때, k번째로 꺼낸 핸드폰이 S8일 확률을 구합니다. 각 테스트 케이스마다 a, b, k가 주어집니다 (1 ≤ T ≤ 10000, 각 변수는 10^9 이하).

#include <cstdio>
int main() {
    int t;
    long long a, b, k;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld %lld %lld", &a, &b, &k);
        printf("%.3f\n", (double)b / (a + b));
    }
    return 0;
}

D. zzq의 이산수학 교실 1

문제 설명: 구간 [L, R] (1 ≤ L, R ≤ 10^6) 내의 정수들로 구성된 하세 그래프에서, '나누어짐' 관계에 의해 연결된 간선의 개수를 구합니다. 간선은 a < b이고 b % a == 0이며, a와 b 사이에 c (a < c < b)가 없어 b % c == 0이고 c % a == 0인 경우에만 연결됩니다. 입력은 최대 1000개의 그룹입니다.

#include <cstdio>
#include <vector>
using namespace std;

const int MAX = 1000000;
vector<int> primes;

void sieve() {
    bool isPrime[MAX + 1];
    fill(isPrime, isPrime + MAX + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= MAX; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= MAX; j += i) isPrime[j] = false;
        }
    }
    for (int i = 2; i <= MAX; ++i) {
        if (isPrime[i]) primes.push_back(i);
    }
}

int main() {
    sieve();
    int l, r;
    while (scanf("%d %d", &l, &r) == 2) {
        long long ans = 0;
        for (int p : primes) {
            int count = r / p - l + 1;
            if (count > 0) ans += count;
            else break;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

E. 미라를 내 집으로

문제 설명: 1번 도시에서 n번 도시까지의 최단 경로를 찾는 문제입니다. 그래프는 n개의 노드(2 ≤ n ≤ 200,000)와 m개의 간선(m ≤ 200,000)으로 구성되며, 각 간선의 가중치는 100,000 이하입니다. 도달할 수 없으면 "qwb baka"를 출력합니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> Edge;

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        vector<vector<Edge>> graph(n + 1);
        for (int i = 0; i < m; ++i) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }
        vector<int> dist(n + 1, INT_MAX);
        priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
        dist[1] = 0;
        pq.push({0, 1});
        while (!pq.empty()) {
            int currentDist = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            if (currentDist > dist[u]) continue;
            for (auto& [v, w] : graph[u]) {
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        if (dist[n] == INT_MAX) printf("qwb baka\n");
        else printf("%d\n", dist[n]);
    }
    return 0;
}

G. 미로 탈출

문제 설명: n x m 그리드에서 'P'(시작점), 'K'(열쇠, 최대 50개), 'E'(출구)가 있습니다. 장애물 '#'을 피해 이동하며, 열쇠를 획득한 후 출구로 나가는 최소 시간을 구합니다. T ≤ 50, n,m ≤ 500.

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 1e9;
int n, m;
char grid[505][505];
int distStart[505][505], distEnd[505][505];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};

void bfs(int sx, int sy, int dist[][505], bool ignoreExit) {
    for (int i = 0; i < n; ++i) fill(dist[i], dist[i] + m, INF);
    queue<pair<int, int>> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '#') continue;
            if (ignoreExit && grid[nx][ny] == 'E') continue;
            if (dist[nx][ny] > dist[x][y] + 1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; ++i) scanf("%s", grid[i]);
        int px, py, ex, ey;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 'P') { px = i; py = j; }
                if (grid[i][j] == 'E') { ex = i; ey = j; }
            }
        }
        bfs(px, py, distStart, true);
        bfs(ex, ey, distEnd, false);
        int ans = INF;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 'K') {
                    ans = min(ans, distStart[i][j] + distEnd[i][j]);
                }
            }
        }
        if (ans >= INF) printf("No solution\n");
        else printf("%d\n", ans);
    }
    return 0;
}

H. 수학 시험

문제 설명: n개의 문제(ai는 점수)에서 길이가 k인 두 개의 연속되지 않은 구간을 선택하여 최대 점수를 구합니다. 두 구간은 겹칠 수 없습니다. n ≤ 200,000, 2k ≤ n.

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, k;
        scanf("%d %d", &n, &k);
        int arr[200005];
        for (int i = 0; i < n; ++i) scanf("%d", &arr[i]);
        long long prefix[200005] = {0};
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + arr[i];
        long long maxFirst = -1e18;
        long long ans = -1e18;
        for (int i = k; i + k <= n; ++i) {
            maxFirst = max(maxFirst, prefix[i] - prefix[i - k]);
            ans = max(ans, maxFirst + prefix[i + k] - prefix[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

L. 햄스터 사육 계획

문제 설명: 작은 선반(a개, 각 1개의 케이지)과 큰 선반(b개, 각 2개의 케이지)이 있습니다. 같은 주인의 케이지만 큰 선반에 함께 넣을 수 있습니다. n명의 주인이 각각 Pi마리의 햄스터를 가지고 있을 때, 모든 케이지를 배치할 수 있는지 판별합니다. T ≤ ?, a,b ≤ 100, Pi ≤ 20.

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int small, large, n;
        scanf("%d %d %d", &small, &large, &n);
        int pets[55];
        for (int i = 0; i < n; ++i) scanf("%d", &pets[i]);
        sort(pets, pets + n, greater<int>());
        bool possible = true;
        for (int i = 0; i < n; ++i) {
            int count = pets[i];
            while (count > 0) {
                if (count >= 2 && large > 0) {
                    count -= 2;
                    large--;
                } else if (small > 0) {
                    count--;
                    small--;
                } else if (large > 0) {
                    count--;
                    large--;
                } else {
                    possible = false;
                    break;
                }
            }
            if (!possible) break;
        }
        printf(possible ? "Yes\n" : "No\n");
    }
    return 0;
}