한자 끝말잇기 Batch 컴파일 명령

Anna와 Bruno는 학교에서 한자 수행평가(..)을 쳐야 합니다. Anna와 Bruno는 $0$ 이상 $N-1$ 이하의 번호가 붙은 $N$개의 한자와 $0$ 이상 $M-1$ 이하의 번호가 붙은 $M$개의 단어를 알고 있습니다. 단어는 두 사람이 알고 있는 한자로 구성되며, $i$번째 단어의 첫 번째 문자는 $A_{i}$번 한자이고 마지막 문자는 $B_{i}$번 한자입니다. 모든 단어에 대해 $A_{i} \neq B_{i}$입니다. 또한 모든 낱말에 대해 $(A_{i}, B_{i})$는 서로 다릅니다. 다시 말해, $i \neq j$라면 $(A_{i}, B_{i}) \neq (A_{j}, B_{j})$입니다. 또한 각 단어를 쓰는 데 걸리는 시간 $C_{i}$가 정해져 있습니다.

시험은 다음과 같은 문제가 $Q$개 출제됩니다.

모든 문제에 대해 $S_{j} \neq T_{j}$입니다. 또한 모든 문제의 $(S_{j}, T_{j})$는 다릅니다. 다시 말해, $i \neq j$라면 $(S_{i}, T_{i}) \neq (S_{j}, T_{j})$입니다.

한자 끝말잇기는 [그림 1]과 같이 단어의 마지막 문자와 그 다음 단어의 첫 번째 문자가 동일한 단어의 나열입니다. $S_{j}$번 한자에서 시작하여 $T_{j}$번 한자로 끝나는 한자 끝말잇기는 첫 번째 단어의 첫 번째 글자가 $S_{j}$번 한자이고 마지막 단어의 마지막 글자가 $T_{j}$번 한자인 한자 끝말잇기입니다.

[그림 1] 한자 $S_{j}$ = 報로부터 시작하여 $T_{j}$ = 情으로 끝나는 한자 끝말잇기의 예시입니다.

답이 될 수 있는 끝말잇기는 몇 가지 있겠지만, 시험 시간이 짧기 때문에 그 중에서 쓰는 데 걸리는 시간이 가장 짧은 것을 답해야 합니다. (시간이 같은 경우가 두 가지 이상 있다면 아무거나 답할 수 있습니다) 한자 끝말잇기를 작성하는 시간은 그 끝말잇기에 포함된 각 단어를 적는 데 걸리는 시간의 합입니다.

시험 직전이 되었고, Bruno는 $U_{0}, U_{1}, \cdots, U_{K-1}$번 단어를 쓰는 데 걸리는 시간 $C_{U_{0}}, C_{U_{1}}, \cdots, C_{U_{K-1}}$를 잊어버렸습니다. 이 $K$개의 단어는 공교롭게도 첫 번째 글자가 서로 같습니다. Anna는 Bruno에게부터 이러한 사실을 들었지만, 시험 시작까지 시간이 없었기 때문에, 시험 도중에 정보를 전달하기로 결정했습니다. Anna는 시험 중에 책상을 두드림으로써 Bruno에게 0 또는 1을 전달할 수 있습니다. 여러분은 Anna가 0 또는 1을 전달하는 횟수를 최소화하고자 합니다.

과연 Bruno는 수행평가에서 만점을 받을 수 있을까요?

문제

한자의 수 $N$과 단어의 수 $M$과 각 단어의 첫 번째 문자와 마지막 문자와 문제의 개수 $Q$와 문제들에 대한 정보, Bruno가 잊어버린 단어의 개수 $K$와 그 단어의 번호가 Anna와 Bruno에게 각각 주어집니다. 또한 Anna에게는 $M$개의 모든 단어들에 대해 각 단어를 쓰는 데 걸리는 시간이 주어지고, Bruno에게는 쓰는 데 걸리는 시간을 잊어버린 $K$개의 단어를 제외한 $M-K$개의 단어들에 대해 각 단어를 쓰는 데 걸리는 시간이 주어집니다. Anna가 Bruno에게 정보를 보내고, Bruno가 이 정보를 가지고 시험에서 만점을 받을 수 있도록 하는 프로그램을 작성하세요.

