Problem with solution to UVa 120

[oldspiderdude]

Hi, I've written the solution to UVa 120:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=56&mosmsg=Submission+received+with+ID+19900326

can someone tell me what is wrong with my solution?
It is returning wrong answer all the time, even though the steps it generates
don't have repeats and orders the pancakes properly.

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <sstream>

using namespace std;

vector< vector<int> > allTests;
vector<int> currSituation;
string line, instruc;
string* pInstruct=&instruc;
int i;
int numTests, numPancakes;

void printInstruc(vector <int> unsorted,vector <int> sorted, int curPan, int vecSize, string* instructions) {
if (vecSize==1) {
    cout << unsorted[0] << endl;
    cout << 0 << endl;
}
bool alwaysBigger;
bool spaceBefore=true;
int curDiam;
    if (curPan==vecSize-1) {
        return;
    }
    if (curPan==1) {
        sort(sorted.begin(), sorted.end());
        spaceBefore=false;
        for (int loop=0; loop<vecSize; loop++) {
            if (spaceBefore) cout << " ";
            cout << unsorted[loop];
            spaceBefore=true;
        }
        spaceBefore=false;
        cout << endl;
    }

curDiam=*(sorted.end()-curPan);

    for (int loop=1; loop<=vecSize; loop++) {
        if (*(unsorted.end()-loop)==curDiam) {
            if (loop==curPan) break;
            if (loop!=vecSize) {
            stringstream ss;
            ss<<loop;
            if (spaceBefore) {
                *instructions+=" ";
            }
            *instructions+=ss.str();
            spaceBefore=true;
            reverse(unsorted.begin(), unsorted.end()-loop+1);
            }
            if (spaceBefore) {
                *instructions+=" ";
            }
            stringstream ss;
            ss<<curPan;
            *instructions+=ss.str();
            spaceBefore=true;
            reverse(unsorted.begin(),unsorted.end()-curPan+1);
        break;
        }
    }
    printInstruc(unsorted, sorted, curPan+1, vecSize, instructions);
    if (curPan==1) {
        cout << *instructions;
        if (spaceBefore)cout << " ";
        cout << "0" << endl;
    }
return;
}

int numCases;

int main()
{

    while (getline(cin, line, '\n')) {
        currSituation.clear();
        if (line=="") continue;
        stringstream ss(line);
        while (ss>>i){
            currSituation.push_back(i);
        }
        allTests.push_back(currSituation);
        *pInstruct="";
        printInstruc(currSituation,currSituation,1,currSituation.size(), pInstruct);
    }

    return 0;
}

[Handy Andy]

Hello oldspiderdude,

This is what I noticed:

1. The header file "sstream" is included twice. You only need one.

2. Line 79 the third parameter is not needed. "\n" is a default.

3. Line 81 needs to end in "break" not "continue". "continue" will bypass the rest of the code returning to the while condition causing an endless loop. "break" will break out of the while loop.

What I found missing is the ability to read from a file. As per my interpretation of the program requirements. So line 79 should be reading from a file not std::cin.

can someone tell me what is wrong with my solution?

What do you think is wrong with the program? Where do you think it is going wrong?
When I ran the program with the sample data "5 1 2 3 4" it printed out "1 2 0". According to the example from your link it worked.

Hope that helps,

Andy

[ne555]

explain your algorithm and comment your code.

you need to test extreme cases, your program crashes (infinite recursion) if there is only one pancake, and produces no output if there are two.


> 1. The header file "sstream" is included twice. You only need one.
header guards

> 2. Line 79 the third parameter is not needed. "\n" is a default.
defaults are evil

> "continue" will bypass the rest of the code returning to the while condition
> causing an endless loop.
¿why?

> When I ran the program with the sample data "5 1 2 3 4" it printed out "1 2 0".
> According to the example from your link it worked.
one testcase is more than enough.

(the program is tested with an unknown input, and it reports things like "correct", "wrong answer", "time limit exceed", that's all the info you get)