567 - Risk

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

fcarlos
New poster
Posts: 5
Joined: Sat Jul 27, 2002 4:16 am

567 - Risk

Post by fcarlos » Thu Apr 03, 2003 4:22 pm

Seemingly, the ouput of my program is correct, but the judge give it, always :cry: WA, i would like to know if the error is because
1. My output is not correctly formatted, or
2. My algorithm is not correct.

Thanks in advance

[cpp]
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
using namespace std;
const int MAX_COUNTRIES = 20;
const int NLINES = 19;
const int INFINITY = 32767;

class WFalgorithm {
public:
void initialize( int );
void shortestAllPath( int );
int getMinimumCost( int , int );
void begin( void );
private:
// length of shortest path between i and j
int d[ MAX_COUNTRIES ][ MAX_COUNTRIES ];
// length of direct edge between i and j
int w[ MAX_COUNTRIES][ MAX_COUNTRIES ];
vector<string> v;
};

int main( void ) {
WFalgorithm wf ;
wf.begin();
}

void WFalgorithm::begin( void ) {

int borders;
int country;
int N;
int testCase = 1;

while ( !cin.eof() ) {

// initialize gameboard
for ( int i = 0; i < MAX_COUNTRIES ; i++ ) {
for ( int j = 0; j < MAX_COUNTRIES; j++ ) {
w[ i ][ j ] = INFINITY;
}
}

for ( int i = 1; i <= NLINES; i++ ) {
cin >> borders;
if ( borders == 0 ) continue;
for ( int j = 1; j <= borders; j++ ) {
cin >> country;
w[ i -1 ][ country - 1 ] = 1;
w[ country - 1 ][ i - 1 ] = 1;
}
}


cin >> N;
initialize( MAX_COUNTRIES );
shortestAllPath( MAX_COUNTRIES );
string header("Test Set #" );
cout << header << testCase << endl;
int origin, destin;
for ( int i = 1; i <= N; i++ ) {
cin >> origin >> destin;
int result = getMinimumCost( origin , destin );

cout << setw( 2 ) << resetiosflags( ios::right ) << origin ;
cout << setw( 4 ) << resetiosflags( ios::left ) << " to " ;
cout << setw( 2 ) << resetiosflags( ios::right ) << destin ;
cout << ":" ;
cout << resetiosflags( ios::left ) << setw( 2 ) << result << endl;
}
cout << endl;
cin.get();
testCase += 1;
} // outer while

}

void WFalgorithm::initialize( int n ) {
for ( int i = 0; i < n; i++) {
for ( int j = 0; j < n; j++) {
d[j] = w[j];
}
}
}

void WFalgorithm::shortestAllPath( int n ) {
for (int k=0;k<n;k++)
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
if (d[k] + d[k][j] < d[j]) {
d[j] = d[k] + d[k][j];
}
}

int WFalgorithm::getMinimumCost( int i, int j ) {
return d[ i - 1 ][ j - 1 ];
}
[/cpp]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Apr 04, 2003 8:02 am

If you not correctly format output, you got PE ;-)
At first look your program should works .... I use the same algorithm (Floyd) to find shortest paths between coutries ...

Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

fcarlos
New poster
Posts: 5
Joined: Sat Jul 27, 2002 4:16 am

Input sample

Post by fcarlos » Sat Apr 05, 2003 5:47 pm

Hello, Domini..
I test the given input, and i am getting the ouput correctly..
could you give some ohter sample input for test it?

Carlos

boatfish
New poster
Posts: 18
Joined: Thu May 08, 2003 11:46 am

567

Post by boatfish » Tue Sep 02, 2003 12:39 pm

I tested many cases, all are right.
But it keeps on WA.
[cpp]#include<iostream>
using namespace std;

int table[21][21];

void fw(){
int i,j,k;
for(k=1;k<=20;k++)
for(i=1;i<=20;i++)
for(j=1;j<=20;j++)
if(table[k]+table[k][j]<table[j])
table[j]=table[k]+table[k][j];
}

int main(){
int i,no,t,case_no=0,j,n,x,y;
while(cin.peek()!=EOF){
case_no++;
for(i=1;i<=20;i++)
for(j=1;j<=20;j++)
if(i==j)
table[j]=0;
else
table[j]=100;
for(i=1;i<=19;i++){
cin>>no;
for(j=1;j<=no;j++){
cin>>t;
table[t]=1;
table[t]=1;
}
}

fw();
cout<<"Test Set #"<<case_no<<endl;
cin>>n;
for(i=1;i<=n;i++){
cin>>x>>y;
cout.width(2);
cout<<x<<" to ";
cout.width(2);
cout<<y<<": "<<table[x][y]<<endl;
}
cout<<endl;
}
return 0;
}[/cpp]

Xeno
New poster
Posts: 4
Joined: Mon Nov 17, 2003 2:01 am
Location: Colorado, USA

567 (Risk) - Wrong Answer

Post by Xeno » Mon Nov 17, 2003 2:12 am

[cpp]// http://acm.uva.es/p/v5/567.html

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

const int n = 20;

