| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 6023 | ACM Puzzles |
|
| 6024 | Undetectable Tour |
|
Description
The Association of Children Machines (ACM) is planning to build up a new type of puzzle for children. All the puzzles will have dimension (3×N) and has some or all of the following pieces. Some pieces can occur more than once. Since the puzzles made by ACM are in very high demand so many other companies have released counterfeit products which look just like puzzles made by ACM.
To prevent such counterfeit products ACM has taken up a measure which they hope will help the sellers to prevent the counterfeit products in their shop. As all puzzles are initially available in a box in a solved format and a (3×N) puzzle can have zillions of solutions for larger values of N. All the puzzles from ACM factory will have only some specific solutions when sold; they will be unique and only small fractions of all possible solutions. So it is more likely that the counterfeit products won’t have these orientations. You have to help them in the initial part: given the value of N you will have to find how many different solutions are there with the given pieces. You are not allowed to rotate the pieces while solving the puzzle but you can use any piece any number of time. Of course some of the pieces are mere rotation of another but they also cannot be rotated to make it look like the other. For example the piece with shape upside down T (the brown piece) cannot be rotated to look like a normal T (the pink piece).
Input
The input file contains several lines of input. Each line contains an integer N (0
Output
For each value of N produce one line of output. This line contains the serial of output followed by an integer which denotes the value (S % 1000000000000). Here S denotes the number of solutions for a (3×N) puzzle. Look at the output for sample input for details.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Mickey is assigned a task to help the puppies to escape by travelling from the south-west corner of a grid to the north-east corner undetected by the set of motion detectors deployed by Cruella. There are k motion detectors (1<=k<=300) which are placed on the grid points and can detect any motion within a given distance, d , from the detector. Here we adopt L1 metrics for distance measurements, i.e., the distance between two points (x1, y1) and (x2, y2) is | x1 - x2| + | y1 - y2| . For example, consider the 9×9 grid in the figure below, if the detecting distance of the two detectors, marked with a solid circle, is 3, there exists a tour from (0, 0) to (8, 8) (for example the diagonal is an undetectable tour); however, if the distance is four, there would be no such tour.
Cruella decides to make it more difficult to escape by setting the detecting distance of the detectors randomly. For each grid, Cruel would flip coins to decide the detecting distance for all the detectors in that grid. Given the probability distribution of the detecting distance d and a series of grids, your task is to write a program to decide for each input grid the probability that it contains an undetectable tour.
Each grid is N×N where 3<=N<=10000 , and each grid point in the grid is denoted by a pair of integers, (x, y) , where 0<=x , y<=N - 1 . The probability distribution is specified by a sequence of ordered pair (d1, p1),(d2, p2),...,(dm, pm) where 1<=m<=100, 1<=di<=2(N - 1) , and each pi has at most three digits after the decimal point. To make it a probability distribution we also have the property that Σpi = 1 .
Input
The first line of the input file contains an integer indicating the number of test cases to follow, there will be at most 5 test cases. For each test case, the first line contains two integers, N and m separated by a space. Followed by m lines to specify the probability distribution, each line consists di, pi . Followed by k lines of the positions of detectors in the form x ,y which is the coordination of the detector. The case ends with a line containing `-1'.
Output
For each test case, output the probability that the grid contains a undetectable tour.