KPU S/W 경진대회 본선 후기

+및-연산자를 사용하여a,…z 알파벳 소문자로작성된 산술 표현식을 고려하십시오.다음은 예입니다.

((a + b)-(((c + d) -e) + a))

완전히 괄호로 묶인 표현식은다음과 같은 간단한 규칙을 사용하여postfix라는 다른 형식으로 변환 할 수 있습니다.

변수는 그대로 유지됩니다.{a,…, z}의모든x에대해Translate [x] = x.
(E1 +E2)형태의 식은Translate[E1] Translate[E2] + 로 변환된다.
(E1 - E2)형태의 식은 Translate[E1] Translate[E2] - 로 변환된다.

예를 들어, 위의 표현식은 다음과 같이 번역됩니다.

 Translate[((a+b)-(((c+d)-e)+a))]
= Translate[(a+b)] Translate[(((c+d)-e)+a)] -
= Translate[a] Translate[b] + Translate[((c+d)-e)] Translate[a] + -
= a b + Translate[(c+d)] Translate[e] - a + -
= a b + Translate[c] Translate[d] + e - a + -
= a b + c d + e - a + -

당신의 임무는 이 작업의 반대를 수행하는 것입니다.

접미사로 표현되는 postfix 표현식을괄호로 잘 묶인원래 표현식으로 재구성해야합니다.

+,-및 문자a, b,…, z가포함된 postfix 표현식을 포함하는 단일 행

최대 80 개의 기호가 있습니다.

위에서 설명한 번역을 통해 입력postfix 표현식을괄호로 잘 묶인원래 표현식을 출력합니다.

ab+cd+e-a+-

((a+b)-(((c+d)-e)+a))

회문(Palindrome)은왼쪽에서 오른쪽으로 읽든, 오른쪽에서 왼쪽으로 읽든 똑같이 읽는 단어입니다.

다음과 같이 알파벳 소문자로만 이루어진 단어에서 회문을 생성하도록 합니다.

알파벳 소문자로 이루어진 단어 word가 있습니다.
word를 오른쪽에서 왼쪽으로 읽는 반전 단어 reverse를 생성합니다.
word와 reverse를 더합니다. 단어 덧셈은 아래 규칙을 따름니다.
덧셈을 한 단어가 회문이면 그 회문을 출력하고 아니면 단어 반전과 덧셈을 회문이 생성될 때 까지 계속합니다.


단어 덧셈 규칙

단어의 덧셈은 단어를 구성하는 알파벳을 26진수숫자로 ('a' = 0, 'b'=1, 'c'=2, ..., 'z'= 25) 가정해서 숫자 덧셈을 한 후 다시 알파벳으로 변환해서 단어를 생성합니다.다음과 같이 단어 덧셈을 할 수 있습니다.

'a' + 'a' = 'a'

'a' + 'b' = 'b'

'b' + 'b' = 'c'

'a' + 'z' = 'z'

'b' + 'z' = 'ba'

당신의 임무는 위에서 설명한 프로세스를 수행하고 결과 회문을 찾으면 출력하는 것입니다.

예를 들어 'see'가 주어지면  'see'의 반전 단어 'ees'를 생성해서 단어 덧셈을 하면 'wiw'를 얻습니다.

또한 'apple'이 주어지면 다음과 같은 시퀀스를 얻습니다.

'apple'

'fbfae'

'jbkbj'

따라서 이경우에는 'jbkbj' 를 출력해야 합니다.

회문을 찾지 못하는 경우는 없습니다.

알파벳 소문자로만 이루어진 길이 30이하의 단일 단어

위에서 설명한 프로세스에 의해 생성 된 회문인 단어

apple

jbkbj

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

//abcde/fghij/klmno/pqrst/uvwxy/z
char out_alp(int num)
{
    switch (num)
    {
    case 0:
        return 'a';
    case 1:
        return 'b';
    case 2:
        return 'c';
    case 3:
        return 'd';
    case 4:
        return 'e';
    case 5:
        return 'f';
    case 6:
        return 'g';
    case 7:
        return 'h';
    case 8:
        return 'i';
    case 9:
        return 'j';
    case 10:
        return 'k';
    case 11:
        return 'l';
    case 12:
        return 'm';
    case 13:
        return 'n';
    case 14:
        return 'o';
    case 15:
        return 'p';
    case 16:
        return 'q';
    case 17:
        return 'r';
    case 18:
        return 's';
    case 19:
        return 't';
    case 20:
        return 'u';
    case 21:
        return 'v';
    case 22:
        return 'w';
    case 23:
        return 'x';
    case 24:
        return 'y';
    case 25:
        return 'z';
    default:
        break;
    }
    return 0;
}

