A. 아람 문자 문제 문제 설명: 아람어에서 단어는 객체만을 나타낼 수 있습니다. 아람어 단어에는 특성이 있습니다:

• 단어에 같은 문자가 한 번 이상 나타나지 않으면 루트입니다.
• 루트와 모든 순열은 동일한 객체를 나타냅니다.
• 단어 y의 루트 x는 y에 나타나는 모든 문자를 각 문자가 한 번만 포함하는 단어입니다. 예를 들어, "aaaa", "aa", "aaa"의 루트는 "a"이고, "aabb", "bab", "baabb", "ab"의 루트는 "ab"입니다.
• 아람어의 모든 단어는 루트와 동일한 객체를 나타냅니다.

고대 아람어 문서가 주어졌을 때, 문서에 언급된 서로 다른 객체의 수를 구해야 합니다. 입력: 첫 번째 줄에는 단어의 수 n(1≤n≤1000)이 주어집니다. 두 번째 줄에는 n개의 문자열 s₁, s₂, ..., sₙ이 주어집니다. 각 문자열의 길이는 1000을 넘지 않으며, 모든 문자는 소문자 영어 알파벳입니다. 출력: 주어진 고대 아람어 문서에 언급된 서로 다른 객체의 수를 출력합니다. 예시: 입력:

5
a aa aaa ab abb

출력:

2

입력:

3
amer arem mrea

출력:

1

해결 방법: 각 단어에 나타나는 고유 문자를 추출하여 새로운 문자열을 만들고, 이 문자열들을 집합에 저장합니다. 집합의 크기가 곧 서로 다른 객체의 수가 됩니다. 코드 구현:

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

int main() {
    int n;
    cin >> n;
    vector<string> words(n);
    for (int i = 0; i < n; i++) {
        cin >> words[i];
    }
    
    set<string> uniqueRoots;
    
    for (const string& word : words) {
        bool charExists[26] = {false};
        for (char c : word) {
            charExists[c - 'a'] = true;
        }
        
        string root;
        for (int i = 0; i < 26; i++) {
            if (charExists[i]) {
                root += 'a' + i;
            }
        }
        
        uniqueRoots.insert(root);
    }
    
    cout << uniqueRoots.size() << endl;
    return 0;
}

B. 망카라 게임 문제 설명: 망카라는 중동에서 유명한 게임입니다. 14개의 구멍이 있는 보드에서 진행되며, 각 구멍에는 aᵢ개의 돌이 있습니다. 플레이어가 움직일 때, 양수의 돌이 들어있는 구멍 하나를 선택합니다. 그는 그 구멍의 모든 돌을 가져오고, 이 돌들을 반시계 방향으로 다음 구멍들에 하나씩 재분배합니다. 14번째 구멍에 돌을 놓았다면, 다음 돌은 첫 번째 구멍에 놓입니다.

움직임이 끝난 후, 플레이어는 짝수 개의 돌이 들어있는 모든 구멍에서 돌을 모읍니다. 모은 돌의 수가 플레이어의 점수입니다. 레슬리는 최대 점수가 얼마나 될지 알고 싶어합니다. 입력: 한 줄에 14개의 정수 a₁, a₂, ..., a₁₄가 주어집니다. 각 aᵢ는 0 또는 홀수이며, 보드에는 최소 하나의 돌이 있습니다. 출력: 한 번의 움직임으로 얻을 수 있는 최대 점수를 출력합니다. 예시: 입력:

0 1 1 0 0 0 0 0 0 7 0 0 0 0

출력:

4

입력:

5 1 1 1 1 0 0 0 0 0 0 0 0 0

출력:

8

해결 방법: 구멍이 14개로 적으므로 모든 가능한 경우를 시뮬레이션할 수 있습니다. 각 구멍에서 돌을 꺼내 재분배한 후, 짝수 개의 돌이 있는 구멍에서 돌을 모아 점수를 계산하고 최대 점수를 찾습니다. 코드 구현:

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

typedef long long ll;

