IOI 2011 day1 1- 열대 식물원(Tropical Garden) > 문제은행 : 정보올림피아드&알고리즘




2675 : 열대 식물원(Tropical Garden)

제한시간
5000 ms   
메모리제한
256 MB   
해결횟수
3 회   
시도횟수
5 회   

문제

식물학자 철수는 여러 반의 학생들과 함께 태국 최대의 식물원을 방문하기로 하였다.

이 넓은 식물원은 N(0 ~ N-1)개의 연못과 M개의 산책로로 구성되어 있다.

각 산책로는 서로 다른 두 연못을 연결하며, 양방향으로 모두 이동하는 것이 가능하다.

어느 연못이든지 최소 하나의 산책로가 연결되어 있다. 이 산책로들에는 철수가 좋아하는 아름다운 식물들이 많이 있다.

같은 반의 학생들은 함께 이동하며, 각 반이 산책을 시작하는 연못은 서로 다를 수 있다.

 

철수는 아름다운 열대 식물들을 아주 좋아한다.

따라서, 철수와 각 반의 학생들은 어느 연못에서든 가장 아름다운 산책로를 선택하여 이용한다.

단, 그 산책로를 바로 직전에 이용한 경우에는 두 번째로 아름다운 산책로를 이용한다.

하지만, 현재 연못에 연결된 산책로가 단 하나뿐인 경우는 두 번째로 아름다운 산책로가 존재하지 않으므로 방금 사용한 산책로를 다시 이용하는 것을 허용한다. 철수는 식물학자이므로 두 산책로의 아름다운 정도가 같은 경우는 없다.

 

학생들은 식물에는 큰 관심이 없다.

학생들의 관심은 어떤 연못 P옆에 위치한 고급 식당에서 점심 식사를 하는 것이다.

철수는 각 반의 학생들이 정확히 K개의 산책로를 지난 다음 배가 고파질 것이라는 것을 알고 있다. 각 반 마다 K의 값은 다를 수 있다.

이 상황 하에서 철수는 각 반에 대해 정확히 K개의 산책로를 이용한 후 연못 P에 도착하는 방법의 수가 얼마나 많은지 알고 싶다.

각 반에 대한 상황을 정리하면 다음과 같다

 

● 각 반은 아무 연못에서나 출발할 수 있다.
● 산책로를 선택하는 규칙은 위의 설명과 같다.
● 각 반은 정확히 K개의 산책로를 이용한 다음에는 연못 P에 도착해야 한다.
● 산책로의 번호가 작을수록 더 아름답다는 것에 주의하자.
    즉, 산책로 0 이 가장 아름다운 것이고, 산책로 1 이 그 다음으로 아름다운 것임을 알 수 있다.

 

각 반이 P로 가는 도중에 연못 P를 지나는 것도 가능하다. 그러나, 마지막에는 반드시 P에 도달하여야 한다.

 

 

해야 할 일

철수와 반 i의 학생들이 정확히 G[i]개의 산책로를 이용한 후 연못 P 에 도달할 수 있는 모든 가능한 서로 다른 경로들의 개수를 찾아야 한다.

 

 

 

 

예제 설명 

  

산책로의 번호가 작을 수록 더 아름답다는 것에 주의하자. 

 

즉, 산책로 0 이 가장 아름다운 것이고, 산책로 1 이 그 다음으로 아름다운 것임을 알수 있다. 

산책로의 개수가 3 이고 연못 0 에서 끝나면서 이동 규칙을 맊족하는 경로는 다음의 두가지 경우 밖에 없다. 

 

●​ 1 → 2 → 1 → 0 

●​ 5 → 4 → 3 → 0 

 

첫번째 경로는 연못 1 에서 시작한다. 

그 곳에서 가장 아름다운 산책로를 택하면 연못 2 로 가게 된다. 

연못 2 에서는 연못 1 로 가는 방법 밖에는 없다. 

이제 연못 1 에서는 방금 사용한 산책로를 제외하면 연못 0 으로 가는 산책로를 택하게 되어 목적지에 도착할 수 있다. 

 

따라서 2를 출력한다.

 

 

 

첫번째 반에 대해서 3 개의 산책로를 이용하여 연못 2 에 도착하는 방법은 하나 밖에 없으며 다음과 같다: 

1 → 0 → 1 → 2. 

 

두번째 반에 대해서 1 개의 산책로를 이용하여 연못 2 에 도착하는 방법은 다음의 두가지가 있다: 

3 → 2 와 4 → 2. 

 

따라서, 정확한 프로그램은 첫 번째 반에 대해 answer(1)을 호출하고 

두 번째 반에 대해 answer(2)를 호출해야 하며 정확한 호출 순서를 지켜야 핚다.
 

 


입력형식

입력의 첫줄에 N, M, P가 들어온다. 다음 줄부터 M개의 줄에 산책로들을 표현한 2차원배열 R[i][0], R[i][1]이 들어온다. 그 다음 줄에 반의 수 Q가 들어오고 다음 줄에 각 반에 대한 K의 값을 가지는 G가 들어온다. ● N - 연못의 수. 연못은 0 부터 N-1 까지 번호가 붙어 있다. ● M - 산책로의 수. 산책로는 0 부터 M-1 까지 번호가 붙어 있다. 산책로의 번호는 아름다운 정도가 줄어드는 순서이다. 즉, 모든 i(0 ≤ i < M-1)에 대해서 산책로 i는 산책로 i+1보다 더 아름답다. ● P - 고급 식당이 위치하는 연못의 번호 ● R - 산책로들을 표현한 2차원 배열. 산책로 i(0 ≤ i < M-1)는 연못 R[i][0]과 연못 R[i][1]을 연결한다. 한 산책로는 서로 다른 두개의 연못을 연결하며, 두 연못 사이에는 최대 하나의 산책로만 존재한다는 것에 주의하라. ● Q - 반의 수 ● G - 각 반에 대한 K 의 값을 가지는 배열. 각 i(0 ≤ i < Q)에 대해서 G[i]의 값은 반 i 가 목적지 P 에 도달하기 위해 이용하는 산책로의 개수인 K 의 값이다. * 2 ≤ N ≤ 150 000 * 1 ≤ M ≤ 150 000 * 1 ≤ Q ≤ 2 000 * G 의 각 원소는 1 이상, 1,000,000,000 이하인 정수이다.

출력형식

출력의 첫 줄에 철수와 반 i의 학생들이 정확히 G[i]개의 산책로를 이용한 후 연못 P 에 도달할 수 있는 모든 가능한 서로 다른 경로들의 개수를 출력한다.


입력 예

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

출력 예

2

입력 예

5 5 2
1 0
1 2
3 2
1 3
4 2
1
1

출력 예

2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP