프로그램 명: ncpc_bread
제한시간: 1 초
[ 문제 요약]
길이 N의 1-N까지 숫자를 각각 한번씩만 쓰는 수열 두개가 주어진다.
첫번째 수열에서 길이가 3인 연속된 부분 수열을 하나 골라 "회전" 시킬 수 있다.
부분 수열 A[i..i+2] (1<=i<=N-2) 를 회전 시킨다는 것은 A[i] = A[i+2], A[i+1] = A[i], A[i+2] = A[i+1] 이 된다는 것이다.
위와 같은 동작을 필요한만큼 수행할수 있다고 할때 첫번째 수열을 두번째 수열로 변환 시킬 수 있는지 구하는게 문제다.
할 수 있으면 Possible, 불가능하면 Impossible 을 출력.
Michael works in a bakery. At the end of his shift, his boss
wants the breads sorted in a certain order. She can’t seem to decide
on which order, though . every day there seems to be a new one
. to Michael’s despair. Michael has worked there for a while now
and has learned a neat trick with his wooden bakery paddle. He
can take three breads next to each other on his paddle and throw
them up in the air such that when they land, the right-most has
moved to the left-most position, and the two other breads have
moved one place to the right. In other words, he can rotate to the
right a subsequence of breads of length three.
Before the end of the shift, his coworkers place the breads in
a long line. Michael would like to sort the line of breads using his
paddle trick. He can take any three consecutive breads along the line on his paddle, rotate them, and then put them
back. Sometimes though, it does not matter how many times he uses his paddle . the line of bread just doesn’t
seem to be possible to sort the way the boss wants. . .
입력
The first line of input contains a positive integer n (3 <= n <= 100 000).
- Then two lines follow:
-
On the first line, a
permutation of the integers 1 through n describing the order in which the breads are lined up.
- On the second line, a permutation of the integers 1 through n describing how Michael’s boss wants the breads sorted.
출력
Output “Possible” if Michael can sort the breads with his paddle in the order prescribed by his boss, otherwise “Impossible”.
입출력 예
입력
4
1 3 4 2
4 3 2 1
출력
Possible
입력
6
1 2 3 4 5 6
6 5 4 3 2 1
출력
Impossible
출처:ncpc/2012/Problem B
요약:likepad
[질/답]
[제출 현황]
[푼 후(0)]