10171 - Meeting Prof. Miguel...

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

Moderator: Board moderators

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

Post by Chow Wai Chung » Mon Jun 30, 2003 4:40 pm

Do you correct with the test data i had posted?? There may be more than one place have 0 cost when me and prof. on the same place.

I also use Dijkstra twice to find minimal cost paths in graph to solved this problem

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Tue Jul 01, 2003 11:10 am

Hi Dominik...
Have you consider when your or prof. city has no connection with the others cities? :wink:

Try these inputs:

Code: Select all

2
Y U A B 0
M U A B 0
A C
2
Y U A B 0
M U A B 0
C C
And my AC solution outputs:

Code: Select all

You will never meet.
0 C
Try them.
Good Luck!

angga888 :D

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

Post by Dominik Michniewski » Tue Jul 01, 2003 12:27 pm

Yes I consider such cases ... I also try using Floyd, but I got WA too ...
I guess that I have some IO problem , but I don;t know which is it .... all tests, which I found or which are sended to me my program solved correctly. This problem drive me crazy - looks easy but I have a lot problems with it :(:(:(:(

Best regards
DM
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)

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

Post by Dominik Michniewski » Tue Jul 01, 2003 12:41 pm

Finally I got it. I did small mistake -incorrect type of one variable. and accepted with this minor change :):)

Thank all very much for help and test cases :)

Best regards
DM
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)

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Thu Nov 13, 2003 6:50 pm

After some nasty submissions & WAs, I found out they have some self-loops in the input. (Can be crucial to some who used Floyd's algo like me..)
JongMan @ Yonsei

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Sat Nov 15, 2003 9:04 pm

CUT.......

Got Ac now.

I failed in this test case :

Code: Select all

4
Y U A B 3
M B B A 0
Y B C A 10
M U B D 1
A B
the answer is obvious so I wouldn't tell.

ciaoo...

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

WA-now i got accepted

Post by Mahmud776 » Mon Dec 22, 2003 9:42 am

I am getting WA, my program passed all the input given in this post, can someone provide me with a case where my program fails.

I think my code is ok,i checked every line.But there was nothing wrong.At least i did not find anything.Could anyone help me.
[cpp]
cut. As i got accepted.So i cut this.

[/cpp]
Last edited by Mahmud776 on Tue Dec 23, 2003 2:59 pm, edited 4 times in total.

MD.Morsalin-Al-Saadi
New poster
Posts: 7
Joined: Wed Dec 17, 2003 2:53 pm
Location: Dhaka
Contact:

Post by MD.Morsalin-Al-Saadi » Mon Dec 22, 2003 2:08 pm

hi mahmud,
try yourself. You should modify a little.

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

morsalin

Post by Mahmud776 » Tue Dec 23, 2003 11:34 am

Hi morsalin,

I want specific help! But what you said is known to me.I think this is known to all.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Dec 23, 2003 2:33 pm

Mahmud, You are not considering the fact there could be more than one path from one point to another. In that case you must use the path with lowest cost.

That is whether the cost should be updated depends on its current value.
Good Luck. :wink:

Mahmud776
New poster
Posts: 22
Joined: Mon Dec 22, 2003 9:29 am
Location: Canada

Great help

Post by Mahmud776 » Tue Dec 23, 2003 2:43 pm

Thanks Shamim,
Thanks for your helps, after some modifications according to your advices i got accepted. You are a great helper.
---Mahmud

dvntae
New poster
Posts: 7
Joined: Fri Feb 14, 2003 12:50 pm

Post by dvntae » Sat Apr 17, 2004 7:36 am

i'm a bit confused about printing the lexographical order of possible places.
consider this test case:

2
Y B A B 2
M B B A 5
A B

Would the output should be:
2 B A
-> B is printed first because the minimum energy is 2, or:

2 A B
-> print the minimum energy, afterwards all the possible places in lexographical order.

i tried using floyd, with special modification to handle the self loops. for all the previous inputs in this thread, it handle correctly. but still got some minor problem i guess... and i dun have many time to think bout it coz i'd prefer to go out and play >_<

so please help me with anymore testcases...

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Sat Apr 17, 2004 5:41 pm

the output should be
2 B
because shahriar manzoor will go to B using cost 2
and Prof. Miguel will stay in B so he uses cost 0.

try this data

4
Y B A B 2
Y U B D 0
M B B C 3
M U B D 0
B B
output is
0 B D
Rakeb

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

Post by jackie » Thu Jul 29, 2004 3:44 am

After many WAs i got AC finally.

I use floyed algorithm to compute all pair shortest distance (just for the simple code).

My program is ok for all the input above but the judge said WA. I generate a case and it's about many U or B roads connecting two cities.
2
Y U A B 10
Y U A B 100
A B
0
hope it will help for those who get WA.

BTW pay attention to the input

i use
[cpp]
scanf(" %c %c %c %c %d", &d1, &d2, &d3, &d4, &len);[/cpp]
good luck[/quote]

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

10171 - Meeting Prof. Miguel

Post by helloneo » Thu Jul 21, 2005 7:01 am

i tested all the cases on this board..
it seems to be all right..
but i still get WA..
help plz.. ㅠㅠ

Code: Select all

CUT AFTER AC
Last edited by helloneo on Fri Jun 08, 2007 6:34 am, edited 2 times in total.

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest