120 - Stacks of Flapjacks

[cfalcon]

hi
thanx a lot now it doesn't say compile error anymore but i still can't find where i went wrong accessing elements in the array that are out of bounds. thanx.

[Quantris]

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.

[Quantris]

I think the problem here is that (ss >> panc[pancs]) returns false if the stringstream hits the end of the stream (that is, the string ends with the last number, with no space after it), so pancs++ doesn't execute the last time.

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!

[UFP2161]

I usually create a new istringstream object per line/block/test/etc. Trying to reuse a stringstream object on the judge is not advisable; it seems certain variables aren't changed when you try to reuse it, so it'll give funky results.

[Rajib]

I got AC in this problem. But I don't think for a space 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...

[Quantris]

actually I meant in the input...

[kiha]

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 :=0;
sort :=0;

end;

i:=0;

while not eoln do
begin

read (j);
if not eoln then write (j, ' ') else writeln (j);
inc (i);
t :=j;
sort :=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 sort > sort [j] then
zamien (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]

[lwisne]

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]

[minskcity]

try following input:

Code: Select all

1
2
3
4

I believe output should be:

Code: Select all

1
0
2
0
3
0
4
0

but your code outputs something different

[lwisne]

Thanks!

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?

[kiha]

But my code does give correct answer for this and it's still WA

[kiha]

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,

[ImLazy]

This is my input and out put:

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

I think this algorithm is all right:

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).
......

And this is my code:

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;
}

[ImLazy]

Why no one replys? Please help me.

[ImLazy]

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.