|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||1||1||1||100.000%|
River polution control is a major challenge that authorities face in order to ensure future clean water supply. Sewage treatment plants are used to clean-up the dirty water comming from cities before being discharged into the river.
As part of a coordinated plan, a pipeline is setup in order to connect cities to the sewage treatment plants distributed along the river. It is more efficient to have treatment plants running at maximum capacity and less-used ones switched off for a period. So, each city has its own treatment plant by the river and also a pipe to its neighbouring city upstream and a pipe to the next city downstream along the riverside. At each city's treatment plant there are three choices:
The choices above ensure that:
Let's represent a city discharging water into the river as "V" (a downwards flow), passing water onto its neighbours as ">" (to the next city on its right) or else "<" (to the left). When we have several cities along the river bank, we assign a symbol to each (V, < or >) and list the cities symbols in order. For example, two cities, A and B, can
We could not have "><" since this means A sends its water to B and B sends its own to A, so both are using the same pipe and this is not allowed. Similarly "«" is not possible since A's "<" means it sends its water to a non-existent city on its left.
So we have just 3 possible set-ups that fit the conditions:
A B A > B A < B V V V V RIVER~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~RIVER "VV" ">V" "V<"
If we now consider three cities, we can determine 8 possible set-ups.
Your task is to produce a program that given the number of cities NC (or treatment plants) in the river bank, determines the number of possible set-ups, NS, that can be made according to the rules define above.
You need to be careful with your design as the number of cities can be as large as 100.
The input consists of a sequence of values, one per line, where each value represents the number of cities.
Your output should be a sequence of values, one per line, where each value represents the number of possible set-ups for the corresponding number of cities read in the same input line.
2 3 20
3 8 102334155