TSOC '15 Contest 1 #5 - Giant Ants - Olympiads Online Judge

TSOC '15 Contest 1 #5 - Giant Ants

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

omaewamoushindeiru, kobortor

Problem type

After getting out from the Building of Secrets, BMP and MSA have uncovered the secret cheesecake formula. Unfortunately, the security at the factory is very angry with them. Wanting to avoid social interaction with the security guards, BMP and MSA must get away from the cheesecake factory and get back home safely.

The city BMP and MSA live in represents the worst urban planning you have ever seen, with $N$ $N$ intersections and $M$ $M$ highways, going all over the place and taking up lots of valuable building land. However, that is not your concern right now, BMP and MSA has bribed you with DMOJ points to help them get home safely!

In an attempt to stop them, security has released their newest invention: the Giant Ant Dispenser on $W$ $W$ intersections. The dispenser will constantly dispense an infinite number of ants which will eat BMP and MSA in an instant. Obviously, BMP and MSA has instructed you to avoid all routes where you will run into the giant ants. Luckily, the giant ants will only travel along roads, but since there are an infinite number of ants, they will split off in all directions (but only along roads of course). In addition, ants are quite slow, as they only travel at 0.25 roads per second (meaning that every 4th turn, they will fully move along 1 road) while BMP's car travels at 1 road/second.

Just in case your program can't find a safe way home for BMP and MSA because of either ants blocking their route or because there is no path that will get them home safely, they have a backup plan of sacrificing bobhob314 and begging for mercy from the guards. But only if there is no safe way home (not because they want to save bobhob314 of course, but just in case they have to sacrifice him at some later time).

Note

BMP and MSA always move immediately before the giant ants do. So if BMP and MSA are currently on an intersection that's about to be overrun by ants the next turn, they are safe as long as they're moving to a safe intersection.

However, if BMP and MSA go to an intersection that's about to be overrun by giant ants right before they arrive, they get eaten!

Additionally, ant dispensers cannot start at intersection $1$ $1$ .

Input Specification

The first line will contain $N$ $N$ $(2 \le N \le 100)$ $(2 \leq N \leq 100)$ and $M$ $M$ $(0 \le M \le 30)$ $(0 \leq M \leq 30)$ .

The next $M$ $M$ lines will have $X$ $X$ and $Y$ $Y$ $(1 \le X, Y \le N)$ $(1 \leq X, Y \leq N)$ representing a road between the 2 intersections.

The next line will have $W$ $W$ $(0 \le W \le 15)$ $(0 \leq W \leq 15)$ .

The next $W$ $W$ lines will contain $W_i$ $W_{i}$ , showing that intersection $i$ $i$ has a giant ant dispenser.

Output Specification

Output a single integer, the length of the shortest path for BMP and MSA to get home from $1$ $1$ to $N$ $N$ while avoiding the ants.

If this is not possible, output sacrifice bobhob314.

Sample Input 1

Copy

Sample Output 1

Copy

sacrifice bobhob314

Explanation for Sample Output 1

Assume that the orange represents the intersections where the ants are, and the green is the location of BMP and MSA's car.

Initially, there is a clear path from $1$ $1$ to $N$ $N$ .

$\text{[math]}$

However, after 4 turns the ants spread from intersection $7$ $7$ to intersection $6$ $6$ .

$\text{[math]}$

And blocks the path.

Sample Input 2

Copy

Sample Output 2

Copy

Explanation for Sample Output 2

Initial setup.

$\text{[math]}$

After 3 turns.

$\text{[math]}$

However, BMP and MSA's car moves before the ants, narrowly escaping the ants and getting home just before getting eaten.

$\text{[math]}$

Comments

6

Evanhyd commented on Feb. 11, 2021, 12:05 a.m. ← edited →

Wanting to avoid social interaction with the security guards, BMP and MSA must get away from the cheesecake factory and get back home safely.

People already KNEW the social distance back in 2015.

3

omaewamoushindeiru commented on July 20, 2022, 10:07 p.m.

you bet lol

2

Dan13llljws commented on Dec. 11, 2019, 8:12 p.m. ← edited →

What happens if there is no way home and ants cannot get you as well

-86

bobhob314 commented on Feb. 23, 2015, 9:16 p.m.

I for one as a dignified and fully legal citizen and individual find it completely monstrous that you could create blasphemy that involves sacrificing a fellow human being.

This comment is hidden due to too much negative feedback. Show it anyway.

105

bobhob314 commented on March 8, 2015, 6:06 p.m.

ok u guys r right i disliked myself 2