383 - Shipping Routes

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

Moderator: Board moderators

User avatar
sahand
New poster
Posts: 19
Joined: Sat Mar 12, 2005 5:56 pm
Location: Halifax, Nova Scotia, Canada
Contact:

Post by sahand » Mon May 02, 2005 4:02 am

There should be an 'Edit' button right next to your post.
Take care...

Lord Nemrod
New poster
Posts: 12
Joined: Mon Mar 28, 2005 7:55 pm
Contact:

Post by Lord Nemrod » Mon May 02, 2005 10:20 am

Thanks a lot~!

HomemPalindromo
New poster
Posts: 1
Joined: Mon May 09, 2005 7:07 pm

How to handle empty requests ?

Post by HomemPalindromo » Mon May 09, 2005 7:15 pm

I'm getting a WA too, I guess I don't handle empty (zero) requests the correct way.

What is the correct output for this input ?

Code: Select all

1
1 0 0
AA
Is it this:

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET OUTPUT 1
<one blank line>
<one more blank line>
END OF OUTPUT
Or this ?

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET OUTPUT 1
<one only blank line>
END OF OUTPUT

User avatar
sahand
New poster
Posts: 19
Joined: Sat Mar 12, 2005 5:56 pm
Location: Halifax, Nova Scotia, Canada
Contact:

Post by sahand » Mon May 09, 2005 8:00 pm

Hey,
My AC program outputs

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET OUTPUT 1
<one only blank line>
END OF OUTPUT
But if you're getting WA instead of PE (Presentation Error) you should consider checking your algorithm instead.

Good luck,
Sahand.

Carunty
New poster
Posts: 18
Joined: Sat Jul 08, 2006 2:40 am

383 PE

Post by Carunty » Mon Jul 24, 2006 8:40 pm

I dont know why I get PE.
Anyone have an idea?

Here is my code.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;

int main(){
int n; cin >> n; cout << "SHIPPING ROUTES OUTPUT" << endl;
for(int i=1;i<=n;++i){
cout << endl << "DATA SET "; if(i<10) cout <<" "; cout << i << endl << endl;
int t=0,x,y,z; cin >> x >> y >> z; string h,k; vector<vector<string> > v; map<string,int> m;
for(int j=0;j<x;++j){cin>>h; m[h]=j; vector<string> w; v.push_back(w);}
for(int j=0;j<y;++j){cin >> h >> k; v[m[h]].push_back(k); v[m[k]].push_back(h);}
for(int j=0;j<z;++j){
cin >> y >> h >> k; int a[x]; memset(a,0,sizeof(a)); a[m[h]]=1; queue<string> q; q.push(h);
while(!q.empty()){
string s=q.front(),t;
for(int i=0;i<v[m[s]].size();++i){
t=v[m[s]];
if(a[m[t]]==0){
a[m[t]]=a[m[s]]+1; q.push(t);
if(t==k) break;
}
}
if(t==k) break; q.pop();
}
if(a[m[k]]>0) cout<<"$"<<(a[m[k]]-1)*100*y<<endl; else cout<<"NO SHIPMENT POSSIBLE"<<endl;
}
}
cout << endl << "END OF OUTPUT";
}

Carunty
New poster
Posts: 18
Joined: Sat Jul 08, 2006 2:40 am

Post by Carunty » Thu Jul 27, 2006 5:40 am

Anyone can help me?

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Fri Mar 14, 2008 10:31 pm

hi sahand
may be u r wrong.
because my AC code shows

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET  1
<one blank line>
<one more blank line>
END OF OUTPUT 
this is correct
''I want to be most laziest person in the world''

regan
New poster
Posts: 4
Joined: Wed Apr 28, 2010 6:24 pm

Getting WA 383 ?? some one help plz...

Post by regan » Wed May 05, 2010 11:17 pm

#include<iostream>
#include<queue>
#include<vector>
#define max 50

using namespace std;

vector <long> edge[max];
char node[max][10];
long color[max],dist[max],n;

long find_pos(char *name)
{
long pos=-1;
for(long i=0;i<=n;i++)
{
if(strcmp(name,node)==0)
{
pos=i;
break;
}
}
if(pos==-1)
{
pos=n;
n++;
strcpy(node[pos],name);
}
return pos;
}

void bfs(long source,long n)
{
long u,i;
for(i=0;i<n;i++)
{
color=1;
dist=10000;
}
color[source]=2;
queue <long> q;
dist[source]=0;
q.push(source);
while(!q.empty())
{
u=q.front();
q.pop();
for(i=0;i<edge.size();i++)
{
if(color[edge]==1)
{
color[edge]=2;
dist[edge]=dist+1;
q.push(edge);
}
}
}
}

int main()
{
long t,l,j,k,n,m,q,ship;
char nam[10],namm[10],ch;
cin>>t;
cout<<"SHIPPING ROUTES OUTPUT\n\n";
for(l=0;l<t;l++)
{
cout<<"DATA SET "<<l+1<<endl<<endl;
cin>>n>>m>>q;
for(j=0;j<n;j++) {
scanf("%s",&nam);
find_pos(nam);
}
for(j=0;j<m;j++)
{
cin>>nam>>namm;
edge[find_pos(nam)].push_back(find_pos(namm));
edge[find_pos(namm)].push_back(find_pos(nam));
}
for(j=0;j<q;j++)
{
scanf("%ld%c%s%s",&ship,&ch,&nam,&namm);
bfs(find_pos(nam),n);
if(dist[find_pos(namm)]==10000)
{
cout<<"NO SHIPMENT POSSIBLE\n";
}
else
{
cout<<"$"<<ship*100*dist[find_pos(namm)]<<endl;
}
}
cout<<endl;
for(j=0;j<n;j++) edge[j].clear();
}
cout<<"END OF OUTPUT\n";
return 0;
}

