124 - Following Orders

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

lorderico
New poster
Posts: 6
Joined: Sat Oct 02, 2010 10:47 pm

Re: #124 Looking for test cases

Post by lorderico » Sun Sep 11, 2011 6:14 am

Uh yeah, well it actually works, I was just printing an extra space out at the end :x , Now why did I get WA instead of PE...

Oh well,
Eric

at5anpo3
New poster
Posts: 7
Joined: Sun Apr 29, 2012 6:46 pm

Re: #124 Looking for test cases

Post by at5anpo3 » Sat May 12, 2012 9:43 am

Hello all,

The pdf description of this problem contains in Output section: "Characters on a line are separated by whitespace." This doesn't appear in the text description. The right way is to printf("%c", whatever) without any whitespace.

Best Regards,
at5anpo3

at5anpo3
New poster
Posts: 7
Joined: Sun Apr 29, 2012 6:46 pm

Re: 124 ....i don't know why WA

Post by at5anpo3 » Sat May 12, 2012 9:48 am

Hello all,

The input for this is wrong. The problem states: "There will be at least one, and no more than 300 orderings consistent with the contraints in a specification. "

The last input in this set produces more than 1100 orderings.

Best Regards,
at5anpo3

nbacool2
New poster
Posts: 24
Joined: Fri Jul 25, 2014 4:31 pm

Re: 124 - Following Orders

Post by nbacool2 » Thu Jan 22, 2015 10:41 pm

Guys, any idea why I could possibly be getting WA? I make a standard DFS backtracking for topological sorting. Tested on so many cases and I get all correct outputs. still WA though.

Code: Select all

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 30;
bool exists[MAXN];
int inDegree[MAXN];
bool graph[MAXN][MAXN];
int sequence[MAXN];
bool visited[MAXN];
vector<string> answer;
void read()
{
    memset(exists, 0, sizeof exists);
    memset(inDegree, 0, sizeof inDegree);
    memset(graph, 0, sizeof graph);
    answer.clear();
    string line1, line2;
    getline(cin, line1);
    getline(cin, line2);
    for(int i = 0; i < line1.size(); i += 2)
    {
        exists[line1[i]-'a'] = true;
    }
    for(int i = 0; i < line2.size(); i += 4)
    {
        char from = line2[i];
        char to = line2[i + 2];
        graph[from-'a'][to-'a'] = true;
        ++inDegree[to-'a'];
    }
}
void printSolution(int pos)
{
    string res;
    for(int i = 0; i < pos; ++i)
    {
        res.push_back((char)(sequence[i]+'a'));
    }
    answer.push_back(res);
}
void DFS(int node, int pos)
{
    visited[node] = true;
    sequence[pos] = node;
    for(int i = 0; i < MAXN; ++i)
    {
        if(exists[i] && graph[node][i])
        {
            --inDegree[i];
        }
    }
    bool hasChildren = false;
    for(int i = 0; i < MAXN; ++i)
    {
        if(exists[i] && !visited[i] && inDegree[i] == 0)
        {
            DFS(i, pos + 1);
            hasChildren = true;
        }
    }
    visited[node] = false;
    for(int i = 0; i < MAXN; ++i)
    {
        if(exists[i] && graph[node][i])
        {
            ++inDegree[i];
        }
    }
    if(!hasChildren) printSolution(pos+1);
}
void solve(bool printLine)
{
    for(int i = 0; i < MAXN; ++i)
    {
        if(exists[i] && inDegree[i] == 0) DFS(i, 0);
    }
    sort(answer.begin(), answer.end());
    for(int i = 0; i < answer.size(); ++i)
    {
        cout<<answer[i];
        if(i < answer.size()-1 || printLine) cout<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    while(!cin.eof())
    {
        read();
        solve(!cin.eof());
        if(!cin.eof() || true) cout<<'\n';
    }
    return 0;
}
/*
a b f g
a b b f
v w x y z
v y x v z v w v

*/


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 124 - Following Orders

Post by brianfry713 » Tue Jan 27, 2015 10:12 pm

Don't use cin.eof(), there will be a newline char at the end of the last line of the judge's input.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”