int main() {
    vector<ll> holes(15);
    for (int i = 1; i <= 14; i++) {
        cin >> holes[i];
    }
    
    ll maxScore = 0;
    
    for (int start = 1; start <= 14; start++) {
        if (holes[start] == 0) continue;
        
        vector<ll> tempHoles = holes;
        ll stones = tempHoles[start];
        tempHoles[start] = 0;
        
        int index = start + 1;
        while (stones > 0) {
            if (index > 14) index = 1;
            tempHoles[index]++;
            stones--;
            index++;
        }
        
        ll currentScore = 0;
        for (int i = 1; i <= 14; i++) {
            if (tempHoles[i] % 2 == 0) {
                currentScore += tempHoles[i];
            }
        }
        
        maxScore = max(maxScore, currentScore);
    }
    
    cout << maxScore << endl;
    return 0;
}

C. 발할라 공성전 문제 설명: 이바르는 라게르타에게 카테가트를 점령하려고 합니다. 전쟁이 시작되고 이바르의 전사들이 하나둘 쓰러집니다.

이바르는 n명의 전사를 주요 성문 앞에 일직선으로 배치합니다. i번째 전사는 (i-1)번째 전사 바로 뒤에 서 있습니다. 첫 번째 전사가 공격을 이끕니다.

각 공격자는 쓰러지기 전까지 aᵀ개의 화살을 막아낼 수 있으며, aᵢ는 i번째 전사의 체력입니다.

라게르타는 i분에 kᵢ개의 화살을 명령합니다. 화살은 하나씩 첫 번째 서 있는 전사에게 명중합니다. 모든 전사가 쓰러지고 현재 날아가는 화살이 지나간 후, 토르는 망치를 휘두르고 모든 전사가 이전 체력을 되찾아 다시 일어납니다. 즉, 모든 전사가 t분에 죽으면, t분 말에 모두 다시 서게 됩니다.

전투는 q분 동안 지속되며, 각 분마다 이바르에게 얼마나 많은 전사가 서 있는지 알려주어야 합니다. 입력: 첫 번째 줄에는 두 개의 정수 n과 q(1≤n,q≤200,000)가 주어집니다. 두 번째 줄에는 n개의 정수 a₁, a₂, ..., aₙ(1≤aᵢ≤10⁹)이 주어집니다. 세 번째 줄에는 q개의 정수 k₁, k₂, ..., kq(1≤kᵢ≤10¹⁴)가 주어집니다. 출력: q줄을 출력합니다. i번째 줄에는 i분 후에 서 있는 전사의 수를 출력합니다. 예시: 입력:

5 5
1 2 1 2 1
3 10 1 1 1

출력:

3
5
4
4
3

입력:

4 4
1 2 3 4
9 1 10 6

출력:

1
4
4
1

해결 방법: 전사들의 체력에 대한 누적 합을 계산하고, 누적 화살 수를 추적합니다. 누적 화살 수가 전체 체력 합을 초과하면 0으로 초기화합니다. 이진 탐색을 사용하여 현재 화살에 맞지 않은 전사의 수를 효율적으로 찾습니다. 코드 구현:

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

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    vector<ll> health(n);
    vector<ll> prefixSum(n + 1, 0);
    
    for (int i = 0; i < n; i++) {
        cin >> health[i];
        prefixSum[i + 1] = prefixSum[i] + health[i];
    }
    
    ll totalArrows = 0;
    
    while (q--) {
        ll arrows;
        cin >> arrows;
        totalArrows += arrows;
        
        if (totalArrows >= prefixSum[n]) {
            totalArrows = 0;
            cout << n << '\n';
            continue;
        }
        
        int remaining = n - (upper_bound(prefixSum.begin(), prefixSum.end(), totalArrows) - prefixSum.begin() - 1);
        cout << remaining << '\n';
    }
    
    return 0;
}

D. 유령 문제 설명: 유령들은 조화롭고 평화롭게 살아갑니다. 그들은 길을 막는 사람을 놀라게 하는 것 외에는 목적 없이 우주를 여행합니다.