bool check(string str)
{
    int i, j = str.length() - 1;
    for (i = 0; i < str.length() / 2; i++, j--)
    {
        if (str[i] != str[j])
            return false;
    }
    return true;
}
void cal(string &str, string r_str, string &ans)
{
    char a2, b2;
    for (int i = str.length() - 1; i >= 0; i--)
    {
        int a = (str[i] - 'a' + r_str[i] - 'a') / 26;
        int b = (str[i] - 'a' + r_str[i] - 'a') % 26;
        if (a == 1)
            str[i - 1] += a;

        ans += out_alp(b);
    }
}

void rule(string &str)
{
    string ans = "";
    string r_str = str;

    reverse(r_str.begin(), r_str.end());
    cal(str, r_str, ans);
    str = ans;
}

int main()
{
    string input;
    cin >> input;

    while (!check(input))
    {
        rule(input);
    }

    cout << input;
    return 0;
}

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동
예를 들어 아래의 방법으로JAZ를 만들 수 있습니다.

첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.


만들고자 하는 이름 name이 입력으로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 출력하세요.

만들고자 하는 이름 name 이 첫번째 줄에 입력됩니다.

제한사항

name은 알파벳 대문자로만 이루어져 있습니다.
name의 길이는 1 이상 20 이하입니다.

이름에 대해 조이스틱 조작 횟수의 최솟값을 출력하세요.

JEROEN

56

JAN

23

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int sol(string name) {
    int answer = 0;
    int i=0;
    string tmp(name.length(),'A');

    while(1){
        tmp[i] = name[i];
        answer += (name[i] <= 'M') ? (name[i] - 'A') : ('Z' - name[i] + 1) ;
        if(!tmp.compare(name)) break;

        for(int mov = 1; mov < name.length() ; mov++){
            if(name [(i + mov) % name.length()] != tmp[(i + mov) % name.length()]){
                i =  (i + mov) % name.length();
                answer += mov;
                break;
            }
            else if(name [(i + name.length() - mov) % name.length()] != tmp[(i + name.length() - mov)% name.length()]){
                i = ( i + name.length() - mov ) % name.length();
                answer += mov;
                break;
            }
        }
    }
    return answer;
}
int main(){
    string input;
    cin >> input;
    cout << sol(input);
    return 0;
}

전세계적으로 퍼진 신종 코로나-19 감염병 예방을 위해서 김교수는 일렬로 배치된 N명(1≤N≤1000) 학생들에게 사회적 거리두기를 시행하고 있습니다.

그러나 이러한 사회적 거리두기에도 불구하고 이미 코로나-19에 감염된 학생과 반경 R 이내에 있는 다른 건강한 학생은 코로나-19에 감염됩니다.

김교수는 R값은 정확히 모르지만 N명 학생들의 위치와 감염여부는 알고 있습니다.

전체 N명 학생들이 전부 감염될 수 있는 최소한의 감염 학생 수를 결정하십시오.

입력의 첫번째 줄에는 학생 수 N

그 다음 N개 줄에는 각각 학생의 위치x(0≤x≤10^6)와 감염여부 s (0 : 건강한 학생, 1: 감염된 학생) 두 개의 정수를 갖습니다.

최소한 한명의 학생이 감염되면 반경 R이내의 학생들은 연속으로 코로나-19에 감염될 수 있습니다.

코로나-19 감염병이 전체 학생 N명에게 퍼질 수 있는 최소 학생 수를 출력하십시오.

예를 들어서 입력이 다음과 같다고 가정하면,

9
7 1
1 1
16 1
3 1
15 1
10 0
6 1
18 1
21 1
이 경우에 우리는 R < 3 임을 알 수 있습니다. 그렇지 않다면 7번 위치 학생이 10번 학생을 감염 시켰을 것입니다.

따라서 이 경우에는 최소한 4명 학생이 (1과 3 위치에 학생 중에서 한명, 6과 7 위치에 있는 한명, 15와 16과 18 위치 학생 중에서 한명, 21위치 학생 한명) 감염되어야 전체 학생들에게 감염을 시킵니다.

따라서 이 경우 정답은 4 입니다.

4

9
7 1
1 1
16 1
3 1
15 1
10 0
6 1
18 1
21 1

4

긴 장마철이 지나고 망가진 도로 보수를 위해서 시흥시는 시내의 모든 교차로를 재포장하기로 결정했습니다.

교차로를 포장하려면 해당 교차로를 통과하는 모든 교통을 통제해야 합니다.

