시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 892 | 188 | 150 | 25.862% |
어떤 수열에서 0개 이상의 원소를 삭제해서 얻을 수 있는 수열을 그 수열의 부분수열이라 한다. 예를 들어, aab
는 $X$ = ababca
의 부분수열이지만, $Y$ = cbabba
의 부분수열은 아니다.
두 개의 수열이 주어졌을 때, 두 수열에 공통으로 나타나는 부분수열을 두 수열의 공통부분수열이라 한다. 예를 들어, 위 두 수열 $X$와 $Y$가 주어졌을 때, baa
는 $X$와 $Y$의 공통부분수열이지만, aab
는 $X$와 $Y$의 공통부분수열이 아니다.
두 수열 $X$와 $Y$의 공통부분수열 $W$가 주어졌을 때, $W$가 확장 가능한지 아닌지 판별하려고 한다. $W$의 한 위치에 어떤 원소를 추가하여 더 긴 공통부분수열을 만들 수 있으면 $W$는 확장 가능하고, 그렇지 않으면 $W$는 확장 불가능하다고 정의한다. 예를 들어, 위의 $X$와 $Y$가 주어졌을 때, 공통부분수열 baa
는 baba
로 확장가능하다. 하지만, 공통부분수열 ca
는 더 이상 확장할 수 없다.
두 수열 $X$, $Y$ 와 두 수열의 공통부분수열 $W$가 주어졌을 때, $W$가 확장 가능한지 불가능한지 판별하는 프로그램을 작성하라.
첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.
다음 $3 \times T$개의 줄에 테스트 케이스의 정보가 주어진다.
각 테스트 케이스는 세 줄로 구성되고, 각 줄에 수열 $X$, $Y$, $W$가 각각 주어진다.
각 수열은 공백 없이 연속된 알파벳 소문자로 주어진다.
각 테스트 케이스에 대해 확장 가능 여부를 한 줄에 하나씩 출력한다.
확장 가능하면 1, 불가능하면 0을 출력한다.
번호 | 배점 | 제한 |
---|---|---|
1 | 14 | $|W| = 1$ |
2 | 17 | $|X|$의 합과 $|Y|$의 합은 각각 $300$ 이하이다. |
3 | 25 | $|X|$의 합과 $|Y|$의 합은 각각 $20~000$ 이하이다. |
4 | 44 | 추가 제약 조건 없음. |
2 ababca cbabba baa aaabbbccc caacbbc ccc
1 0
Olympiad > 한국정보올림피아드 > KOI 2021 1차대회 > 고등부 3번