쿠옹이는 태보를 보고, 이런 생각이 들었다. '태권도와 복싱을 합해서 태보면 양궁과 파워리프팅을 합하면 양파인가? 나도 운동 하나 만들어 볼까?'

운동 A와 B의 이름을 합치면 A의 첫음절과 B의 첫음절을 이어 붙인 이름의 새로운 운동이 만들어진다. 만약 둘 중 하나라도 첫음절이 존재하지 않는다면 새로운 운동의 이름을 만들 수 없다.

문자열의 첫음절이란 문자열의 첫 번째 모음을 포함하고 그다음 나오는 첫 번째 자음을 포함하지 않는 접두사 중 가장 긴 접두사이다. 만약 모음이 없거나 첫 번째 모음 이후 자음이 없다면 첫음절은 존재하지 않는다. 다음은 여러 문자열의 첫음절의 예시이다.

• taekwondo tae
• boxing bo
• tae는 모음이 없어 첫음절이 존재하지 않는다.
• ski는 모음은 있지만 첫 모음 이후 자음이 없어 첫음절이 존재하지 않는다.

모음은 a, e, i, o, u의 5가지 문자를 말하며, 자음은 이 5가지를 제외한 모든 문자를 말한다.

쿠옹이가 새롭게 만들 운동의 이름을 출력해 보자.

쿠옹이는 큐브가 가시를 뛰어넘는 게임을 하고 있다.

이 게임의 모든 맵에서 큐브는 위치 0에서 출발하여 매 프레임 1만큼 이동한다. 큐브가 위치 N에 도달한다면 공중에 떠 있는 상태인지와 관계없이 맵을 클리어하게 된다.

큐브는 프레임마다 공중에 떠 있는 상태가 아니라면 점프할 수 있다. 큐브가 점프하면 점프한 다음 프레임부터 3프레임 동안 공중에 떠 있는 상태가 된다. 예를 들어 1프레임에 점프를 하면 2프레임부터 4프레임까지는 공중에 떠 있는 상태이다가 5프레임에 공중에 떠 있는 상태가 아니게 된다.

만약 큐브가 공중에 떠 있는 상태가 아닐 때 어떤 가시와 위치가 일치하면 큐브는 가시에 부딪혀 죽고 클리어에 실패하게 된다.

쿠옹이는 어떤 맵은 클리어가 불가능하다고 생각했다. 쿠옹이를 위해 맵의 클리어 가능성을 판별해 주자.

쿠옹이는 편식을 많이 한다. 친구들은 쿠옹이의 편식을 막기 위해 쿠옹이가 좋아하는 음식인 피자 위에 다양한 재료를 올리려고 한다. 이 피자는 첫 번째 조각과 마지막 조각이 연속되어 있는 원 모양이다.

쿠옹이의 피자의 선호도는 연속된 피자 조각의 피자 조각의 선호도의 합의 최댓값이다. 또한 피자 조각의 선호도는 그 피자 조각 위에 올라가 있는 재료의 재료의 선호도의 합과 같다. 아무 재료도 올라가 있지 않은 피자 조각의 선호도는 0이다.

아무 피자 조각도 선택하지 않고 피자의 선호도라고 하는 것은 이상하므로 피자의 선호도는 하나 이상의 피자 조각을 고르는 경우만을 포함한다.

최초에 피자 위에는 아무 재료도 올라가 있지 않다. 쿠옹이의 친구들은 총 Q번에 걸쳐 다음 두 행동 중 하나를 한다.

• 1 a b: a(1 ≤ a ≤ S)번 조각 위에 재료의 선호도가 b( - 10⁹ ≤ b ≤ 10⁹)인 재료를 올린다.
• 2: 쿠옹이에게 현재 쿠옹이의 피자의 선호도가 몇인지 질문한다.

쿠옹이는 어느 날 갑자기 이런 궁금증이 들었다. '연산 결과가 N이 되는 수식은 몇 개가 있을까?'

쿠옹이는 연산 결과가 N이 되는 수식의 뒤에 +0, -0 등을 이어 붙이면 여전히 연산 결과가 N이므로 이 시행을 반복하면 연산 결과가 N인 수식을 무한히 만들 수 있다는 슬픈 사실을 깨닫고 말았다.

그래서 쿠옹이는 수식의 길이가 M이어야 한다는 제약을 추가했지만 이번에는 답을 내지 못했다. 여러분이 대신 이 문제를 풀어 주자!

수식은 다음과 같이 정의된다.

