## Search found 11 matches

Sat Sep 28, 2002 11:30 pm
Forum: Volume 100 (10000-10099)
Topic: 10037 - Bridge
Replies: 84
Views: 23411
I have algorithm like LittleJohn. My program pass all Waterloo tests. I know that one test has more then n people. I tried three ways: 1. read n for i = 1 to n read human read line until empty line 2. read integer (n, dummy line) n = 0 read human; n++; until empty line 3. specification All three met...
Thu Sep 26, 2002 11:40 am
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424
Krzysztof, I understand you algorithm with a starting set of all nodes with firestations before launching dijkstra. so what was the error that caused your program to be Not accepted previously? Because if #fs = 0 then for all vertex dist. from firestation to it was infinity and '1' was written and ...
Wed Sep 25, 2002 2:38 pm
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424
OK. Output belongs to Even is correct. At last I've got ACCEPTED. My algorithm is almost good. It produced bad solutions for m = 0. For this case you can find solution in time O(E) and overall O(ElogV). In spite of that, my program has O(VElogV) complexity because there was less modification to crea...
Wed Sep 25, 2002 11:39 am
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424
My program write the same output. But I'm given WA.
Tue Sep 24, 2002 9:58 am
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424
Output:

Code: Select all

``````1

1``````
Warning. My program is not ACCEPTED.
Sat Sep 21, 2002 3:33 pm
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424
Sorry, no lowest but highest. Find max in array of dist. Normally we use Dijksta with one vertex (source) and dist for this vertex is 0. In this case we use Dijkstra with a set (set of firestations) and for all vertex from this set dist is 0. Now you must launch Dijksta. After it max := -1; for all ...
Sat Sep 21, 2002 11:05 am
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424
To Hongping.

You needn't iterate through all possible intersection.
Initially, you can put all firestations to heap and run Dijkstra.
Than find the intersection with the lowest distance.
Time Complexity O(E*logV).
Sat Sep 21, 2002 11:00 am
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424
2 2
1
2
my output is 1.
Sat Sep 21, 2002 9:57 am
Forum: Volume 102 (10200-10299)
Topic: 10212 - The Last Non-zero Digit.
Replies: 63
Views: 30474
Let l = length of N = O(log(N))
The complexity of this your algorithm is O(N) = O(10^l).
Mon Sep 02, 2002 11:45 pm
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424
I'm sure. Last year there was a contest in Poland. One of problem was the same meaning and I got ACCEPTED.
Mon Sep 02, 2002 4:48 pm
Forum: Volume 102 (10200-10299)
Topic: 10278 - Fire Station
Replies: 59
Views: 20424

### 10278 - Fire Station

I solved this problem but I got WA.
I used Dijkstra and set all cities with fire station on 0, others on infinity.
Could you help me? Maybe a trick?