302 - John's trip
Moderator: Board moderators
302 - John's trip
Please, help me understand problem text.
Where John live?
In poblem text:
Johnny lives at the _junction_ ending the 1st street input with smaller number.
In clarification:
John lives in the 1st _street_ input.
What first junction/street in John's path?
What mean phrase
"...[path] when written down as a sequence of street numbers is lexicographically the smallest." ?
What right order for street 20 100 3?
100 20 3 or
3 20 100
If only one street in input what should output?
Where John live?
In poblem text:
Johnny lives at the _junction_ ending the 1st street input with smaller number.
In clarification:
John lives in the 1st _street_ input.
What first junction/street in John's path?
What mean phrase
"...[path] when written down as a sequence of street numbers is lexicographically the smallest." ?
What right order for street 20 100 3?
100 20 3 or
3 20 100
If only one street in input what should output?
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
302 john's trip
How could I get a sequence of street numbers is lexicographically the smallest since I could use brutal force?Adrian Kuegel wrote:The first street you are reading is the street where john lives.
Example input:
3 1 6
1 2 1
2 3 2
2 4 3
4 5 4
5 2 5
5 3 9
5 6 7
6 3 8
0 0
1 1 1
0 0
0 0
john lives in street 3 1 at junction 1. Output should be:
1 2 8 7 4 3 5 9 6
1
I always got 1 3 4 5 2 8 7 9 6
like this?
since you use a "brute force" (i'd rather call it depth first exploration) all you have to do is test all the possibilities in the correct order, the first solution you find is the good one.
if you can take sreets i or j, and i<j, try to take street i first, if it fails, fall back to street j, etc...
this problem seems interesting (although still another graph pb), i might give it a try, if i succeed i'll give ya insights
if you can take sreets i or j, and i<j, try to take street i first, if it fails, fall back to street j, etc...
this problem seems interesting (although still another graph pb), i might give it a try, if i succeed i'll give ya insights
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
302 - John Trip
hi,
can anyone provide me sample input/output?
i thought this is euler cycle problem. since the output must be lexicography street name first, from start, i search for the biggest street name, and so on.. (just like finding euler cycle as usual). but got WA in 5 sec.
thanks before
regards,
titid gede
can anyone provide me sample input/output?
i thought this is euler cycle problem. since the output must be lexicography street name first, from start, i search for the biggest street name, and so on.. (just like finding euler cycle as usual). but got WA in 5 sec.
thanks before
![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
regards,
titid gede
Kalo mau kaya, buat apa sekolah?
302 (John's trip) test cases
Hi, is something wrong with my program's output for this input?
input:
2 4 3
2 4 4
2 1 1
1 4 2
2 3 5
3 4 6
2 5 7
2 5 8
4 6 9
5 5 15
1 1 16
3 3 14
6 6 17
7 4 13
6 7 10
7 6 11
6 7 12
0 0
2 1 3
2 2 2
2 2 6
2 2 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
2 1 3
2 2 2
2 2 6
2 1 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
1 2 16
2 1 21
1 4 12
4 1 15
1 3 10
1 3 11
3 1 17
3 1 19
3 2 2
2 3 4
2 7 1
2 7 3
3 7 23
5 7 22
5 3 20
3 4 5
3 4 7
4 6 8
6 4 14
1 1 24
4 4 25
4 4 26
5 6 6
6 5 9
7 6 13
7 6 18
9 1 27
9 9 30
9 8 32
8 8 28
8 8 29
8 8 34
8 10 31
10 4 35
10 10 33
1 8 36
4 8 37
0 0
0 0
my program's output:
1 3 4 7 15 8 5 14 6 9 10 11 17 12 13 2 16
1 2 6 7 8 3 4 5
Round trip does not exist.
1 3 2 4 16 10 5 7 11 12 8 6 9 13 18 14 15 17 20 22 23 19 24 27 30 32 28 29 31 33 35 25 26 37 34 36 21
input:
2 4 3
2 4 4
2 1 1
1 4 2
2 3 5
3 4 6
2 5 7
2 5 8
4 6 9
5 5 15
1 1 16
3 3 14
6 6 17
7 4 13
6 7 10
7 6 11
6 7 12
0 0
2 1 3
2 2 2
2 2 6
2 2 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
2 1 3
2 2 2
2 2 6
2 1 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
1 2 16
2 1 21
1 4 12
4 1 15
1 3 10
1 3 11
3 1 17
3 1 19
3 2 2
2 3 4
2 7 1
2 7 3
3 7 23
5 7 22
5 3 20
3 4 5
3 4 7
4 6 8
6 4 14
1 1 24
4 4 25
4 4 26
5 6 6
6 5 9
7 6 13
7 6 18
9 1 27
9 9 30
9 8 32
8 8 28
8 8 29
8 8 34
8 10 31
10 4 35
10 10 33
1 8 36
4 8 37
0 0
0 0
my program's output:
1 3 4 7 15 8 5 14 6 9 10 11 17 12 13 2 16
1 2 6 7 8 3 4 5
Round trip does not exist.
1 3 2 4 16 10 5 7 11 12 8 6 9 13 18 14 15 17 20 22 23 19 24 27 30 32 28 29 31 33 35 25 26 37 34 36 21
you can check John's home in your code. [ at first look, i can't get John's home correctly].
you wrote:
why biggest? shouldn't you search for smallest?
you wrote:
i thought this is euler cycle problem. since the output must be lexicography street name first, from start, i search for thename, and so on..biggest street
why biggest? shouldn't you search for smallest?
__nOi.m....
Problem 302
I got WA many times.
Is my output for this test case is correct?
Is my output for this test case is correct?
Code: Select all
2 4 3
2 4 4
2 1 1
1 4 2
2 3 5
3 4 6
2 5 7
2 5 8
4 6 9
5 5 15
1 1 16
3 3 14
6 6 17
7 4 13
6 7 10
7 6 11
6 7 12
0 0
2 1 3
2 2 2
2 2 6
2 2 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
2 1 3
2 2 2
2 2 6
2 1 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
1 2 16
2 1 21
1 4 12
4 1 15
1 3 10
1 3 11
3 1 17
3 1 19
3 2 2
2 3 4
2 7 1
2 7 3
3 7 23
5 7 22
5 3 20
3 4 5
3 4 7
4 6 8
6 4 14
1 1 24
4 4 25
4 4 26
5 6 6
6 5 9
7 6 13
7 6 18
9 1 27
9 9 30
9 8 32
8 8 28
8 8 29
8 8 34
8 10 31
10 4 35
10 10 33
1 8 36
4 8 37
0 0
0 0
Code: Select all
1 16 2 13 10 11 12 17 9 3 4 6 14 5 7 15 8
1 2 6 7 8 3 4 5
Round trip does not exist.
10 11 12 14 13 1 16 15 25 26 35 33 31 28 29 32 30 27 17 19 21 2 20 22 18 6 9 8 5 23 3 4 7 37 34 36 24
Correct output:
Code: Select all
1 16 2 3 4 9 10 11 17 12 13 6 14 5 7 15 8
1 2 6 7 8 3 4 5
Round trip does not exist.
10 2 1 3 4 5 7 11 12 8 6 9 13 18 14 15 16 21 17 20 22 23 19 24 27 30 32 28 29 31 33 35 25 26 37 34 36
Thank you very much mf.
I got AC.
If you have questions about this problems http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:50323 I help you
I got AC.
If you have questions about this problems http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:50323 I help you