• 항은 0, 1, 2, 3, 4, 5, 6, 7, 8, 9만으로 구성되어 있으며 0으로 시작하지 않는 길이 1 이상의 문자열이다. 단 0은 0으로 시작하지만 예외적으로 항이다.
• 수식은 1개 이상의 항을 포함하며 각 항이 + 또는 -로 구분되어 있는 문자열이다.

다르게 설명하면 수식은 다음 정규식을 만족하는 문자열을 말한다.

• (([1-9][0-9]*|'0')[+-]))*([1-9][0-9]*|'0')

이 문제는 간단한 동전 문제 (Hard)와 N과 M의 제한을 제외하면 동일한 문제입니다.

쿠옹이는 경희 왕국에 살고 있다. 경희 왕국에서는 P₁원, P₂원, ..., P_N원의 N종류의 동전을 사용한다.

신기하게도 경희 왕국에는 0 또는 음수의 가치를 가지는 동전이 있을 수 있다.

쿠옹이는 물건을 사기 위해 정확히 M원을 지불하려 한다. 물론 M이 0 또는 음수인 경우에도 정확히 M원을 지불해야 한다. 쿠옹이는 각 동전을 무한히 많이 가지고 있어서 정확히 M원을 지불하는 방법이 있다면 항상 지불할 수 있다.

예를 들어 50원 동전과  - 3원 동전으로 94원을 지불해야 한다면 지불해야 하는 동전의 최소 개수는 50원 2개,  - 3원 2개로 총 4개이다. 이보다 적은 개수의 동전으로 정확히 94원을 지불할 수는 없다.

이 문제는 간단한 동전 문제 (Easy)와 N과 M의 제한을 제외하면 동일한 문제입니다.

쿠옹이는 경희 왕국에 살고 있다. 경희 왕국에서는 P₁원, P₂원, ..., P_N원의 N종류의 동전을 사용한다.

신기하게도 경희 왕국에는 0 또는 음수의 가치를 가지는 동전이 있을 수 있다.

쿠옹이는 물건을 사기 위해 정확히 M원을 지불하려 한다. 물론 M이 0 또는 음수인 경우에도 정확히 M원을 지불해야 한다. 쿠옹이는 각 동전을 무한히 많이 가지고 있어서 정확히 M원을 지불하는 방법이 있다면 항상 지불할 수 있다.

예를 들어 50원 동전과  - 3원 동전으로 94원을 지불해야 한다면 지불해야 하는 동전의 최소 개수는 50원 2개,  - 3원 2개로 총 4개이다. 이보다 적은 개수의 동전으로 정확히 94원을 지불할 수는 없다.

1부터 N까지 N개의 정점으로 이루어진 무방향 트리가 있다.

트리에는 특별한 정점이 있다. 트리에 간선을 추가해서 모든 특별한 정점을 한 번씩 방문하는 경로를 만들려고 한다. 이때 같은 정점을 두 번 방문해서는 안된다. 특별한 정점이 아닌 일반 정점은 경로상에 포함될 수 있지만, 모든 일반 정점을 방문할 필요는 없다.

모든 특별한 정점을 한 번씩 방문하는 경로를 만들기 위해 필요한 간선의 최소 개수를 구해보자.

길이가 N인 수열 A = {a₁, a₂, a₃, ..., a_N}는 초항이 a이고 공차가 d인 유한 등차수열이다.

양의 정수 M에 대하여 합이 M인 A의 부분 수열 중 가장 긴 것을 구하시오.

부분 수열이란 주어진 수열에서 원래 순서를 유지하며 0개 이상의 원소를 제거하여 얻은 수열이다.

jwpassion1은 사용하지 않는 오래된 교통카드 여러장을 찾아 현금으로 환불받기로 하였다. jwpassion1은 500원 동전이 필요한 리듬게임을 할 때 외에는 현금을 사용할 일이 없다. 그러나 하필 환불을 받을 금액이 500으로 나눈 나머지가 정확히 490이 되는 바람에 아무데도 쓸모 없는 동전 9개가 생겨 곤란하게 되었다. 따라서 앞으로는 불필요한 동전이 생기지 않게 주의하려고 한다.

구체적으로 아래와 같은 규칙으로 교통카드를 환불받아야 한다.

• 잔액이 20 000원 이상인 교통카드는 환불이 불가능하다.
• 환불 수수료는 500원이다. 즉, i번째 교통카드의 환불 금액은 정확히 A_i - 500원이 된다. 만약 A_i ≤ 500인 교통카드는 환불을 받는 것이 손해이기에 환불이 불가능하다.
• 환불받은 금액의 합은 500으로 나누어떨어져야 한다.

jwpassion1이 가지고 있는 교통카드의 개수와 각 교통카드의 잔액이 주어질 때 환불받을 수 있는 최대 금액을 구해라.

