VPL1_AE - Winter Crush

Winter is a sad season, specially if you have nobody to share your time with. Valentine’s day is coming and Dickie is crushed for Elizabeth, but she has already friendzoned him with the classic “You’re my best friend” and other silly phrases used by girls in order to keep the “friend” neutralized but at the same time, keep him close.

Nevertheless, Dickie ain’t gonna to take any more stools. He’s thinking about an ultimate move to gain Elizabeth heart! He has called this ”No more stools operation!”, and will take place on Valentine’s day. He hasn’t clearly decided what to do, because that heavily depends on Elizabeth’s position on Valentine’s day. Even so, Dickie has been smart enough to figured out a way to know Elizabeth’s position in terms of probability based on the time elapsed from the beginning of the day.

As Elizabeth’s “best friend”, Dickie knows her preferences and tastes. He knows that if she’s at a given position x, she will move to any adjacent position y with a probability pxy depending on the joy attained going there and the amount of snow on the path. The joy jxy is being measured in joysons and the snow sxy by centimeters, and the choice will be taken by the relation jxy / sxy. Some properties shall hold:

  • The set of all positions is to be named V.
  • For any given x ∈ V, the set of all positions y ∈ V adjacent to x is to be named Ex. A position y is to be called adjacent if there is a path from x to y. Paths are bidirectional, so jxy/sxy = jyx/syx.
  • ∀x ∈ V ∧ ∀y ∈ Ex:

Dickie has some places in mind where he can find Elizabeth, but he’s aware that she could depart that morning from either her house or any of hers friends’ houses, so he wants to know which is the position with the highest probability to find Elizabeth given an elapsed time and the position she’s departing. Dickie wants to evaluate several possible scenarios, so a query will be formed by a time Ti and several possible initial positions Pi.

Input

The first line contains an integer C, which specifies the number of test cases. Then, will follow the descriptions of C test cases.

Each case will start with two integers, N and M, denoting the number of positions and the number of paths respectively. Next M will describe each of the paths between positions with four integers x, y, jxy, sxy, with the significance given above in the statement. All position indexes are 0-based. The line M + 1 will contain an integer Q denoting the number of Dickie’s queries. Each query will start with two integers, Ti and qi denoting the elapsed time and the number Elizabeth’s possible starting positions. Next qi lines will contain an integer will represent Elizabeth’s starting positions Pi.

Output

For each test case you should print the string "Scenario #i:" where i represents the test case you are analyzing (starting from 1), followed by a blank line. For each query Qi in the input, you must output a line with qi integers representing the position with the highest probability to find Elizabeth given the elapsed time Ti and the starting position Pi of her. If there are several positions with the highest probability, print the smallest one. If there are no positions with higher probability than 0, print -1.

Sample

Input:
2
3 3
0 1 10 2
0 2 1 8
1 2 100 1
2
1 1 0
2 1 0
4 5
0 1 10 2
1 3 2 3
0 2 4 8
2 1 1 10
2 3 1 1
2
2 1 2
10 2 0 3

Output:
Scenario #1:

1
2

Scenario #2:

1
0 0

Constraints

  • 0 < jxy, sxy ≤ 100
  • 0 ≤ M ≤ (N * (N - 1)) / 2

Subtask 1 (30%)

  • 1 ≤ C ≤ 50
  • 1 ≤ N ≤ 20
  • 0 ≤ | Ex | ≤ 3, ∀ x ∈ V
  • 1 ≤ Ti ≤ 20
  • 1 ≤ Q ≤ 10
  • qi = 1
  • 0 ≤ Pi ≤ N

Subtask 2 (70%)

  • 1 ≤ C ≤ 20
  • 1 ≤ N ≤ 100
  • 1 ≤ Q ≤ 10
  • 2 ≤ Ti ≤ 2000
  • 1 ≤ qi ≤ 100
  • 0 ≤ Pi ≤ N 

Added by:Venezuelan Programming League
Date:2013-03-08
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-11-07 01:33:39 Federico Lebrón
@Daniel:

About 3), so for all x, \sum_{y \in E_x} p_{x, y} = 1, except when E_x = {}? It is possible, then, for E_x = {}? If Elizabeth starts at such an x, where does she move to? Does she always stay at x, making p_{x, x} = 1?

EDIT: After AC, it seems the rule is:

For all x in V, \sum_{y in E_x} p_{x, y} = 1, except when E_x = {}. In that case, if Elizabeth starts there, one needs to output -1. She moves nowhere - she instantly disappears.

Last edit: 2013-07-17 07:56:53
2014-11-07 01:33:39 Daniel Ampuero
I've already added the following:
"Paths are bidirectional, so jxy/sxy = jyx/syx."

In the other hand, some other clarifications:
1- If there's no incidence on some vertex, then all its edges are pxy=0.
2- Please ignore the p_xy = p_yx indication, it should not be there.
3- \sum_{p_{x, y}} p_i = 1 idicates that the sum of probabilities over Ex is 1. If Ex is empty, then it sums 0.
2014-11-07 01:33:39 Mitch Schwartz
The problem is poorly written, to the point of being unintelligible. I can almost make sense of it with several guesses of the form "the author wrote X, but meant Y", but even then it's entirely unclear what should happen if the starting vertex does not have any incident edges. @problem setter: Please respond, or the problem may be hidden.
2014-11-07 01:33:39 Federico Lebrón
You say E_x is the set of y in V adjacent to x. What does it mean to be adjacent? The input doesn't say when x is adjacent to y. The input speaks of some number of "paths". If there is a path from x to y, is x adjacent to y? Is y then adjacent to x? Is j_{x ,y} = j_{y, x}? Is s_{x, y} = s_{y, x}?

p_{x, y} is defined using j_{x, y} and s_{x, y}, but the input does not say what j_{x, y} is for, for example, x = 2, y = 1. Is it the same as j_{1, 2}?

In general, how will we know what j_{x, y} and s_{x, y} is? Will it always be true that (j_{x, y} == j_{y, x}, s_{x, y} == s_{y, x}), and at least one of {j_{x, y}, j_{y, x}} and one of {s_{x, y}, s_{y, x}} are given in the input? Will we ever be given BOTH s_{x, y} and s_{y, x}, or j_{x, y} and j_{y, x}? If so, are we guaranteed that they match? What if they do not?

In the first example, do you mean that E_0 = {1, 2}, E_1 = {2}, E_2 = {}, p_{0, 1} = 40/41, p_{0, 2} = 1/41, p_{0, 0} = 0? What is p_{1, 0}, p_{1, 2}, p_{2, 0}, p_{2, 1}, and p_{2, 2}? Could you explain it?


I guess I've no idea how we're supposed to find p_{x, y}, with the information given in the input. Indeed, without further clarification, p_{x, y} is not well defined. Suppose M = 0, so we have not a single j_{x, y} or s_{x, y}. p_{x, y} could be a number of different things, and the answers would be different. Could you explain how to obtain E_x and p_{x, y}, given the input?

Also, what does the second equation mean? \sum_{p_{x, y}} p_i = 1???

Last edit: 2013-07-16 20:24:54
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.