구현 세부 사항

여러분은 동일한 프로그래밍 언어로 두 개의 파일을 제출해야 합니다.

첫 번째 파일은 Anna.c 또는 Anna.cpp입니다. 이 파일은 Anna의 전략을 구현한 파일이며 다음 함수를 구현해야 합니다.

void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]);

이 함수는 처음 한 번만 호출됩니다.

• N은 한자의 개수입니다.
• M은 단어의 개수입니다.
• A는 길이가 M인 배열이며, 원소 A[i]는 i번 단어의 첫 번째 문자의 번호 $A_{i}$입니다.
• B는 길이가 M인 배열이며, 원소 B[i]는 i번 단어의 마지막 문자의 번호 $B_{i}$입니다.
• C는 길이가 M인 배열이며, 원소 C[i]는 i번 단어를 쓰는 데 걸리는 시간입니다.
• Q는 문제의 수입니다.
• S는 길이가 Q인 배열이며, 원소 S[j]는 $j$번 문제에 해당하는 답의 첫 번째 문자의 번호 $S_{j}$입니다.
• T는 길이가 Q인 배열이며, 원소 T[j]는 $j$번 문제에 해당하는 답의 마지막 문자의 번호 $T_{j}$입니다.
• K는 Bruno가 쓰는 데 걸리는 시간을 잊어버린 단어의 수입니다.
• U는 길이가 K인 배열이며, 원소 U[0], U[1], ..., U[K-1]은 Bruno가 소요 시간을 잊어버린 단어의 번호 $U_0, U_1, \cdots, U_{K-1}$입니다.

또한 프로그램에서 다음 함수를 호출하여 Bruno에게 0 또는 1을 보낼 수 있습니다.

void Tap (int x);

x는 Bruno에게 전달될 신호이며 0 또는 1입니다.

• x는 반드시 0 또는 1이어야 합니다. 만약 만족하지 못하면, 오답 [1]이 판정됩니다.
• Tap 함수를 호출한 횟수가 1000번을 초과하면, 오답 [2]이 판정됩니다.

Tap을 호출하는 과정에서 오답 판정이 난 경우, 그 시점에서 프로그램의 실행이 즉시 종료됩니다.

두 번째 파일은 Bruno.c 또는 Bruno.cpp입니다. 이 파일은 Bruno의 전략을 구현한 파일이며 다음 함수를 구현해야 합니다.

void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]);

이 함수는 Anna가 호출된 후 단 한 번 호출됩니다.

• N, M, A, B, Q, S, T, K, U는 Anna의 것과 같습니다.
• C는 길이가 N인 배열이며, 원소 C[i]는 i번 단어를 쓰기 위해 걸리는 시간 $C_{i}$입니다. 단 i가 $U_{0}, U_{1}, \cdots, U_{K-1}$ 중 하나일 경우 $-1$입니다.
• L은 Anna로부터 보내져 온 0 또는 1의 개수입니다.
• X는 길이가 L인 배열이며, Anna가 0 또는 1로 구성된 수열 X[0], X[1], ..., X[L-1]을 차례대로 보내온 것을 의미합니다.\

프로그램에서 다음 함수를 호출할 수 있습니다.

void Answer (int w);

• 인수 w는 0 이상 M-1 이하의 정수 또는 -1이어야 합니다. 이를 만족하지 못할 경우 오답 [3]이 판정됩니다.
• 인수 w가 -1인 호출을 Q회 수행한 후 Answer 함수가 호출된 경우 오답 [4]이 판정됩니다.

Answer 호출 과정에서 오답 판정이 난 경우, 그 시점에서 프로그램이 즉시 종료됩니다. 프로그램은 Answer 함수를 사용하여 답을 적는 과정을 Q회 반복해야 합니다.

$j+1$번째 ($0 \le j \le Q-1$) 과정에서는 다음을 수행합니다.

