## 120 - Stacks of Flapjacks

**Moderator:** Board moderators

### 120 (Flapjacks) input

Does the input for 120 sometimes have extra spaces at the end of the line, and sometimes not?

I think that this is the case since that is the only thing I changed between WA and AC, and if so, I think there should be either a warning in the problem, or the input should be standardised to remove such trailing spaces.

I think that this is the case since that is the only thing I changed between WA and AC, and if so, I think there should be either a warning in the problem, or the input should be standardised to remove such trailing spaces.

the way I avoided this was to just add a space (or newline) to the end of the stream before processing. this is better than incrementing pancs an extra time after the loop because then if the input *does* have a space after the last number, the while works like you wanted.

Hope that makes sense, this was annoying me to no end when I kept getting WA on this problem!

**Judge**may reply a WA.

But if more then one output is in same line it may give you WA.

For example:

output1 (space) output2

And if there is any extra space at the end of any output it will give you P.E

For example:

output1 (space)

output2 (space)

Hope you are cleare enough about Judge reply...

Hi,

I can't make out what's wrong with my program :/

I've tested it on all inputs I can think of, I consider the case that two pancakes have the same diameter, but it gives me WA in 0.000

Please help! Check my program or even give me some stupid input

[pascal]

program miazio;

var

t, sort:array [1..30] of longint;

i, j, k, l, lg, m:longint;

g, h:boolean;

{}

procedure zamien (var a, b:longint);

var c:longint; begin c:=a; a:=b; b:=c end;

{}

procedure filip (i:longint);

var

j2:longint;

begin

for j2:=1 to ((lg - i) div 2 + 1) do

zamien (t [lg - j2 + 2 - i], t [j2])

end;

{}

begin

while not eof do

begin

for i:=1 to 30 do

begin

t

I can't make out what's wrong with my program :/

I've tested it on all inputs I can think of, I consider the case that two pancakes have the same diameter, but it gives me WA in 0.000

Please help! Check my program or even give me some stupid input

[pascal]

program miazio;

var

t, sort:array [1..30] of longint;

i, j, k, l, lg, m:longint;

g, h:boolean;

{}

procedure zamien (var a, b:longint);

var c:longint; begin c:=a; a:=b; b:=c end;

{}

procedure filip (i:longint);

var

j2:longint;

begin

for j2:=1 to ((lg - i) div 2 + 1) do

zamien (t [lg - j2 + 2 - i], t [j2])

end;

{}

begin

while not eof do

begin

for i:=1 to 30 do

begin

t

*:=0;*

sortsort

*:=0;*

end;

i:=0;

while not eoln do

begin

read (j);

if not eoln then write (j, ' ') else writeln (j);

inc (i);

tend;

i:=0;

while not eoln do

begin

read (j);

if not eoln then write (j, ' ') else writeln (j);

inc (i);

t

*:=j;*

sortsort

*:=j;*

end;

lg:=i;

readln;

g:=false;

if lg <> 0 then

for i:=1 to lg - 1 do

for j:=i + 1 to lg do

if sortend;

lg:=i;

readln;

g:=false;

if lg <> 0 then

for i:=1 to lg - 1 do

for j:=i + 1 to lg do

if sort

*> sort [j] then*

