하수 처리장

하천 오염 관리는 깨끗한 물 공급을 지키기 위해 당국이 마주하는 큰 과제이다. 하수 처리장은 도시에서 나온 더러운 물을 강으로 흘려보내기 전에 깨끗하게 정화한다.

계획에 따라, 강을 따라 배치된 하수 처리장과 각 도시를 잇는 배관이 설치되어 있다. 일부 처리장은 최대 용량으로 가동하고 덜 쓰이는 처리장은 한동안 꺼 두는 편이 더 효율적이다. 그래서 각 도시는 강가에 자기 처리장을 하나씩 두고, 상류 쪽 이웃 도시로 가는 배관과 하류 쪽 이웃 도시로 가는 배관을 하나씩 갖는다. 각 도시의 처리장은 다음 세 가지 중 하나를 택한다.

이웃 도시 한 곳에서 받은 물을 자기 도시의 더러운 물과 함께 정화하여 강으로 내보낸다;
자기 도시의 더러운 물과 하류 이웃에서 온 물을 상류 이웃 도시의 처리장으로 보낸다(그 상류 이웃이 같은 배관으로 자기 물을 하류로 보내고 있지 않을 때만 가능);
배관이 쓰이지 않고 있다면, 자기 도시의 더러운 물과 상류 이웃에서 온 물을 하류 이웃 도시의 처리장으로 보낸다.

강가의 처리장과 이들을 잇는 배관

이 규칙에 따라 다음이 보장된다.

모든 도시의 물은 어딘가에서 반드시 처리되고,
적어도 한 도시는 정화한 물을 강으로 내보낸다.

강으로 물을 내보내는 도시를 V(아래로 흐름), 물을 오른쪽 이웃에게 넘기는 도시를 >, 왼쪽 이웃에게 넘기는 도시를 <로 나타내자. 강가에 여러 도시가 있을 때, 각 도시에 기호를 하나씩 배정하고 순서대로 나열한다. 예를 들어 두 도시 A와 B는 다음과 같이 할 수 있다.

각자 자기 하수를 처리하여 둘 다 깨끗한 물을 강으로 내보낸다. A도 V, B도 V이므로 VV로 적는다;
또는 A가 오른쪽 B에게 하수를 보내 B가 처리·배출한다. >V로 적는다;
또는 B가 왼쪽 A에게 하수를 보내고 A가 자기 물과 함께 처리하여 내보낸다. A는 V, B는 <이므로 V<로 적는다.

><는 불가능하다. A가 B에게 물을 보내고 B가 A에게 물을 보내는 셈이라 둘이 같은 배관을 함께 쓰게 되기 때문이다. 마찬가지로 가장 왼쪽 도시는 <가 될 수 없다. 그 왼쪽에는 물을 받을 도시가 없기 때문이다.

따라서 두 도시일 때 규칙에 맞는 배치는 정확히 3가지이다.

         A    B       A > B       A < B
         V    V           V       V
  RIVER~ ~ ~ ~ ~     ~ ~ ~ ~ ~   ~ ~ ~ ~ ~RIVER
          "VV"        ">V"         "V<"

도시가 세 개이면 가능한 배치는 8가지이다.

강가에 늘어선 도시(= 처리장)의 수 NC가 주어질 때, 위 규칙을 만족하는 배치의 수 NS를 구하라. NC는 최대 100까지 커질 수 있음에 유의하라.

하수 처리장

문제

입력

출력