Informatica Online Judge

  사다리 제작 [2223 / 08AF]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 12   Total Tried : 15


The Champion of this Problem (C++) : gs16036 - 0ms / 634byte
My Best Submission (C++) : N/A

[35th 황선우]
Writer ID : [gs17126]

Background

사다리를 제작하는 일을 하고 있는 세빈이는 어느 날 한 사람에게서 의뢰를 받았다.
그 의뢰의 내용은 바로 다음 조건을 만족하는 사다리를 제작해 달라는 것이다.



1부터 n까지의 수들이 임의로 배열된 수열 A와 1부터 n까지의 수들이 의뢰인이 원하는 순서로 배열된 수열 B가 주어진다.

이때 시작을 수열 A로 하고 이 사다리를 타게 되면 결과가 수열 B가 되게 된다.
세빈이는 위 조건을 만족하는 사다리를 제작할 때 주어진 n개의 가로막대에서 몇 개의 세로 막대를 추가해야 하는지 알고 싶어한다.

여러분은 세빈이를 도와 주어진 범위에서 몇 개의 세로 막대를 이용하면 이 사다리를 만들 수 있는지 구하는 소스 코드를 작성하시오.

Input

첫 번째 줄에는 수열의 길이를 의미하는 자연수인 n(1<=n<=5000)과
세빈이가 사용할 수 있는 세로 막대의 수 k의 범위(a<=k<=b)인 a, b가 주어진다.
(0<=a<=b<=30000000)

두 번째 줄에는 초기 수열 A가 주어진다.

세 번째 줄에는 의뢰인이 사다리 타기를 통해 만들고 싶어 하는 수열 B가 주어진다. (단, 숫자 카드의 수는 int 범위를 넘어가지 않는다)

Output

첫 번째 줄에는 가능한 세로막대 수의 경우의 수를 출력한다.
두 번째 줄부터는 가능한 세로막대의 수를 크기 순서대로 출력한다.

IO Example

예제 1

입력
5 6 7
3 5 2 4 1
5 4 1 2 3

출력
1
6

예제 2

입력
4 1 3
4 1 2 3
2 4 1 3

출력
1
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]