CCO '10 P1 - Barking Dogs! - Olympiads Online Judge

CCO '10 P1 - Barking Dogs!

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 1G

Problem type

Canadian Computing Competition: 2010 Stage 2, Day 1, Problem 1

You live in a neighbourhood of dogs. Dogs like dogs. Dogs like barking even better. But best of all, dogs like barking when other dogs bark.

Each dog has a collection of dogs that can hear him/her. Each dog has a delay time in barking if they hear another dog bark.

Dog 1 always starts barking first, and this first bark occurs during second number $0$ $0$ .

Your job is to figure out how many times each dog has barked in the first $T$ $T$ seconds (inclusive). You can assume that sound travels instantly from the mouth of one dog into the ear of another.

Each dog spends any given second doing one of three things: sleeping, waiting, or barking. If dog $i$ $i$ hears a bark during a second $n$ $n$ when it is sleeping, the dog wakes up and waits during seconds $n+1$ $n + 1$ through $n+w_i-1$ $n + w_{i} - 1$ inclusive, barks during second $n+w_i$ $n + w_{i}$ , then goes back to sleep from second $n+w_i+1$ $n + w_{i} + 1$ onward. If a dog hears a bark during a second in which it is waiting or barking, it ignores the bark.

During second number $0$ $0$ , all the dogs except dog $1$ $1$ are sleeping.

Input Specification

The first line of input is $D$ $D$ $(1 \le D \le 1\,000)$ $(1 \leq D \leq 1 000)$ , the number of dogs in the neighbourhood.

The next $D$ $D$ lines of each contain an integer $w_i$ $w_{i}$ $(1 \le w_i \le 1\,000)$ $(1 \leq w_{i} \leq 1 000)$ representing the time (in seconds) that dog $i$ $i$ waits before considering to bark upon hearing a bark.

The next line contains the number $F$ $F$ $(1 \le F \le 10\,000)$ $(1 \leq F \leq 10 000)$ . On each of the next $F$ $F$ lines, there are two integers: $i$ $i$ and $j$ $j$ , representing that when dog $i$ $i$ barks, dog $j$ $j$ hears this bark. It is never the case that $i = j$ $i = j$ .

The next line (which is the last line of input) contains the integer $T$ $T$ $(1 \le T \le 1\,000)$ $(1 \leq T \leq 1 000)$ , the number of seconds during which your program is to monitor the dogs.

Output Specification

Produce one line of output for each dog in order from dog $1$ $1$ to dog $D$ $D$ . On line $i$ $i$ , output the number of seconds between $1$ $1$ and $T$ $T$ inclusive that dog $i$ $i$ spent barking.

Sample Input 1

Copy

Sample Output 1

Copy

3
2
2

Sample Input 2

Copy

Sample Output 2

Copy

2
2
1

Comments

5
anishmahto commented on Jan. 31, 2017, 3:30 p.m.
I'm not sure I understand sample input 1. This is what I get:

Dog 1 barks at second 0

Dog 2 hears at second 0, barks at second 1 (0 + 1)

Dog 3 hears at second 1, barks at second 4 (1 + 3)

Dog 1 hears at second 4, barks at second 5 (4 + 1)

Dog 2 hears at second 5, barks at second 6 (5 + 1)

Dog 3 hears at second 6, barks at second 9 (6 + 3)

Dog 1 hears at second 9, barks at second 10 (9 + 1)

Between seconds 1 to 10:

Dog 1 barks for a total of 2 seconds

Dog 2 barks for a total of 2 seconds

Dog 3 barks for a total of 2 seconds

5

leonchen0613 commented on Oct. 24, 2017, 6:13 p.m.

I agree, the output specification should say the number of seconds between $0$ $0$ and $T$ $T$ inclusive that dog $i$ $i$ spent barking.

1

Badmode commented on Sept. 7, 2021, 11:06 p.m.

But this is a CCO question, shouldn't such a big of a typo be noticed before the problem released? Did no one notice it during the contest?