10187 - From Dusk Till Dawn

[kryptolus]

The following page has some information about the restricted packages:
http://acm.uva.es/problemset/java.html

[serur]

What's outpyut for this:

Code: Select all

1
A B 24 6
A B

[Jan]

Code: Select all

1
A B 24 6
A B

My accepted code returns
Output:

Code: Select all

Test Case 1.
Vladimir needs 0 litre(s) of blood.

[serur]

Ok, thanks Jan. If

Code: Select all

1
A B 24 3
A B

should be 1 litre?

[Jan]

The correct output is

Output:

Code: Select all

Test Case 1.
Vladimir needs 0 litre(s) of blood.

[serur]

Sorry, but I can't see why. Why he can't start at midnight (00.00 AM) and arrive at B at 03.00 AM?

[Jan]

Sorry for the outputs I have posted. I have corrected both outputs. The reason for posting wrong output is simple

Code: Select all

1
1 
A B 24 6 
A B

It is the correct input format. I just copied your input and ran my code . So, the outputs were wrong.

[serur]

Thanks, Jan.
I implemented shortest path in 0-1 graphs, but still can't get it right.

[Jan]

Try the cases...

Input:

Code: Select all

2
3
Dhk Ctg 1 2
Ctg Syl 2 3
Syl Mym 4 5
Dhk Syl
3
Dhk Ctg 18 19
Ctg Syl 19 20
Syl Mym 21 22
Dhk Ctg

Output:

Code: Select all

Test Case 1.
Vladimir needs 1 litre(s) of blood.
Test Case 2.
There is no route Vladimir can take.

Hoe these help.

[TimeString]

My code gets WA several times. Can someone tell me why??

Code: Select all

cut after AC...

Thanks.

[neno_uci]

I am trying to solve this problem using the following approach:

1. For each route (city1 city2 departure_time travelling_time):
a) if departure_time lies between 18 and 24, departure_time -= 18
b) if departure_time lies between 1 and 6, departure_time += 6
c) else ignore route.

after these steps the following mapping has been made:
18 -> 0 1 -> 7
19 -> 1 2 -> 8
20 -> 2 3 -> 9
21 -> 3 4 -> 10
22 -> 4 5 -> 11
23 -> 5 6 -> 12
24 -> 6

if departure_time + travelling_time <= 12 then the train arrives before 6AM and the route must be added to the list of routes available from city1, else ignore route.

2. After that I try to generate every possible path from starting_city to destination_city using recursion taking into account that:

if the time at which I arrive to a city <= departure_time of a route the vampire does not have to drink blood, else he must drink one litre.

Is there anything wrong in that?

This is my code... It would be very helpful if you find some input that makes my program fail.

Code: Select all

#include <stdio.h>
#include <string.h>

#define MAXVERT 100
#define MAXEDGE 1000
#define LEN 32
#define INF 1000000

typedef struct aruta
{
    int final;
    int hora_salida;
    int hora_llegada;
} ruta;

int n, ini, fin, min;
char ciudad[MAXVERT + 1][LEN + 1];
int grado[MAXVERT + 1];
ruta mat[MAXVERT + 1][MAXEDGE + 1];

bool mark[MAXVERT + 1];

int buscar_ciudad(const char *key)
{
    for (int i = 1; i <= n; i++)
        if (strcmp(key, ciudad[i]) == 0)
            return i;
            
    return 0;
}

void go(int nodo, int time, int cons)
{
    if (cons > min)
        return;

    if (nodo == fin)
    {
        if (cons < min)
            min = cons;
            
        return;
    }
    
    for (int i = 1; i <= grado[nodo]; i++)
    {
        int final, hora_salida, hora_llegada;
        
        final = mat[nodo][i].final;
        hora_salida = mat[nodo][i].hora_salida;
        hora_llegada = mat[nodo][i].hora_llegada;
        
        if (!mark[final])
        {
            mark[final] = true;
            
            if (time <= hora_salida)
                go(final, hora_llegada, cons);
            else
                go(final, hora_llegada, cons + 1);
                
            mark[final] = false;
        }
    }
}

int main()
{
    int test;
    
    scanf("%d", &test);
    
    for (int tt = 1; tt <= test; tt++)
    {
        int nr, index1, index2, hs, td;
        char s1[LEN + 1], s2[LEN + 1];
        
        printf("Test Case %d.\n", tt);

        scanf("%d", &nr);
        n = 0;
        
        while (nr--)
        {
            scanf("%s %s %d %d", &s1, &s2, &hs, &td);

            index1 = buscar_ciudad(s1);
            
            if (index1 == 0)
            {
                index1 = ++n;
                grado[n] = 0;
                strcpy(ciudad[n], s1);
            }
            
            index2 = buscar_ciudad(s2);
            
            if (index2 == 0)
            {
                index2 = ++n;
                grado[n] = 0;
                strcpy(ciudad[n], s2);
            }
            
            if (hs >= 18 && hs <= 24)
            {
                hs -= 18;
            }
            else
                if (hs >= 1 && hs <= 6)
                {
                    hs += 6;
                }
                else
                    continue;
                    
            if (hs + td <= 12)
            {
                grado[index1]++;
                mat[index1][ grado[index1] ].final = index2;
                mat[index1][ grado[index1] ].hora_salida = hs;
                mat[index1][ grado[index1] ].hora_llegada = hs + td;
                
//                printf("%d -> %d HS=%d HL=%d\n", index1, index2, hs, hs + td);
            }
        }
        
        scanf("%s %s", &s1, &s2);
        ini = buscar_ciudad(s1);
        fin = buscar_ciudad(s2);
        
        if (ini && fin)
        {
            for (int i = 1; i <= n; i++)
                mark[i] = false;

            min = INF;
            mark[ini] = true;
            
            go(ini, 0, 0);
            
            if (min != INF)
            {
                printf("Vladimir needs %d litre(s) of blood.\n", min);
            }
            else
            {
                puts("There is no route Vladimir can take.");
            }
        }
        else
        {
            puts("There is no route Vladimir can take.");
        }
    }
    
    return 0;
}

[micmix]

Other question:
If the train arrives, let say at 22 and another leaves at 22 (same hour), are we able to leave with the second train??

[TimeString]

getting wrong answer a lot of times and finally ACCEPTED!!!

i think it is a normal bfs problem but the starting time doesn't have a range, namely the starting time can be very large, more than 24, so after you read the starting time, you need to mod 24, and then judge wheter it is <=6 or >=18. if starting time is out of this range, Vladimir surely couldn't take this train.

to micmix, yes, it is available to take more than one train at the same day, and consider Vladimir can change to another train immediately, i.e. don't need any time.

[micmix]

I've implemented it using dijkstra algorithm. It works fine with all test data posted in this thread. I've tried 1000 connections and 100 towns, yet it still gets WA. I think that it may be because of No connections, but I'm not shure. Anyone has any wierd test data with wrong connections that may be incorrectly accepted??

[whateva]

no.. we must not mod the departing time with 24... mine didn't use any mod and still AC... so just use the "> 6 or < 18" rule of range for the departing time... ^^