1. 문제 $j$의 답이 되는 단어들에 대해 차례대로(첫 단어에서부터 마지막 단어까지 순서대로) Answer(w)를 호출합니다. 이 때 w는 해당 단어의 번호입니다.
2. Answer(-1)을 호출합니다.

Bruno가 호출된 후, 판정이 이루어집니다.

• 인수 w가 -1인 호출 횟수가 $Q$ 미만인 경우 오답 [5]이 판정됩니다.
• 문제의 답의 길이 (단어의 수)가 0인 경우, 오답 [6]이 판정됩니다.
• 문제의 답에서 어떤 단어의 마지막 문자와 그 다음 단어의 첫 번째 문자가 다를 경우 오답 [7]이 판정됩니다.
• $j$번 문제의 답에서 첫 번째 단어의 첫 글자가 $S_{j}$가 아니거나, 마지막 단어의 마지막 문자가 $T_{j}$가 아니면 오답 [8]이 판정됩니다.
• 문제의 답을 적는 데 걸리는 시간이 가장 짧지 않으면 오답 [9]이 판정됩니다.

내부에서 사용하기 위해 다른 함수를 구현하거나 전역 변수를 선언하는 것은 자유입니다. 그러나 제출된 두 프로그램은 채점 프로그램과 함께 연결되어 하나의 실행 파일이 되므로, 각 파일의 모든 전역 변수와 내부 함수들을 static으로 선언하여 다른 파일과의 충돌을 막을 필요가 있습니다. 채점 시, Anna 측과 Bruno 측은 서로 다른 두 개의 프로세스로 실행되므로, 이 두 프로그램이 전역 변수를 공유한다거나 할 수 없습니다. 여러분의 프로그램이 표준 입출력을 이용하거나 다른 파일과 어떤 방식으로도 상호 작용하는 것은 금지되어 있습니다.

컴파일 및 실행 방법

프로그램을 시험해 보기 위한 예시 채점 프로그램을 여기에서 내려받을 수 있습니다. 이 파일에는 제출해야 할 파일의 예시도 들어 있습니다.

예시 채점 프로그램은 한 개의 파일로 구성됩니다. 그 파일은 grader.c 또는 grader.cpp입니다. 만든 프로그램을 시험하려면 다음과 같이 명령을 실행해야 합니다. (리눅스 한정)

• C의 경우: gcc -O2 -lm grader.c Anna.c Bruno.c -o grader
• C++의 경우: g++ -O2 -lm grader.cpp Anna.cpp Bruno.cpp -o grader

컴파일에 성공하면 grader라는 실행 파일이 만들어집니다.

실제 채점 프로그램은 예시 채점 프로그램과 다르다는 것에 유의해야 합니다. 예시 채점 프로그램은 단일한 프로세스로 구성되어 있으며, 표준 입력에서 입력을 받고 표준 출력에 결과를 출력합니다.

채점 프로그램의 입력 예시

예시 채점 프로그램은 표준 입력에서 다음 입력을 받습니다.

• 첫 번째 줄에는 정수 $N$, $M$, $Q$, $K$가 공백을 사이로 두고 주어집니다. 한자의 개수가 $N$, 단어의 수가 $M$, 문제의 수가 $M$, Bruno가 쓰는 데 걸리는 시간을 잊어버린 단어의 수가 $K$임을 나타냅니다.
• 그 다음에 $M$개 줄이 주어지는데, 이 중에서 $i+1$번째 줄 ($0 \le i < M$)에는 세 개의 정수 $A_{i}, B_{i}, C_{i}$가 공백을 사이로 두고 주어지는데, 이것은 $i$번 단어의 첫 번째 문자가 $A_{i}$번 한자이고 마지막 문자가 $B_{i}$번 한자이며 쓰는 데 걸리는 시간이 $C_{i}$임을 의미합니다.
• 그 다음에 $Q$개 줄이 주어지는데, 이 중에서 $j+1$번째 줄 ($0 \le j < Q$)에는 세 개의 정수 $S_{j}, T_{j}, Z_{j}$가 주어집니다. 이것은 $j$번 문제의 답의 첫 번째 문자가 $S_{j}$여야 하고, 마지막 문자가 $T_{j}$여야 하며, 답을 적는 데 걸리는 최소 시간이 $Z_{j}$임을 나타냅니다.
• 그 다음에 $K$개 줄이 주어지는데, 이 중 $k+1$번째 줄 ($0 \le k \le K$)에는 정수 $U_{k}$가 주어집니다. 이는 Bruno가 쓰는 데 걸리는 시간을 잊어버린 단어들이 $U_{0}, U_{1}, \cdots, U_{K-1}$임을 나타냅니다.