우주에는 n개의 유령이 있으며, OXY 평면에서 움직입니다. 각 유령은 자신의 속도를 가지며, 이 속도는 시간에 따라 변하지 않습니다: →V = Vₓ→i + Vᵧ→j, 여기서 Vₓ는 x축 방향 속도이고, Vᵧ는 y축 방향 속도입니다.

유령 i는 경험 값 EXᵢ을 가지며, 이는 과거에 그를 놀리려고 했던 유령의 수를 나타냅니다. 두 유령이 특정 시점에 같은 카르테시안 좌표에 있을 때 서로를 놀립니다.

유령들은 일정한 속도로 움직이므로, 어떤 시점 이후에는 더 이상 놀림이 없습니다(안도할 일이군요!). 그리고 종족 경험 값 GX = Σᵢ₌₁ⁿ EXᵢ은 더 이상 증가하지 않습니다.

타임은 거성이었습니다. 그는 특정 시점 T에 카르테시안 평면의 사진을 찍었고, 놀랍게도 모든 유령들이 y = a·x + b 형태의 선에 정렬되어 있었습니다. 당신의 임무는 미래에 유령 종족의 경험 지수 GX가 얼마가 될지 계산하는 것입니다.

참고로, 타임이 사진을 찍을 때 GX는 이미 0보다 클 수 있습니다. 왜냐하면 많은 유령들이 [-∞, T] 구간의 어떤 시점에서 서로를 놀렸을 수 있기 때문입니다. 입력: 첫 번째 줄에는 세 개의 정수 n, a, b(1≤n≤200,000, 1≤|a|≤10⁹, 0≤|b|≤10⁹)가 주어집니다. 다음 n줄에는 각각 세 개의 정수 xᵢ, Vₓᵢ, Vᵧᵢ(-10⁹≤xᵢ,Vₓᵢ,Vᵧᵢ≤10⁹)가 주어집니다. xᵢ는 i번째 유령의 현재 x좌표이고(yᵢ = a·xᵢ + b).

모든 유령이 초기 위치가 다름이 보장됩니다. 즉, 모든 (i,j)에 대해 i≠j일 때 xᵢ≠xⱼ입니다. 출력: 한 줄에 미래의 유령 종족 경험 지수 GX를 출력합니다. 예시: 입력:

4 1 1
1 -1 -1
2 1 1
3 1 1
4 -1 -1

출력:

8

입력:

3 1 0
-1 1 0
0 0 -1
1 -1 -2

출력:

6

입력:

3 1 0
0 0 0
1 0 0
2 0 0

출력:

0

해결 방법: 문제는 유령의 경로가 교차하는 지점의 수를 찾는 것과 관련이 있습니다. 각 유령의 경로는 직선이며, 두 직선이 평행하지 않으면 교차합니다. T 시점에 모든 유령이 한 직선에 있으므로, 경로가 평행하려면 T 시점의 직선을 따라 움직여야 합니다. 경로가 평행하지 않으면 반드시 교차합니다. a·Vₓ - Vᵼ 값이 같은 유령들의 그룹을 찾고, 각 그룹 내에서 유령들이 서로 만나는 횟수를 계산합니다. 코드 구현:

#include <iostream>
#include <map>
#include <vector>
using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    ll a, b;
    cin >> n >> a >> b;
    
    map<ll, ll> lineCount;
    map<pair<ll, ll>, ll> pointCount;
    
    for (int i = 0; i < n; i++) {
        ll x, vx, vy;
        cin >> x >> vx >> vy;
        
        ll key = a * x - vy;
        lineCount[key]++;
        pointCount[{x, vy}]++;
    }
    
    ll totalCollisions = 0;
    
    for (auto& entry : lineCount) {
        ll count = entry.second;
        totalCollisions += count * (count - 1);
    }
    
    for (auto& entry : pointCount) {
        ll count = entry.second;
        totalCollisions -= count * (count - 1);
    }
    
    cout << totalCollisions << '\n';
    
    return 0;
}