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

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

please

Post by Nick » Wed Feb 12, 2003 4:58 pm

Hi, PMNOX!!
please post your AC code......of P120
i've been getting RTE (SIGSEGV) all the time....and i can't find what the problem is

[c]


#include <stdio.h>

char input[221];
int stack[150][31],org[150][31],count,i,j,k,flag,temp_stack[31],l,n,steps[150][120];


int max_arr(int arr[],int begin, int end)
{
int i,max;
max=arr[begin];
for (i=begin+1;i<=end;i++) if (arr>max) max=arr;
return max;
}



void main(void)
{
count=0;

/*
#ifndef ONLINE_JUDGE
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
#endif
*/

while(fgets(input,220,stdin)!=NULL)
{
if (input[0]==NULL) break;
for (i=j=k=flag=0;i<220;i++)
{
if (input<'0'||input>'9')
{if (flag) stack[count][k++]=j;
j=flag=0;}
else {j=(j*10)+input-'0'; flag=1;}

if (input==NULL) break;
}


for (i=0;i<k;i++) org[count]=stack[count];
org[count][k]=stack[count]=0;




for (j=k,n=0;j>0;j--)
{



for (flag=1,i=k-1;i>0;i--)

if (stack[count]<stack[count][i-1])
{flag=0;break;}

/*if (stack[count][i]!=max_arr(stack[count],0,i)) { flag=0;break;}*/

if (flag) break;
/*else j=i+1; */


/*for (i=l=0;i<j;i++) if (stack[count][i]>l) l=stack[count][i];*/
l=max_arr(stack[count],0,j-1);

for (i=0;i<j&&stack[count][i]!=l;i++);

if (i==j-1) continue;
else if (i)
{
steps[count][n++]=k-i;
for (l=0;i>=0;i--,l++) temp_stack[l]=stack[count][i];

for (l--,i=0;l>=0;l--,i++) stack[count][i]=temp_stack[i];
}

steps[count][n++]=k-j+1;
for (i=0,l=j-1;i<j;i++,l--) temp_stack[l]=stack[count][i];

for (i=0;i<j;i++) stack[count][i]=temp_stack[i];
}
steps[count][n]=0;

count++;
}

for (i=0;i<count;i++)
{

for (j=0;org[i][j]!=0;j++) printf("%d ",org[i][j]);
printf("\n");
for (j=0;;j++) {printf("%d ",steps[i][j]);if (steps[i][j]==0) break;}
printf("\n");
/*
for (j=0;stack[i][j]!=0;j++) printf("%d ",stack[i][j]);
printf("\n");
*/
}

}

[/c]

There's my code!!

Pibben
New poster
Posts: 3
Joined: Sat Jun 14, 2003 9:45 am

120 - pancakes WA

Post by Pibben » Sun Jun 15, 2003 11:51 pm

What's the catch with problem 120? Here's my code:

[cpp]#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iterator>
using namespace std;

void solve(vector<int>& stack, int start) {
if(start==stack.size()) return;

int minpos = start;
for(int c = start; c < stack.size(); ++c) {
if(stack[c]<stack[minpos]) minpos = c;
}
if(minpos!=start) {
if(minpos!=stack.size()-1) {
reverse(stack.begin()+minpos,stack.end());
cout << minpos+1 << " ";
}
if(start!=stack.size()-1) {
reverse(stack.begin()+start,stack.end());
cout << start+1 << " ";
}
}
solve(stack,start+1);
}

int main() {
while(true) {
vector<int> stack;
while(true) {
char c = cin.peek();
int temp;
if(c=='\n') {
cin.ignore(1);
break;
}
cin >> temp;
if(cin.eof()) exit(0);
stack.push_back(temp);
}

if(!stack.empty()) {
copy(stack.begin(), stack.end(), ostream_iterator<int>(cout," "));
cout << endl;
solve(stack,0);
cout << "0";
cout << endl;
}
}
}

[/cpp]

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

Post by oriol78 » Wed Jul 16, 2003 11:44 am

you read correctly all de input?
(sorry, my english is awful)

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder » Sun Jul 20, 2003 7:07 pm

yes i tested your code, it didnt even work for the sample inputs. no wonder it got WA :S

losskid
New poster
Posts: 3
Joined: Mon Jul 28, 2003 7:13 am

