120 - Stacks of Flapjacks

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

cfalcon
New poster
Posts: 13
Joined: Fri Dec 19, 2003 12:33 pm

Post by cfalcon » Sat Jan 24, 2004 7:07 am

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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

120 (Flapjacks) input

Post by Quantris » Fri May 28, 2004 5:25 am

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
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Fri May 28, 2004 8:27 pm

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!

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri May 28, 2004 11:13 pm

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
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Location: Bangladesh

Post by Rajib » Tue Jun 22, 2004 12:48 pm

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... :D

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Tue Jun 22, 2004 5:35 pm

actually I meant in the input...

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Wed Jul 21, 2004 10:57 pm

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]
kiha

lwisne
New poster
Posts: 2
Joined: Sat Jul 17, 2004 9:38 am

120 WA

Post by lwisne » Fri Jul 30, 2004 10:40 am

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Fri Jul 30, 2004 4:30 pm

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 :wink:

lwisne
New poster
Posts: 2
Joined: Sat Jul 17, 2004 9:38 am

Post by lwisne » Sat Jul 31, 2004 10:07 am

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? :D

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Sat Jul 31, 2004 7:47 pm

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

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Wed Sep 01, 2004 5:02 pm

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,
kiha

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

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

Post by ImLazy » Thu Jan 27, 2005 3:54 pm

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

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Sun Jan 30, 2005 3:56 pm

Why no one replys? Please help me.
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Please answer me this question about #120.

Post by ImLazy » Sat Feb 05, 2005 11:14 am

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.
I stay home. Don't call me out.

Post Reply

Return to “Volume 1 (100-199)”