그런데 교차로들 중에서 중요한 교차로는 교통 통제에 주의해야 합니다.

예를 들어서 교차로 J에서 교차로 K를 가려면 반드시 교차로 I를 통과해야 한다면, 교차로 I를 통제하면 J에서 K로 가는 길이 막히므로, 교차로 I를 중요한 교차로라고 합니다.

시흥시의 도로는모두 양방향 통행이 가능하며, 모든 교차로를 이용할 수 있다면 어느 교차로에서 든지 다른 교차로로 갈 수 있습니다.시흥시 도로의 이름은 오직 2개의 교차로를 연결하고 다른 교차로는 통과하지 않습니다.

예를 들어서5 개의 교차로I1,I2,I3,I4,I5가 있고  6개의 도로가있다고 가정합니다.

도로 1은I1과I2를연결합니다.
도로 2는I2와I3을연결합니다.
도로 3은I1과I3을연결합니다.
도로 4는I2와I4를연결합니다.
도로 5는I2와I5를연결합니다.
도로 6은I5와I4를연결합니다.
그러면 I2를 교통 통제하면 I4에서 I1 (혹은 I3)으로 가는 길이 없으므로 I2는 중요한 교차로 입니다.

또한 I5에서 I1 그리고 I5에서 I3로 가는 길도 끊깁니다. I2이외의 더 이상의 중요한 교차로는 없습니다.

당신이 할 일은 시흥시 교차로와 도로 정보를 살펴보고 중요한 교차로 목록을 결정하는 것입니다.

입력의 첫 번째 줄에는 두 개의 정수N과M이있습니다.

N은 시흥시의 교차로 수이고M은 도로 수입니다.

교차로의 번호는 1,2, ...,N이라고 가정합니다.

다음M개 줄(2, ...,M+1번째 줄)은 시흥시의 도로를 나타냅니다.

i+1번째 줄은도로i로연결된 교차로 쌍을 나타내는1, ...,N범위의 두 정수를 포함합니다.

N≤ 300, M≤ 50000 입니다.

출력의 첫 번째 줄에는 중요한 교차로 개수를 나타내는정수C를 출력합니다.

다음C개 줄에는한 줄 당 하나씩 중요한 교차로 번호를 출력합니다.

중요한 교차로가 여러개 이면 교차로 번호 오름 차순으로 출력합니다.

5 6
1 2
2 3
1 3
2 4
2 5
5 4

1
2

- A 교차로가 중요한 교차로가 아니라면,  A 교차로를 제외한 다른 임의의 교차로에서 시작해서 나머지 모든 교차로를 방문할 수 있다.
- A 교차로가 중요한 교차로라면,A 교차로를 제외한 다른 임의의 교차로에서 시작해서 나머지 모든 교차로들을 방문하려고 할 때 하나라도 방문하지 못하는 교차로가 존재한다.

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN공항에서 출발합니다.

항공권 정보가 담긴 tickets가 입력으로 주어질 때, 방문하는 공항 경로를 출력합니다.

모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 a b는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
동일한 경로를 가지는 항공권이 있을 수 있습니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 출력합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
입력으로 첫번째 줄에는 ticket의 개수가 주어지고 그 다음 N개 줄에는 항공권 정보를 나타냅니다.

다음과 같은 3장의 ticket에 대한 정보가 주어진다고 합시다.

3

ICN JFK

HND IAD

JFK HND

그러면 방문 순서는

ICN

JFK

HND

IAD

과 같습니다.

또 다른 예로 5장의 ticket에 대한 정보가 주어진다고 합시다.

5

ICN SFO

ICN ATL

SFO ATL

ATL ICN

ATL SFO

그러면

ICN

SFO

ATL

ICN

ATL

SFO

순으로 방문할 수도 있지만

ICN

ATL

ICN

SFO

ATL

SFO

가 알파벳 순으로 앞섭니다.

입력의 첫째 줄에는 ticket의 개수를 나타내는 단일 정수 N 이 나타납니다.

그 다음 N개 줄에는 각줄 마다 출발 공항 a와 도착 공항 b가 나타납니다.

방문 공항 순서대로 공항 이름을 한 줄에 하나씩 출력합니다.

3
ICN JFK
HND IAD
JFK HND

ICN
JFK
HND
IAD

5
ICN SFO
ICN ATL
SFO ATL
ATL ICN
ATL SFO

ICN
ATL
ICN
SFO
ATL
SFO

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

vector<vector<string>> all_routes;

