Flipper
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 521 Accepted Submission(s): 334
Problem Description
Little Bobby Roberts (son of Big Bob, of Problem G) plays this solitaire memory game called Flipper. He starts withn cards, numbered 1 through
n, and lays them out in a row with the cards in order left-to-right. (Card 1 is on the far left; cardn is on the far right.) Some cards are face up and some are face down. Bobby then performsn - 1 flips — either right flips or left
flips. In a right flip he takes the pile to the far right and flips it over onto the card to its immediate left. For example, if the rightmost pile has cards A, B, C (from top to bottom) and card D is to the immediate left, then flipping the pile over onto
card D would result in a pile of 4 cards: C, B, A, D (from top to bottom). A left flip is analogous.
n, and lays them out in a row with the cards in order left-to-right. (Card 1 is on the far left; cardn is on the far right.) Some cards are face up and some are face down. Bobby then performsn - 1 flips — either right flips or left
flips. In a right flip he takes the pile to the far right and flips it over onto the card to its immediate left. For example, if the rightmost pile has cards A, B, C (from top to bottom) and card D is to the immediate left, then flipping the pile over onto
card D would result in a pile of 4 cards: C, B, A, D (from top to bottom). A left flip is analogous.
The very last flip performed will result in one pile of cards — some face up, some face down. For example, suppose Bobby deals out 5 cards (numbered 1 through 5) with cards 1 through 3 initially face up and cards 4 and 5 initially face down. If Bobby performs
2 right flips, then 2 left flips, the pile will be (from top to bottom) a face down 2, a face up 1, a face up 4, a face down 5, and a face up 3.
Now Bobby is very sharp and you can ask him what card is in any position and he can tell you!!! You will write a program that matches Bobby’s amazing feat.
Input
Each test case will consist of 4 lines. The first line will be a positive integern (2 ≤
n ≤ 100) which is the number of cards laid out. The second line will be a string ofn characters. A character U indicates the corresponding card is dealt face up and a character D indicates the card is face down. The third line is a string
ofn - 1 characters indicating the order of the flips Bobby performs. Each character is either R, indicating a right flip, or L, indicating a left flip. The fourth line is of the formm q1 q2 . . . qm, where
m is a positive integer and 1 ≤qi ≤ n. Each
qi is a query on a position of a card in the pile (1 being the top card,n being the bottom card). A line containing 0 indicates end of input.
n ≤ 100) which is the number of cards laid out. The second line will be a string ofn characters. A character U indicates the corresponding card is dealt face up and a character D indicates the card is face down. The third line is a string
ofn - 1 characters indicating the order of the flips Bobby performs. Each character is either R, indicating a right flip, or L, indicating a left flip. The fourth line is of the formm q1 q2 . . . qm, where
m is a positive integer and 1 ≤qi ≤ n. Each
qi is a query on a position of a card in the pile (1 being the top card,n being the bottom card). A line containing 0 indicates end of input.
Output
Each test case should generate m + 1 lines of output. The first line is of the form
Pile t
where t is the number of the test case (starting at 1). Each of the nextm lines should be of the form
Card qi is a face up k.
or
Card qi is a face down k.
accordingly, for i = 1, ..,m, where k is the number of the card.
For instance, in the above example with 5 cards, if qi = 3, then the answer would be
Card 3 is a face up 4.
Sample Input
5 UUUDD RRLL 5 1 2 3 4 5 10 UUDDUUDDUU LLLRRRLRL 4 3 7 6 1 0
Sample Output
Pile 1 Card 1 is a face down 2. Card 2 is a face up 1. Card 3 is a face up 4. Card 4 is a face down 5. Card 5 is a face up 3. Pile 2 Card 3 is a face down 1. Card 7 is a face down 9. Card 6 is a face up 7. Card 1 is a face down 5.
/*
hdoj 3328 栈的应用
将n张牌横向排开，从左到右编号1~n。输入正反情况
R操作就是把最右边的一堆牌放到次右边并改变每一张牌的方向，
L操作就是把最左边的一堆牌放到次左边并改变每一张牌的方向。
注意：每一对牌的最上面一个先取出，因此，直接用栈来模拟比较方便。
接着输入m个提问x，问从上到下第x张牌的情况。
*/
#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
#define N 110
struct node{
char dir;
int val;
};
node card,ans[N];
char str1[N],str2[N];
stack<node> st[N];
int n;
int main()
{
int cas,i,len,l,r,k,m,a;
cas=1;
while(scanf("%d",&n),n)
{
scanf("%s",str1);
scanf("%s",str2);
printf("Pile %d\n",cas++);
for(i=0;i<=n;i++)//清空栈
while(!st[i].empty())
st[i].pop();
for(i=1;i<=n;i++)//存储
{
card.dir=str1[i-1];
card.val=i;
st[i].push(card);
}
len=strlen(str2);
l=1;r=n;
for(i=0;i<len;i++)//执行每一个翻转
{
if(str2[i]=='R')
{
while(!st[r].empty())
{
card=st[r].top();
st[r].pop();
if(card.dir=='D')//方向翻转
card.dir='U';
else
card.dir='D';
st[r-1].push(card);
}
r--;
}
else
{
while(!st[l].empty())
{
card=st[l].top();
st[l].pop();
if(card.dir=='D')
card.dir='U';
else
card.dir='D';
st[l+1].push(card);
}
l++;
}
}
k=1;
while(!st[l].empty())
{
card=st[l].top();
st[l].pop();
ans[k++]=card;
}
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&a);
printf("Card %d is a face ",a);
if(ans[a].dir=='D')
printf("down ");
else
printf("up ");
printf("%d.\n",ans[a].val);
}
}
return 0;
}