int main()
{
int set = 0;

while (!cin.eof())
{
set++;
vector<vector<int> > table(n, vector<int>(n, 0));

for (int i = 0; i < n - 1; ++i)
{
int hnn; // higher-numbered neighbors
cin>>hnn;

for (int j = 0; j < hnn; ++j)
{
int neighbor;
cin>>neighbor;
table[neighbor - 1] = 1;
table[neighbor - 1] = 1;
}
}

// Floyd-Warshall the mofo
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
if (table[k] != 0)
for (int j = 0; j < n; ++j)
if (table[k][j] != 0)
if (table[j] == 0 || table[k] + table[k][j] < table[j])
table[j] = table[k] + table[k][j];

cout<<"Test Set #"<<set<<endl;
int pairs;
cin>>pairs;

for (int i = 0; i < pairs; ++i)
{
int from, to;
cin>>from>>to;

cout<<setiosflags(ios::right)<<setw(2)<<from<<" to "<<setw(2)<<to<<": "<<setiosflags(ios::left)<<table[from - 1][to - 1]<<endl;
}

cout<<endl;
}
}[/cpp]

I have no idea why the judge isn't accepting my program. It works for all the example inputs and it even works for another test case that I got from elsewhere on the web (http://www.geocities.com/acmbeganer/p567io.htm). I can only surmise that there is some special input that I must account for, but after thoroughly scanning the problem statement, I can't figure out what it is. Any ideas?
You're in a maze of twisty compiler features, all different.

Xeno
New poster
Posts: 4
Joined: Mon Nov 17, 2003 2:01 am
Location: Colorado, USA

Post by Xeno » Wed Nov 19, 2003 11:12 pm

Bumpity. Come on, someone out there must have solved this problem. What's wrong with my code?
You're in a maze of twisty compiler features, all different.

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

Post by UFP2161 » Thu Nov 20, 2003 5:51 am

Your terminating condition doesn't terminate correctly. Let's say, that the last input had a few spaces after. Then, your !cin.eof () would return true, since you're not at the end of file yet, and thus, while continue trying to read the next number.

Xeno
New poster
Posts: 4
Joined: Mon Nov 17, 2003 2:01 am
Location: Colorado, USA

Post by Xeno » Sat Nov 22, 2003 10:00 am

Exactly right, UFP2161. I changed my terminating condition and it worked like a charm. :D Thanks a lot.

In my defense, the judge gets mad when submissions generate answers with extraneous whitespace, so I don't think it's right that the judge's input files have extra whitespace in them. Gar. :x
You're in a maze of twisty compiler features, all different.

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Try this.

Post by _.B._ » Mon Aug 09, 2004 7:10 pm

Greetings!
Try an input with blank lines and/or blank spaces at the end of the data.
Your program won't stop if finds it at the end, and throws wrong output.
I modified it with that, and it's an ACed ;)

Ah!, freaking important:
Line 20 of the test set contains a single integer (1 <= N <= 100) indicating the number of country pairs that follow.
Is not true!!!!!
I've spent many WA's to finally find out that the real range is:

(1 <= N <= 300)

Keep posting!
_.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Post by I LIKE GN » Thu Sep 01, 2005 10:21 pm

well, i amm getting OLE for this problem
with this code

Code: Select all

cut got ACC...
please help...
thx
Last edited by I LIKE GN on Fri Sep 02, 2005 12:06 pm, edited 1 time in total.
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Try this.

Post by _.B._ » Fri Sep 02, 2005 2:56 am

Greetings!

Try changing char read() for int read() instead.
Read my previous post, the limit in the description is corrupted.
Hope it helps 8)
_.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Re: Try this.

Post by I LIKE GN » Fri Sep 02, 2005 12:05 pm

_.B._ wrote:Greetings!

Try changing char read() for int read() instead.
Read my previous post, the limit in the description is corrupted.
Hope it helps 8)
many many thanx to UUUUUUUUU
have a nice DAY!!!!
RSS
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Good.

Post by _.B._ » Sat Sep 03, 2005 6:19 pm

Glad it helpeld :wink:

Keep posting! :D
_.

User avatar
TripShock
New poster
Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

WA

Post by TripShock » Sat Nov 10, 2007 3:49 pm

Can someone please point out why I'm getting WA for this code? It's just a straightforward implementation of Floyd-Warshall...

Code: Select all

#include <iostream>
#include <algorithm>
#include <iomanip>

using namespace std;

int main()
{
    int Case = 0;
    while (true)
    {
        const int MAX = 20;
        const int INF = 999999999;
        int D[MAX][MAX] = { 0 };
       
        for (int i = 0; i < MAX; i++)
            for (int j = 0; j < MAX; j++)
                if (i == j)
                    D[i][j] = 0;
                else
                    D[i][j] = INF;

        for (int i = 0; i < MAX - 1; i++)
        {
            int Number = 0;
            if (!(cin >> Number))
                return 0;
            for (int j = 0; j < Number; j++)
            {
                int Country = 0;
                cin >> Country;
                D[i][Country - 1] = 1;
                D[Country - 1][i] = 1;
            }
        }
       
        for (int k = 0; k < MAX; k++)
            for (int i = 0; i < MAX; i++)
                for (int j = 0; j < MAX; j++)
                    D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
       
        int Cases = 0;
        cin >> Cases;
        int From = 0;
        int To = 0;
       
        if (Case)
            cout << endl;
        Case++;
        cout << "Test Set #" << Case << endl;
        for (int i = 0; i < Cases; i++)
        {
            cin >> From >> To;
            cout << setw(2) << From << " to " << setw(2) << To << ": ";
            cout << D[From - 1][To - 1] << endl;
        }
    }
   
    return 0;
}
Thanks

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

WA please help me.

Post by alamgir kabir » Fri Nov 23, 2007 5:27 pm

Thanks a lot Sapnil.
I have now ACC.

Code: Select all

code removed after ACC.
Thanks.
Last edited by alamgir kabir on Sat Nov 24, 2007 3:45 pm, edited 1 time in total.

Post Reply

Return to “Volume 5 (500-599)”