zamien (sortzamien (sort

*, sort [j]);*

if lg <> 1 then

repeat

{finding the biggest one and putting it on top}

l:=lg;

while t [l] = sort [l] do dec (l);

if (l = 0) or (lg = 1) then begin writeln ('0'); break; end;

j:=l;

k:=l;

while l <> 1 do

begin

dec (l);

if t [l] > t [k] then

k:=l;

end;

if k <> 1 then

begin

h:=true;

for m:=1 to k do

if t [m] <> t [k] then

h:=false;

end;

if (k <> 1) and (not h) then

begin

if g then begin writeln ('0'); break; end else

write (lg - k + 1);

filip (lg - k + 1);

g:=true;

for j:=1 to i - 1 do

if t [j] > t [j + 1] then

g:=false;

if g then begin writeln (' 0'); break; end else write (' ');

end;

{putting the top pancake on its right place}

for j:=1 to lg - 1 do

if t [j] > t [j + 1] then

g:=false;

if g then begin writeln ('0'); break; end;

l:=lg;

while t [l] = sort [l] do dec (l);

filip (lg - l + 1);

write (lg - l + 1, ' ');

g:=true;

for j:=1 to lg - 1 do

if t [j] > t [j + 1] then

g:=false;

if g then writeln ('0');

until g else

writeln ('0');

end;

end.

[/pascal]if lg <> 1 then

repeat

{finding the biggest one and putting it on top}

l:=lg;

while t [l] = sort [l] do dec (l);

if (l = 0) or (lg = 1) then begin writeln ('0'); break; end;

j:=l;

k:=l;

while l <> 1 do

begin

dec (l);

if t [l] > t [k] then

k:=l;

end;

if k <> 1 then

begin

h:=true;

for m:=1 to k do

if t [m] <> t [k] then

h:=false;

end;

if (k <> 1) and (not h) then

begin

if g then begin writeln ('0'); break; end else

write (lg - k + 1);

filip (lg - k + 1);

g:=true;

for j:=1 to i - 1 do

if t [j] > t [j + 1] then

g:=false;

if g then begin writeln (' 0'); break; end else write (' ');

end;

{putting the top pancake on its right place}

for j:=1 to lg - 1 do

if t [j] > t [j + 1] then

g:=false;

if g then begin writeln ('0'); break; end;

l:=lg;

while t [l] = sort [l] do dec (l);

filip (lg - l + 1);

write (lg - l + 1, ' ');

g:=true;

for j:=1 to lg - 1 do

if t [j] > t [j + 1] then

g:=false;

if g then writeln ('0');

until g else

writeln ('0');

end;

end.

[/pascal]

kiha

### 120 WA

I have no clue why this gives WA...can anyone help?

[cpp]

#include <iostream>

#include <deque>

#include <string>

#include <algorithm>

using namespace std;

int main()

{

deque<int> main, temp, sorted;

char curInput[100];

string curString;

int idx, endIdx, dummy;

while(cin.getline(curInput, 100))

{

main=deque<int>();

temp=deque<int>();

curString=string(curInput);

idx=0;

//parse string into main deque

for(int x=0; x<curString.size(); x++)

{

if(curString[x]==' ')

{

main.push_back(atoi(curString.substr(idx, x-idx).c_str()));

idx=x+1;

}

}

main.push_back(atoi(curString.substr(idx, main.size()-idx).c_str()));

//print out intial deque

for(int x=0; x<main.size(); x++)

{

cout << main[x] << " ";

}

cout << endl;

sorted=main;

sort(sorted.begin(), sorted.end());

//endIdx is the last sorted element in the main deque

endIdx=main.size()-1;

while(endIdx>=0 && main[endIdx]==sorted[endIdx])

endIdx--;

while(endIdx>=0)

{

//do this one of the biggest unsorted element is at the top

if(sorted[endIdx]==main[0])

{

cout << sorted.size()-endIdx << " ";

//flip them using the temp deque

for(int x=0; x<=endIdx; x++)

{

temp.push_front(main.front());

main.pop_front();

}

for(int x=0; x<=endIdx; x++)

{

main.push_front(temp.back());

temp.pop_back();

}

while(endIdx>=0 && main[endIdx]==sorted[endIdx])

endIdx--;

}

//do this one if you need to bring the biggest unsorted element to the top

else

{

//find it

deque<int>::iterator midget = find(main.begin(), main.end(), sorted[endIdx]);

//flip them using the temp deque

while(main.front()!=*midget)

{

temp.push_front(main.front());

main.pop_front();

}

temp.push_front(main.front());

main.pop_front();

cout << main.size()+1 << " ";

while(!temp.empty())

{

main.push_front(temp.back());

temp.pop_back();

}

}

}

cout << "0" << endl;

}

return 0;

}[/cpp]

[cpp]

#include <iostream>

#include <deque>

#include <string>

#include <algorithm>

using namespace std;

int main()

{

deque<int> main, temp, sorted;

char curInput[100];

string curString;

int idx, endIdx, dummy;

while(cin.getline(curInput, 100))

{

main=deque<int>();

temp=deque<int>();

curString=string(curInput);

idx=0;

//parse string into main deque

for(int x=0; x<curString.size(); x++)

{

if(curString[x]==' ')

{

main.push_back(atoi(curString.substr(idx, x-idx).c_str()));

idx=x+1;

}

}

main.push_back(atoi(curString.substr(idx, main.size()-idx).c_str()));

//print out intial deque

for(int x=0; x<main.size(); x++)

{

cout << main[x] << " ";

}

cout << endl;

sorted=main;

sort(sorted.begin(), sorted.end());

//endIdx is the last sorted element in the main deque

endIdx=main.size()-1;

while(endIdx>=0 && main[endIdx]==sorted[endIdx])

endIdx--;

while(endIdx>=0)

{

//do this one of the biggest unsorted element is at the top

if(sorted[endIdx]==main[0])

{

cout << sorted.size()-endIdx << " ";

//flip them using the temp deque

for(int x=0; x<=endIdx; x++)

{

temp.push_front(main.front());

main.pop_front();

}

for(int x=0; x<=endIdx; x++)

{

main.push_front(temp.back());

temp.pop_back();

}

while(endIdx>=0 && main[endIdx]==sorted[endIdx])

endIdx--;

}

//do this one if you need to bring the biggest unsorted element to the top

else

{

//find it

deque<int>::iterator midget = find(main.begin(), main.end(), sorted[endIdx]);

//flip them using the temp deque

while(main.front()!=*midget)

{

temp.push_front(main.front());

main.pop_front();

}

temp.push_front(main.front());

main.pop_front();

cout << main.size()+1 << " ";

while(!temp.empty())

{

main.push_front(temp.back());

temp.pop_back();

}

}

}

cout << "0" << endl;

}

return 0;

}[/cpp]

Code: Select all

```
1
2
3
4
```

Code: Select all

```
1
0
2
0
3
0
4
0
```

For anyone who cares, I used the wrong variable in the line:

main.push_back(atoi(curString.substr(idx, main.size()-idx).c_str()));

It should have been curString.size() instead of main.size().

Dont you just hate it when you make a blatant typo and the program still magically works for 99% of inputs?

Hi,

Quantris -- this is indeed true. I also changed only the input processing part [ I read integer by integer and have changed it to reading character by character ] and this got AC. Before, my code got WA in 0.000 or 0.002 even if I added a part:

[pascal]

for i:=1 to 10000000000 do

writeln ('gfdgfdhgfdjfhjadszxgvdhgfj');

[/pascal]

at the end of the program. This of course means it was runtime error. I was really confused, now I'm really angry.

Greetings,

Quantris -- this is indeed true. I also changed only the input processing part [ I read integer by integer and have changed it to reading character by character ] and this got AC. Before, my code got WA in 0.000 or 0.002 even if I added a part:

[pascal]

for i:=1 to 10000000000 do

writeln ('gfdgfdhgfdjfhjadszxgvdhgfj');

[/pascal]

at the end of the program. This of course means it was runtime error. I was really confused, now I'm really angry.

Greetings,

kiha

### 120 Still WA. If you get AC, please try this input.

This is my input and out put:
I think this algorithm is all right:
And this is my code:

Code: Select all

```
Input:
1
3 4 5 8 7 1 2 9 6 10
3 4 5 8 7 1 2 9 6 10 13 14 15 18 17 11 12 19 16 20
3 4 5 8 7 1 2 9 6 10 13 14 15 18 17 11 12 19 16 20 23 24 25 28 27 21 22 29 26 30
Output:
1
0
3 4 5 8 7 1 2 9 6 10
3 2 6 3 8 4 7 5 8 6 9 7 9 0
3 4 5 8 7 1 2 9 6 10 13 14 15 18 17 11 12 19 16 20
3 2 6 3 18 4 7 5 18 6 9 7 9 11 13 12 16 13 18 14 17 15 18 16 19 17 19 0
3 4 5 8 7 1 2 9 6 10 13 14 15 18 17 11 12 19 16 20 23 24 25 28 27 21 22 29 26 30
3 2 6 3 28 4 7 5 28 6 9 7 9 11 13 12 16 13 28 14 17 15 28 16 19 17 19 21 23 22 26 23 28 24 27 25 28 26 29 27 29 0
```

Code: Select all

```
Put the biggest on the top, then FLIP(1).
Put the second biggest on the top, then FLIP(2).
Put the third biggest on the top, then FLIP(3).
......
```

Code: Select all

```
#include<stdio.h>
int cake[30],
cnt_cake;
int flip(int p)
{
int i=0,temp;
while(i<p)
{
temp=cake[i];
cake[i]=cake[p];
cake[p]=temp;
i++;
p--;
}
return 0;
}
int main()
{
int newcake,
max,
i,j,k,l,
temp;
char line[200];
while(gets(line)!=NULL)
{
for(i=0;i<30;i++)
cake[i]=0;
newcake=0;
i=0;
cnt_cake=0;
while(1)
{
if(line[i]>'9' || line[i]<'0')
{
if(newcake==1)
{
newcake=0;
printf("%d ",cake[cnt_cake]);
cnt_cake++;
}
if(line[i]=='\0')
break;
}
else
{
newcake=1;
cake[cnt_cake]*=10;
cake[cnt_cake]+=line[i]-'0';
}
i++;
}
printf("\b\n");
for(i=cnt_cake-1;i>0;i--)
{
max=i;
for(j=i-1;j>=0;j--)
if(cake[j]>cake[max])
max=j;
if(max==i)
continue;
if(max==0)
printf("%d ",cnt_cake-i);
else
printf("%d %d ",cnt_cake-max,cnt_cake-i);
flip(max);
flip(i);
}
printf("0\n");
}
return 0;
}
```

Last edited by ImLazy on Sun Feb 06, 2005 5:53 am, edited 5 times in total.

I stay home. Don't call me out.

### Please answer me this question about #120.

I'm not sure the meaning of "the stack can be sorted so that the largest pancake is on the bottom and the smallest pancake is on the top."

Does that mean:

1. Just put the biggest on the bottom and the smallest on the top. The order of other cakes doesn't matter.

Or:

2. The biggest at position 1, the second biggest at position 2, the third biggest at position 3 .... the smallest on the top.

Which of the two understanding is right, please tell me.

Does that mean:

1. Just put the biggest on the bottom and the smallest on the top. The order of other cakes doesn't matter.

Or:

2. The biggest at position 1, the second biggest at position 2, the third biggest at position 3 .... the smallest on the top.

Which of the two understanding is right, please tell me.

I stay home. Don't call me out.