경희대학교 알고리즘 동아리 KHUA에서는 축하할 일이나 기념할 일이 있을 떄 선물로 수열을 주고받는 PS계의 문화를 본받아 신입 부원들에게 선물로 수열을 나누어 주려고 한다. 하지만 매번 새로운 수열을 만들어 내는 것은 귀찮기 때문에 수열 하나를 만들어 두고 그것을 재활용해서 새로운 수열을 만들어 내기로 했다.

재활용할 무한한 길이의 주기 수열 A₁, A₂, ...를 만든다. A의 첫 N개 원소는 A₁, A₂, ..., A_N로 주어지며, i > N일 때 A_i = A_i - N이다. 이 수열의 각 원소는 0 이상 M - 1 이하의 정수이다. 1 이상 N 이하인 정수 i와 0 이상 M - 1 이하의 정수 j에 대해 다음과 같이 정의되는 길이 T (T ≤ N)인 수열 B^i, j₁, B^i, j₂, ..., B^i, j_T을 선물로 나누어 주면 좋겠다고 생각했다.

하지만 이렇게 만들어진 수열이 중복되면 사람들이 수열을 재활용하고 있다는 걸 알아챌 수 있으므로 이런 상황은 최대한 피하려고 한다.

재활용해 만들어낸 임의의 두 수열이 같을 확률을 구해 얼마나 수열을 재활용할 수 있을 지 예측하려고 한다. 1 ≤ i₁, i₂ ≤ N이고 0 ≤ j₁, j₂ ≤ M - 1인 정수 i₁, i₂, j₁, j₂를 균일한 확률로 무작위로 뽑았을 때 B^i₁, j₁과 B^i₂, j₂가 서로 같을 확률을 구해야 한다. 각 수는 독립적으로 선택되므로 (i₁, j₁) = (i₂, j₂)인 경우도 발생할 수 있다. 이 경우를 포함하여 확률을 구해야 한다.

mex(S)는 집합 S에 포함되지 않는 가장 작은 음이 아닌 정수이다.

문자열 X의 부분 문자열이란 길이가 0 이상인 X의 연속된 일부분을 말한다.

'M', 'E', 'X'가 순서대로 번갈아 등장하는 길이 0 이상의 문자열을 MEX 문자열 이라고 하자. 예를 들어 "", "M", "MEX", "MEXME"는 MEX 문자열이지만 "MMEX", "EXM", "EX" 등은 MEX 문자열이 아니다.

문자열로만 이루어진 집합 S의 점수를 mex(|k|: k ∈ S)이라고 하자.

MEX 문자열 M의 길이 N이 주어질 때 M의 MEX 문자열인 부분 문자열을 겹치지 않고 선택해 만들 수 있는 집합의 최대 점수를 출력하라. M 부분문자열이 겹치지 않는다는 것은 M의 모든 문자는 많아야 하나의 부분문자열에만 포함된다는 것이다.

이 문제는 부도덕한 그래프 (Hard)와 N과 M의 제한을 제외하면 동일한 문제입니다.

그래프 세계에선 서로 말 한마디 섞어본 적 없는 두 정점이 같은 자식을 갖기도 한다.

사이클 없는 단순 방향 그래프의 서로 다른 정점 x, y, z가 다음 조건을 모두 만족하면 이를 부도덕한 관계라고 한다.

• x에서 z로 가는 간선과 y에서 z로 가는 간선이 모두 존재한다.
• x와 y를 잇는 간선이 없다.

그래프 세계에선 이런 관계가 꽤 흥미로운 구조로 취급된다.

N개의 정점과 M개의 간선으로 이루어진 사이클 없는 단순 방향 그래프가 주어진다. 부도덕한 관계의 개수를 구해 보자.

이 문제는 부도덕한 그래프 (Easy)와 N과 M의 제한을 제외하면 동일한 문제입니다.

그래프 세계에선 서로 말 한마디 섞어본 적 없는 두 정점이 같은 자식을 갖기도 한다.

사이클 없는 단순 방향 그래프의 서로 다른 정점 x, y, z가 다음 조건을 모두 만족하면 이를 부도덕한 관계라고 한다.

• x에서 z로 가는 간선과 y에서 z로 가는 간선이 모두 존재한다.
• x와 y를 잇는 간선이 없다.

그래프 세계에선 이런 관계가 꽤 흥미로운 구조로 취급된다.

N개의 정점과 M개의 간선으로 이루어진 사이클 없는 단순 방향 그래프가 주어진다. 부도덕한 관계의 개수를 구해 보자.