/*
Subject: #120 Stacks of Flapjacks
e-mail: morcavon@gmail.com
Homepage: http://morcavon.com
Building: 02/02/2005 ~ 03/02/2005
Last Update: 03/02/2005
*/
/*
<INPUT>
sequence of stacks of pancakes given as a single line. (top -> bottom)
.
.
.
-
<OUTPUT>
original stack
sequence of flips that results in the stack of pancakes being sorted so that
the largest diameter pancake is on the bottom and the smallest on top. (terminated by 0)
-
<CONDITION>
1 <= # of pancakes <= 30
1 <= diameter <= 100
*/
#include <iostream>
#include <stdlib.h>
#define ONLINE_JUDGE
using namespace std;
typedef struct _cake* pCake;
typedef struct _cake
{
int diameter; // diameter of cake
int position; // position of cake (reverse order)
pCake up, down; // link to sub-cake
} cake;
void flip(pCake head, pCake cakes);
void clear(pCake head);
pCake find_largest(pCake head, int n);
pCake find_last(pCake head, int n);
void display(pCake head);
int main()
{
pCake w_ptr;
cake head;
int nCakes, diameter;
while (cin >> diameter) {
cout << diameter << " ";
for (w_ptr = &head, nCakes = 1; ; nCakes++, w_ptr = w_ptr->down) {
pCake temp = (pCake)malloc(sizeof(cake));
temp->diameter = diameter;
temp->down = NULL;
temp->up = w_ptr;
temp->position = nCakes;
w_ptr->down = temp;
// 줄 단위로 처리해야함...
if (cin.get() == '\n' || cin.eof()) {
cout << "\n";
break;
}
cin >> diameter;
cout << diameter << " "; // echo..이거 다른방법없나=_=;
} // end of input
for (int i = nCakes; i > 1; i--) {
// 이미 제자리에 위치해 있다.
if ((w_ptr = find_largest(&head, i))->position == i)
continue;
if (w_ptr != head.down) {
cout << nCakes - w_ptr->position + 1 << " ";
flip(&head, w_ptr); // 맨위로 옮김
}
w_ptr = find_last(&head, i);
cout << nCakes - i + 1 << " ";
flip(&head, w_ptr); // 맨 아래로 옮김
#ifndef ONLINE_JUDGE
cout << "\n<Display> i = " << i << "\n";
display(&head);
cout << "\n<End>\n";
#endif
}
cout << "0\n";
// clear(&head);
} // end of while(), one stack of pancakes
return 0;
}
void flip(pCake head, pCake cakes)
{
/*
cakes의 바닥에 뒤집게를 놓고 cakes의 위치부터
젤 위에 있는 케이크까지를 뒤집어버린다! =_=;
-
cakes는 절대 NULL이 아니다!!
*/
pCake w_ptr;
pCake temp = cakes->down, swap_temp;
int new_position = 1;
for (w_ptr = cakes; ; ) {
swap_temp = w_ptr->down;
w_ptr->down = w_ptr->up;
w_ptr->up = swap_temp;
w_ptr->position = new_position++;
if (w_ptr->down == head)
break;
else
w_ptr = w_ptr->down;
}
head->down = cakes;
head->down->up = head;
if (temp)
temp->up = w_ptr;
w_ptr->down = temp;
}
void clear(pCake head)
{
pCake w_ptr, temp;
for (w_ptr = head->down; w_ptr != NULL; ) {
temp = w_ptr->down;
free(w_ptr);
w_ptr = temp;
}
}
pCake find_largest(pCake head, int n)
{
// n개의 팬케이크 더미에서 제일 큰걸 구해 포인터를
cake largest;
largest.diameter = 0;
for (head = head->down; n > 0; head = head->down, n--) {
if (head->diameter > largest.diameter) {
largest.diameter = head->diameter;
largest.down = head;
}
}
return largest.down;
}
pCake find_last(pCake head, int n)
{
// 제일 밑에 있는 케이크를 찾음
for (; n > 0; head = head->down, n--)
;
return head;
}
void display(pCake head)
{
for (head = head->down; head != NULL; head = head->down)
cout << head->diameter << " ";
}