void dfs(vector<vector<string>> tickets, vector<bool> &visited, int cnt, int start, vector<string> &route)
{
    visited[start] = true;
    route.push_back(tickets[start][0]);

    if (cnt == tickets.size())
    {
        route.push_back(tickets[start][1]);
        all_routes.push_back(route);
        route.pop_back();
        return;
    }
    for (int i = 0; i < tickets.size(); i++)
    {
        if (!visited[i] && tickets[start][1] == tickets[i][0])
        {
            dfs(tickets, visited, cnt + 1, i, route);
            visited[i] = false;
            route.pop_back();
        }
    }
}

vector<string> sol(vector<vector<string>> tickets)
{
    vector<string> route;
    vector<bool> visited;
    int cnt = 1;

    for (int i = 0; i < tickets.size(); i++)
    {
        if (tickets[i][0] == "ICN")
        {
            visited.assign(tickets.size(), false);
            route.clear();
            dfs(tickets, visited, cnt, i, route);
        }
    }
    sort(all_routes.begin(), all_routes.end());
    return all_routes[0];
}
int main()
{
    int N;
    cin >> N;
    vector<vector<string>> tickets(N, vector<string>(2, ""));
    vector<string> answer;
    for (int i = 0; i < N; i++)
    {
        cin >> tickets[i][0] >> tickets[i][1];
    }

    answer = sol(tickets);

    for (auto n : answer)
    {
        cout << n << endl;
    }
    return 0;
}

기상청은 매일 기상 위성에서 이미지를 수신합니다.이 이미지는어두운 배경에구름을 나타내는 흰색 영역이 있습니다.

기상청은 폭풍에 대해 다소 단순화 된 모델이 있습니다. 특정 크기를 초과하는 흰색 영역은 폭풍이 되어야 한다고 결정했습니다.

위성 이미지는#과. 으로 이루어진 격자 이미지이며 . 은 구름을나타냅니다.

위성 이미지 각 포인트에는 최대 8 개의 이웃 (북동, 북, 북서, 동, 서, 남동, 남, 남서)이 있으며, 구름은 이웃과 연속으로 이어진 . 으로 이루어집니다.

아래 위성 이미지는 4개의 구름을 가지고 있습니다.

#####.#####
####.####.#
###..##.#.#
##...######
######.....
###########


만약 폭풍으로 간주할 임계 크기를 4라고 하면, 크기가 4를 넘어가는 구름은 2개가 있으며 아래와 같이 숫자 1과 2의 영역으로 표시할 수 있습니다.

#####1#####
####1####.#
###11##.#.#
##111######
######22222
###########


당신이 할 일은위성 이미지와 폭풍으로 간주할 임계 값을 입력받아서,폭풍의 갯수와 가장 큰 폭풍의 크기를 결정하는 것입니다.

입력의 첫 번째 줄에는위성 이미지의 행과 열 수를 나타내는두 개의 정수M과 N이포함됩니다.

그 다음에는 위성 이미지를 설명하는M개줄이 나옵니다.

M+2번째 줄에는폭풍을 결정하는 임계 값K가 포함됩니다.

1 ≤M, N≤ 1000 입니다.

입력의 80 %에서1 ≤M, N≤ 60 입니다.

한 줄에 공백으로 구분 된 정수n과s는 각각 폭풍의 갯수와 가장 큰 폭풍의 크기를 나타냅니다.

6 11
#####.#####
####.####.#
###..##.#.#
##...######
######.....
###########
4

2 7

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int M, N;
int K;
int answer = 0, answer_max = 0;
int dir[8][2] = {{-1, 0}, {-1, -1}, {-1, 1}, {1, 1}, {1, -1}, {1, 0}, {0, -1}, {0, 1}};

void bfs(vector<vector<bool>> &map, int S_x, int S_y)
{
    int r = 1; //구름 넓이

    queue<pair<int, int>> q;
    map[S_y][S_x] = true;
    q.push(make_pair(S_x, S_y));
    int x,y,next_x,next_y;
    while (!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int i = 0; i < 8; i++)
        {
            next_x = x + dir[i][0];
            next_y = y + dir[i][1];

            if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && map[next_y][next_x] == false)
            {
                map[next_y][next_x] = true;
                q.push(make_pair(next_x, next_y));
                r++;
            }
        }
    }
    if (K < r)
    {
        answer_max = (answer_max < r) ? r : answer_max;
        answer += 1;
    }
}

