383 - Shipping Routes
Moderator: Board moderators
-
- New poster
- Posts: 12
- Joined: Mon Mar 28, 2005 7:55 pm
- Contact:
-
- New poster
- Posts: 1
- Joined: Mon May 09, 2005 7:07 pm
How to handle empty requests ?
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 ?
Is it this:
Or this ?
What is the correct output for this input ?
Code: Select all
1
1 0 0
AA
Code: Select all
SHIPPING ROUTES OUTPUT
DATA SET OUTPUT 1
<one blank line>
<one more blank line>
END OF OUTPUT
Code: Select all
SHIPPING ROUTES OUTPUT
DATA SET OUTPUT 1
<one only blank line>
END OF OUTPUT
-
- New poster
- Posts: 19
- Joined: Sat Mar 12, 2005 5:56 pm
- Location: Halifax, Nova Scotia, Canada
- Contact:
Hey,
My AC program outputs
But if you're getting WA instead of PE (Presentation Error) you should consider checking your algorithm instead.
Good luck,
Sahand.
My AC program outputs
Code: Select all
SHIPPING ROUTES OUTPUT
DATA SET OUTPUT 1
<one only blank line>
END OF OUTPUT
Good luck,
Sahand.
383 PE
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";
}
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";
}
-
- Learning poster
- Posts: 81
- Joined: Wed May 09, 2007 9:59 pm
- Location: (CSE,DU) Dhaka,Bangladesh
hi sahand
may be u r wrong.
because my AC code shows
this is correct
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
''I want to be most laziest person in the world''
Getting WA 383 ?? some one help plz...
#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;
}
#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;
}
-
- New poster
- Posts: 5
- Joined: Sat Apr 06, 2013 12:42 pm
- Location: Dhaka, Bangladesh
- Contact:
Re: 383 PE
This is the output format of my AC code.
Notice the format specifier for DATA SET. It should be %2d.
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" );
Website: http://binaryrongo.wordpress.com
Facebook: http://facebook.com/aspaul.93
Twitter: http://twitter.com/anindyaspaul
LinkedIn: http://bd.linkedin.com/in/aspaul
UVa: http://uhunt.felix-halim.net/id/210560
Facebook: http://facebook.com/aspaul.93
Twitter: http://twitter.com/anindyaspaul
LinkedIn: http://bd.linkedin.com/in/aspaul
UVa: http://uhunt.felix-halim.net/id/210560
Re: 383 - Shipping Route
For those of you getting presentation errors notice that after DATA SET you need to print two spaces. See below:
Apart from that there are no tricks in this question. Here is one another test case:
Input
Output
Notice that there are two blank lines after data set 1 and 2. Your program should handle that by default.
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
Input
Code: Select all
2
1 0 0
AA
1 0 0
AA
Code: Select all
SHIPPING ROUTES OUTPUT
DATA SET 1
DATA SET 2
END OF OUTPUT
Re: 383 - Shipping Route
![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
![:)](./images/smilies/icon_smile.gif)
Problem 383... Why WA ?
I used BFS and still getting WA.
Can anyone help me with this pls
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: Problem 383... Why WA ?
Always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!