채점 프로그램의 출력 예시

프로그램의 실행이 정상적으로 종료된 경우, 예시 채점 프로그램은 표준 출력에 다음 정보를 첫 번째 줄에 출력합니다. (단 따옴표는 출력되지 않습니다.)

• 정답의 경우 Tap이 호출된 횟수를 "Accepted : L = 100"과 같이 출력합니다.
• 오답의 경우 오답의 종류가 "Wrong Answer[1]"과 같이 출력합니다.

제약 조건

모든 입력 데이터는 다음을 만족합니다.

• $2 \le N \le 300$
• $1 \le M \le N \times (N-1)$
• $0 \le A_{i} < N$ ($0 \le i < M$)
• $0 \le B_{i} < N$ ($0 \le i < M$)
• $A_{i} \neq B_{i}$ ($0 \le i < M$)
• $(A_{i}, B_{i}) \neq (A_{j}, B_{j})$ ($0 \le i < j < M$)

• $1 \le C_{i} \le 10^{16}$ ($< 2^{54}$) ($0 \le i < M$)

• $1 \le Q \le 60$

• $0 \le S_{j} < N$ ($0 \le j < Q$)
• $0 \le T_{j} < N$ ($0 \le j < Q$)
• $S_{j} \neq T_{j}$ ($0 \le j < Q$)
• $(S_{i}, T_{i}) \neq (S_{j}, T_{j})$ ($0 \le i < j < Q$)

• $S_{j}$에서 시작해서 $T_{j}$로 끝나는 한자 끝말잇기는 반드시 존재합니다. ($0 \le j < Q$)

• $1 \le K \le 5$

• $0 \le U_{k} < M$ ($0 \le k < K$)
• $U_{i} \neq U_{j}$ ($0 \le i < j < K$)
• Bruno가 잊어버린 단어의 첫 번째 글자는 모두 같습니다. 즉, $A_{U_{0}} = A_{U_{1}} = \cdots = A_{U_{K-1}}$

서브태스크

서브태스크 1 [10점]

• $Q \le 10$
• 각 문제에 대해 10개 이하의 단어를 사용하는 답이 항상 존재합니다.
• Anna는 Tap을 최대 1000번 호출할 수 있습니다.

서브태스크 2 [22점]

• Anna는 Tap을 최대 180번 호출할 수 있습니다.

서브태스크 3 [8점]

• Anna는 Tap을 최대 160번 호출할 수 있습니다.

서브태스크 4 [40점]

• Anna는 Tap을 최대 90번 호출할 수 있습니다.

서브태스크 5 [20점]

• 이 서브태스크에서 Tap을 호출한 횟수의 최댓값을 $L$이라고 둡시다. 이 서브태스크에서 획득할 점수는 아래와 같습니다.
  • $L \le 64$이면 20점
  • $64 < L < 90$이면, $\lfloor (\frac{90 - L}{90 - 64})^2 \times 20 \rfloor$점 ($\lfloor x \rfloor$는 $x$ 이하의 가장 큰 정수입니다.)
  • $L \ge 90$이면 0점

예시

아래 표는 예시 채점 프로그램이 읽어들이는 입력의 예와 해당 함수를 호출하는 예입니다.

이 예에서 Tap의 호출이 반드시 의미가 있는 호출은 아니라는 점에 유의하세요. 이 때, Anna(...)와 Bruno(...)에 전달되는 인수는 다음과 같습니다.

C[1]과 C[3]에 유의하세요.