int main()
{

    cin >> M >> N;

    vector<vector<bool>> arr(M, vector<bool>(N, true));

    for (int i = 0; i < M; i++)
    {
        int j = 0;
        string str;
        cin >> str;
        for (auto c : str)
        {
            if (c != '#')
            {
                arr[i][j] = false;
            }
            j++;
        }
    }
    cin >> K;

    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (arr[i][j] == false)
            {
                bfs(arr, j, i);
            }
        }
    }
    cout << answer << " " << answer_max;
    return 0;
}

숲은 직사각형 모양이며 나무는 균등 한 간격으로 배열되어 있습니다.

나무의 높이와 둘레가 다르기 때문에 목재 값은 나무마다 다릅니다.산림청은 각 나무에 대한 데이터를 수집했으며 숲의 각 나무에서 사용할 수있는 나무의 양 (입방 피트)을 알고 있습니다.

산림청은 이 정보를 정수의M×N배열형태로 유지합니다. 여기서(i, j)항목은i번째 행의j번째 나무의 양 (입방 피트)입니다.

행은 위에서 아래로 번호가 매겨지고 열은 왼쪽에서 오른쪽으로 번호가 매겨진다고 가정합니다.

예를 들어 배열이 다음과 같습니다.

위 배열의 위치 (3,4)에 있는 나무의 양은 15 입방 피트 입니다.

산림청은 숲의 직사각형의 토지에 목재의 총량을 계산하여 토지 임대 자료로 활용하려고 합니다.

직사각형은 왼쪽 상단 모서리와 오른쪽 하단 모서리의 나무 위치로 나타냅니다. 예를 들어서 위치 (2,2) 와 (3,4) 모서리를 가지는 직사각형은 아래 그림과 같습니다.

이 직사각형 토지의 목재 총량은 76 입방 피트입니다.

마찬가지로 직사각형 모서리가 (4,2)와 (4,2)인 경우의 목재양은 하나 뿐인 나무의 양 20 입방 피트입니다.

당신의 임무는 삼림청에서 지정한 직사각형 토지의 목재 총량을 계산하는 것입니다.

입력의 첫 번째 줄에는 숲의 나무 행과 열을 나타내는 두 개의 정수 M과 N

다음 M개 줄에는 각각 N개의 정수가 있습니다.

숲의 i행 j열 위치의 나무 양은 입력의 i+1번째 줄의 j번째 정수로 나타냅니다.

M+2번째 줄에는 목재 총량을 계산해야 하는 직사각형 토지의 개수 C를 나타냅니다.

이어지는 C개 줄 (M+2+1번째 줄 ... M+2+C번째 줄)에는 4개의 정수 r1, c1, r2, c2 (r1≤r2, c1≤c2)가 직사각형의 2개 모서리를 나타냅니다.

(r1,c1)은 좌측 상단 모서리, (r2,c2)는 우측 하단 모서리를 나타냅니다.

2 ≤M≤ 1000, 2 ≤N≤ 1000,C≤ 1000000입니다.

입력의 30% 는C≤ 100 입니다.

목재 총량을 계산해야 하는 직사각형 토지 개수 C가 매우 큰 수 입니다.

출력의 C개 줄에는 각각 직사각형 토지의 목재 총량의 정수를 출력합니다.

즉 출력의 i번째 줄에는 입력의 M+2+i번째 줄에서 설명한 직사각형 토지의 목재 총량을 출력합니다.

4   4
3   4   15  23
14  20  12  9
3   8   12  15
12  20  7   5
2
2   2   3   4
4   2   4   2

76
20

단순한 알고리즘은 시간초과를 극복할 수 없습니다.

동적 계획법(Dynamic Programming) (https://ko.wikipedia.org/wiki/동적계획법)

일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다.
각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

#include <iostream>
#include <vector>

using namespace std;
int M, N;

int main()
{

    cin >> M >> N;
    vector<vector<int>> forest(M, vector<int>(N, 0));
    vector<vector<int>> dp(M, vector<int>(N, 0));

    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> forest[i][j];
            if (j != 0)
            {
                dp[i][j] += dp[i][j - 1] + forest[i][j];
            }
            else{
                dp[i][j] += forest[i][j];
            }
        }
    }
    int C;
    cin >> C;
    vector<int> answer(C, 0);

    for (int i = 0; i < C; i++)
    {
        int sx, sy, dx, dy;
        cin >> sy >> sx >> dy >> dx;

        for (int j = sy - 1; j < dy - 1; j++)
        {
            if (sx - 1 != 0)
            {
                answer[i] += dp[j][dx - 1] - dp[j][dx - 2];
            }
            else
            {
                answer[i] += dp[j][dx];
            }
        }
    }
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer[i] << endl;
    }

    return 0;
}