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.
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!
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!
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](./images/smilies/icon_biggrin.gif)
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](./images/smilies/icon_biggrin.gif)
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![;)](./images/smilies/icon_wink.gif)
[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]
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
![;)](./images/smilies/icon_wink.gif)
[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
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]
try following input:I believe output should be:but your code outputs something different ![:wink:](./images/smilies/icon_wink.gif)
Code: Select all
1
2
3
4
Code: Select all
1
0
2
0
3
0
4
0
![:wink:](./images/smilies/icon_wink.gif)
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](./images/smilies/icon_biggrin.gif)
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](./images/smilies/icon_biggrin.gif)
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.