120 wa :(

Post by losskid » Thu Aug 07, 2003 4:11 am

//please help

#include <iostream>
#include <strstream>
using namespace std;

int cake[100];
int nCake;

int ReadCakes()
{
nCake=0;
char buf[1024];
if (cin.getline(buf,1024)){
istrstream input(buf);
int diam;
while (input >> diam){
nCake++;
cake[nCake] = diam;
}
return 1;
}
else{
return 0;
}
}

int search(int i)
{
int t = i;
int j;
for (j = i-1;j>=1;j--)
if (cake[j]>=cake[t])
t = j;
return t;
}

void flap(int t,int en)
{
int temp;
int i;
if (t!=1){
cout << nCake - t+1 <<" " << endl;
for (i = t;i>=t/2+1;i--)
{
temp = cake;
cake = cake[t-i+1];
cake[t-i+1] = temp;
}
}
for (i = 1;i<=nCake;i++)
cout << cake << " ";
cout << endl;
for (i = en;i>=en/2+1;i--)
{
temp = cake;
cake = cake[en-i+1];
cake[en-i+1] = temp;
}
cout << nCake - en+1 <<" " << endl;
for (i = 1;i<=nCake;i++)
cout << cake << " ";
cout << endl;
}

void solve()
{
int i;
for (i = nCake;i>1;i--)
{
int t = search(i);
if (t != i){
flap(t,i);
}
}
cout <<0<< endl;
}

int main()
{
while (ReadCakes())
{
solve();
}
return 0;
}

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

Post by UFP2161 » Sun Aug 10, 2003 9:54 pm

Sample input got me this output, which is not correct:
0
5 4 3 2 1
1
1 2 3 4 5
0
5 1 2 3 4
1
4 3 2 1 5
4 3 2 1 5
2
1 2 3 4 5
0

MyThirdEye
New poster
Posts: 1
Joined: Sun Sep 21, 2003 5:57 am

120 - Stack of Flapjacks

Post by MyThirdEye » Sun Sep 21, 2003 6:00 am

I am getting a wrong answer on this particular problem, and i was wondering if anyone had a suggested solution set to try. Before i post some code, though, i have a question. Are the results of flipping supposed to be printed in reverse order? If you look at the problem, the example

5 1 2 3 4 has the solution set of 1 2 0. If you work the problem out, you first flip at two, then at one. This makes me thing that the solution set is printed out from last flip to first. Some help on this question would be appreciated. Here is my code.

[cpp] #include <stdio.h>
#include <stdlib.h>

int iaArray[50];
int iaPosition[50];
int iaOriginalLoop[50];

void vFlip(int iMin, int iMax);
void vPosition(int iMin, int iMax);

void main() {

char chaInputLine[1000];
int iCount;
int iCount2;
int iCount3;
int iLoop1;
char chaElement[5];
int iOrder[100];
int iOrderCount;
int iFirstTime = 0;

//input data
while(gets(chaInputLine)) {
iCount = 0;
iCount2 = 0;
iCount3 = 0;

if(iFirstTime == 1)
printf("\n");
else
iFirstTime = 1;

while(chaInputLine[iCount3] != 0) {
while(chaInputLine[iCount3] != ' ' && chaInputLine[iCount3] != 0) {
chaElement[iCount2] = chaInputLine[iCount3];
iCount2++;
iCount3++;
}
chaElement[iCount2] = 0;
iCount2 = 0;
iCount++;
iaArray[iCount] = atoi(chaElement);
iaOriginalLoop[iCount] = atoi(chaElement);
if(chaInputLine[iCount3] != 0)
iCount3++;
}

vPosition(1, iCount);

iOrderCount = 0;

//Sorting by reversals
for(iLoop1 = 1; iLoop1 < iCount; iLoop1++) {
if(iaPosition[iLoop1] != iLoop1) {
if(iaPosition[iLoop1] != iCount) {
iOrder[iOrderCount] = iaPosition[iLoop1];
iOrderCount++;
vFlip(iaPosition[iLoop1], iCount);
}
vFlip(iLoop1, iCount);
iOrder[iOrderCount] = iLoop1;
iOrderCount++;
}
}
for(iLoop1 = 1; iLoop1 <= iCount; iLoop1++) {
printf("%d", iaOriginalLoop[iLoop1]);
if(iLoop1 + 1 <= iCount)
printf(" ");
}
printf("\n");
for(iLoop1 = iOrderCount - 1; iLoop1 >= 0; iLoop1--) {
printf("%d ", iOrder[iLoop1]);
}
printf("0");
}
}

void vFlip(int iMin, int iMax) {

int iTemp;
int iNewMin = iMin;
int iNewMax = iMax;

//flip array
while(iNewMin < iNewMax) {
iTemp = iaArray[iNewMin];
iaArray[iNewMin] = iaArray[iNewMax];
iaArray[iNewMax] = iTemp;
iNewMin++;
iNewMax--;
}

vPosition(1, iMax);

}

void vPosition(int iMin, int iMax) {

int iLoop1;
int iLoop2;
int iElement;
int iIndex;

for(iLoop1 = iMin; iLoop1 <= iMax; iLoop1++) {
iElement = 500;
iIndex = 0;
for(iLoop2 = 1; iLoop2 <= iMax; iLoop2++) {
if(iaArray[iLoop2] < iElement) {
iElement = iaArray[iLoop2];
iIndex = iLoop2;
}
}
iaPosition[iLoop1] = iIndex;
iaArray[iIndex] = iaArray[iIndex] + 1000;
}

for(iLoop1 = iMin; iLoop1 <= iMax; iLoop1++)
iaArray[iLoop1] = iaArray[iLoop1] - 1000;
}
[/cpp]

thanks,

chris

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Mon Sep 22, 2003 2:00 pm

This problem has a special judge, so it doesn't really matter HOW you sort them, as long as you do.

The strategy that is popular here is find the biggest, flip it to the top, then flip it to its final position.

So, find the largest, flip it to the top, then flip the entire stack over so the top is now bottom.

Then, find next largest, flip it to top, then flip the entire stack except for the bottom one over.

Continue this until they are sorted.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

120 Stack of flap jacks WA ... please help me!!

Post by Maarten » Sat Sep 27, 2003 5:30 pm

I'm getting desperate here, after a day (!) of debugging... I really don't know what's wrong with my program, I even downloaded some test data from somewhere on the internet (http://contest.mff.cuni.cz/cgi-bin/arch ... 3.tgz?c.in), did an *exact* file compare between their output and mine and found no difference... I checked boundary cases, such as a stack with only one pancake.. but still WA.. PLEASE HELP ME!!!

[cpp]
#include <stdio.h>
#include <string.h>

int stack[30];
char line[1024];
int N;

/* return the index of the maximum element of stack[] between 0 and n (inclusive) */
int max( int n ) {
int max = 0;
for( int i=1; i<=n; i++ )
if( stack >= stack[max] )
max = i;
return max;
}

/* flip(N-k) */
int flip( int k ) {
for( int i=0; i<=k/2; i++ ) {
int temp = stack[k-i];
stack[k-i] = stack;
stack = temp;
}
printf( "%d ", N-k );
}

int main(int argc, char *argv[])
{
while( gets(line) != NULL ) {
for( N=0; sscanf(line, "%d %[^\0]", &stack[N], line) == 2; N++ );
N++;

for (int i = 0; i < N-1; i++)
printf("%d ", stack);
printf( "%d\n", stack[N-1] );

int cur = N-1;
while( cur>0 ) {
int index = max(cur);
if( index < cur ) {
if( index > 0 )
flip( index );
flip( cur );
}
cur--;
}
printf( "0\n" );
}
return 0;
}
[/cpp]

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Mon Sep 29, 2003 10:30 am

Come on !! anyone please help me !!

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Mon Sep 29, 2003 10:14 pm

I found my problem, for those who are interested, I had to replace the following lines (which worked fine on my beloved WinXP computer)

Code: Select all

for( N=0; sscanf(line, "%d %[^\0]", &stack[N], line) == 2; N++ ); 
      N++; 
by something like this:

Code: Select all

int pos = 0;
N=0;
while( line[pos] != 0 ) {
   while( line[pos] < '0' || line[pos] > '9' ) pos++;
	int num=0;
	while( line[pos] >= '0' && line[pos] <= '9' ) 
		num = num*10 + line[pos++]-'0';
	stack[N++] = num;
}
Nice, huh ?

Oog
New poster
Posts: 6
Joined: Sat Dec 20, 2003 5:29 am

stringstream bug

Post by Oog » Sat Dec 20, 2003 5:33 am

i think ive found a problem with stringstreams in what ever compiler the judge uses.

here is an accepted solution for 120

[cpp]
#include<cstdio>
#include <iostream>
#include<cstdlib>
#include <memory.h>
#include <algorithm>
#include <sstream>
#include <string>

using namespace std;

int panc[30];
int panc0[30];
int pancs;
char *c,vstup[500];
int i,j;
int comp(const void *p,const void *q) {
return (*(int *)p)-(*(int *)q);
}

void flip (int flip)
{
int stackCopy[30];
int i, size, index;

memcpy ( stackCopy, panc, sizeof (int) * pancs );

size = pancs;

for ( i = 0, index = size - flip; i <= size - flip; ++i, --index )
panc = stackCopy[index];
}

int main() {
stringbuf sb;
stringstream ss;

while ( cin.get ( sb, '\n' ) )
{
cin.ignore ( INT_MAX, '\n' );

ss.clear ();
ss.str ("");
ss << sb.str ();
sb.str ("");

pancs=0;

strcpy ( vstup, ss.str ().c_str () );
for (c=vstup; *c; ) {
sscanf(c,"%d",&panc[pancs++]);
while (*c>='0') c++;
while (*c&&(*c<'0')) c++;
}

/*while ( ss >> panc[pancs] )
pancs++;
*/

for (i=0; i<pancs; i++)
if (!i)
printf("%d",panc0=panc);
else
printf(" %d",panc0=panc);
printf("\n");
qsort(panc0,pancs,sizeof(int),comp);
for (i=pancs-1; i>0; i--)
if (panc!=panc0) {
for (j=i-1; panc[j]!=panc0; j--);
if (j) {printf("%d ",pancs-j); flip(pancs-j);}
printf("%d ",pancs-i); flip(pancs-i);
}
printf("0\n");
}
return 0;
}[/cpp]

now notice the

[cpp] strcpy ( vstup, ss.str ().c_str () );
for (c=vstup; *c; ) {
sscanf(c,"%d",&panc[pancs++]);
while (*c>='0') c++;
while (*c&&(*c<'0')) c++;
}
[/cpp]

if that is commented out and

[cpp] /*while ( ss >> panc[pancs] )
pancs++;*/[/cpp]

is uncommented it gets wrong answer. now i am 99.99999% sure those things do the same thing. if i am wrong please tell me

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Sat Dec 20, 2003 6:57 am

stringstreams are a bit sketchy in general, but for some reason they rarely work with the OJ's compiler. At least half the time I tried using them, my programs would have problems, but after switching to sscanf() they would work. So I've given up on using stringstreams.

Furthermore, after the OJ's compiler was recently updated, the programs that actually succeeded with stringstream earlier are now failing when they are rejudged. And e-mails are now no longer sent out for rejudgiements, so I'm not even informed. :-(

LeoST
New poster
Posts: 7
Joined: Thu Dec 25, 2003 5:10 pm
Location: Russia

problem 120

Post by LeoST » Sat Jan 03, 2004 9:32 pm

My program works on all my tests but gets the WA . Please help me to fix the mistakes.


This is my code

Code: Select all

[pascal]program n120;
var
  stk : array[1..1000] of integer;
  operators : array[1..10000] of integer;
  len : integer;
  max : integer;
  ready : integer;
  maxissue : integer;
  i : integer;
  comandnumb : integer;
procedure swap(var a,b : integer);
var
  temp : integer;
begin
  temp := a;
  a := b;
  b := temp;
end;
procedure flip(FLend : integer);
var
  i : integer;
begin
  i := 1;
  while i <= len - FLend + 2 -i do
    begin
      swap(stk[i],stk[len - FLend + 2 - i]);
      inc(i);
    end;
end;


begin
{  assign(input,'input.txt');
  assign(output,'output.txt');
  reset(input);
  rewrite(output);
}  
while not eof do
begin
  len := 0;
  while not eoln do
    begin
      inc(len);
      read(stk[len]);
    end;
  for i := 1 to len do write(stk[i],' ');
  writeln;
  readln;
  comandnumb := 0;
  ready := 0;
  while ready <> len do
    begin
      max := stk[1];
      maxissue := 1;
      for i := 1 to len - ready do if stk[i] > max then
        begin
          max := stk[i];
          maxissue := i;
        end;
      if maxissue <> len - ready then
        begin
          if maxissue <> 1 then
            begin
              flip(len - maxissue+1);
              inc(comandnumb);
              operators[comandnumb] := len - maxissue + 1;
            end;
          flip(ready+1);
          inc(comandnumb);
          operators[comandnumb] := ready+1;
          inc(ready);
        end                        else
          ready := ready + 1;
    end;
  for i := 1 to comandnumb + 1 do write(operators[i],' ' );
  writeln;
end;

end.
[/pascal][/code]
Best reguards

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

#120

Post by cfalcon » Sat Jan 17, 2004 9:13 pm

hi,
i have one small question. can the input have more than one pancake with the same diameter? thanx a lot.

Post Reply

Return to “Volume 1 (100-199)”