10187 - From Dusk Till Dawn

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

kryptolus
New poster
Posts: 16
Joined: Sun Mar 19, 2006 9:36 am
Location: New York

Post by kryptolus » Sat Apr 08, 2006 10:12 am

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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Tue Mar 20, 2007 2:18 pm

What's outpyut for this:

Code: Select all

1
A B 24 6
A B
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Mar 20, 2007 4:40 pm

serur wrote:

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.
Last edited by Jan on Thu Mar 22, 2007 9:55 am, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Thu Mar 22, 2007 9:03 am

Ok, thanks Jan. If

Code: Select all

1
A B 24 3
A B
should be 1 litre?
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Mar 22, 2007 9:25 am

The correct output is

Output:

Code: Select all

Test Case 1.
Vladimir needs 0 litre(s) of blood.
Last edited by Jan on Thu Mar 22, 2007 9:56 am, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Thu Mar 22, 2007 9:32 am

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?
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Mar 22, 2007 9:54 am

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 :oops: . So, the outputs were wrong.
Ami ekhono shopno dekhi...
HomePage

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Sat Mar 24, 2007 2:36 pm

Thanks, Jan.
I implemented shortest path in 0-1 graphs, but still can't get it right.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Mar 25, 2007 10:01 am

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.
Ami ekhono shopno dekhi...
HomePage

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

Post by TimeString » Fri Jul 27, 2007 8:15 am

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

Code: Select all

cut after AC...
Thanks.
Last edited by TimeString on Fri Jan 25, 2008 3:01 pm, edited 1 time in total.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Bad approach?

Post by neno_uci » Fri Nov 09, 2007 7:10 am

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
New poster
Posts: 2
Joined: Fri Jan 25, 2008 9:50 am

Post by micmix » Fri Jan 25, 2008 10:00 am

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
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

it is an unavailable input = =||

Post by TimeString » Fri Jan 25, 2008 3:27 pm

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
New poster
Posts: 2
Joined: Fri Jan 25, 2008 9:50 am

Post by micmix » Sat Jan 26, 2008 2:57 pm

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
New poster
Posts: 3
Joined: Fri Jun 20, 2008 7:22 am

Re: 10187 - From Dusk till Dawn

Post by whateva » Thu Jun 26, 2008 2:02 pm

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... ^^

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest