120 - Stacks of Flapjacks

[Nick]

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]

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]

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

[bugzpodder]

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

[losskid]

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

[UFP2161]

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]

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]

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]

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]

Come on !! anyone please help me !!

[Maarten]

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]

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]

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]

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]

[cfalcon]

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