AnindyaPaul
New poster
Posts: 5
Joined: Sat Apr 06, 2013 12:42 pm
Location: Dhaka, Bangladesh
Contact:

Re: 383 PE

Post by AnindyaPaul » Tue Nov 12, 2013 2:26 pm

This is the output format of my AC code.

Code: Select all

puts( "SHIPPING ROUTES OUTPUT" );
for each case
    printf( "\nDATA SET %2d\n\n", cs++ );
    for each query
        print necessary output
puts( "\nEND OF OUTPUT" );
Notice the format specifier for DATA SET. It should be %2d.

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 383 - Shipping Route

Post by vsha041 » Wed Feb 26, 2014 9:22 am

For those of you getting presentation errors notice that after DATA SET you need to print two spaces. See below:

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET  1 (there are two spaces after the word SET)

$500
$1400
$100
NO SHIPMENT POSSIBLE
$2600

DATA SET  2 (there are two spaces after the word SET)

NO SHIPMENT POSSIBLE

END OF OUTPUT
Apart from that there are no tricks in this question. Here is one another test case:

Input

Code: Select all

2
1 0 0
AA
1 0 0
AA
Output

Code: Select all

SHIPPING ROUTES OUTPUT

DATA SET  1


DATA SET  2


END OF OUTPUT
Notice that there are two blank lines after data set 1 and 2. Your program should handle that by default.

sidsi
New poster
Posts: 7
Joined: Sun Mar 23, 2014 5:28 pm

Re: 383 - Shipping Route

Post by sidsi » Thu May 15, 2014 1:26 pm

:D :D thnx vsha041 i don't think i could figure the two spaces... :)

Pooria
New poster
Posts: 4
Joined: Thu May 29, 2014 9:56 pm

Problem 383... Why WA ?

Post by Pooria » Fri Aug 08, 2014 2:38 pm

I used BFS and still getting WA.
Can anyone help me with this pls

Code: Select all

#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

class Node
{
  public:
            Node(){}
            char color;
            int d;
};

class Queue
{
  public:
            Queue(int n)
            {
                Q = new int[n];
                len = 0;
            }
            int len;
            int* Q;
            void Enq(int m)
            {
                Q[len] = m;
                len++;
            }
            int Deq()
            {
                len--;
                return Q[len];
            }
            bool IsEmpty()
            {
                if(len == 0)
                    return true;
                return false;
            }

};

void BFS(int s,Node* node,int** adjWh,int n)
{
    for(int i=0;i<n;i++)
    {
        node[i].color = 'W';
        node[i].d = -1;
    }
    node[s].color = 'G';
    node[s].d = 0;
    Queue Q(n);
    Q.Enq(s);
    while(Q.IsEmpty() == false)
    {
        int u = Q.Deq();
        for(int v=0;v<n;v++)
        {
            if(adjWh[u][v] == 1 && node[v].color == 'W')
            {
                node[v].color = 'G';
                node[v].d = node[u].d + 1;
                Q.Enq(v);
            }
        }
        node[u].color = 'B';
    }
}


int main()
{
    cout<<"SHIPPING ROUTES OUTPUT\n\n";
    int a[26][26]={0};
    int n;
    cin>>n;
    int c = n+1;
    while(n>0)
    {
        printf("DATA SET  %d\n\n",c-n);
        n--;
        int w,l,r;
        cin>>w>>l>>r;
        int** adjWh = new int*[w];
        for(int i=0;i<w;i++)
            adjWh[i] = new int[w];
        for(int i=0;i<w;i++)
            for(int j=0;j<w;j++)
                adjWh[i][j] = 0;
        string inWh;
        for(int i=0;i<w;i++)
        {
            cin>>inWh;
            a[inWh[0] - 'A'][inWh[1] - 'A'] = i;
        }
        string legL,legR;
        for(int i=0;i<l;i++)
        {
            cin>>legL>>legR;
            adjWh[a[legL[0] - 'A'][legL[1] - 'A']][a[legR[0] - 'A'][legR[1] - 'A']] = 1;
            adjWh[a[legR[0] - 'A'][legR[1] - 'A']][a[legL[0] - 'A'][legL[1] - 'A']] = 1;
        }
        Node* node = new Node[w];

        int** bfsDis = new int*[w];
        for(int i=0;i<w;i++)
        {
            bfsDis[i] = new int[w];
        }

        for(int i=0;i<w;i++)
        {
            BFS(i,node,adjWh,w);
            for(int j=0;j<w;j++)
                bfsDis[i][j] = node[j].d;
        }
        int rWeight,rNumberOfLegs;
        string rWhL,rWhR;
        for(int i=0;i<r;i++)
        {
            cin>>rWeight>>rWhL>>rWhR;
            rNumberOfLegs = bfsDis[a[rWhL[0] - 'A'][rWhL[1] - 'A']][a[rWhR[0] - 'A'][rWhR[1] - 'A']];
            if(rNumberOfLegs >= 0)
            {
                cout<<"$"<<(rWeight*rNumberOfLegs*100)<<endl;
            }
            else
                cout<<"NO SHIPMENT POSSIBLE"<<endl;
        }
        cout<<endl;

    }
    cout<<"END OF OUTPUT";

    return 0;
}


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

Re: Problem 383... Why WA ?

Post by brianfry713 » Fri Aug 08, 2014 9:35 pm

Always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 3 (300-399)”