시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB64292746.552%

문제

Some pranksters have watched too much Discovery Channel and now they want to build a crop triangle during the night. They want to build it inside a large crop that looks like an evenly spaced grid from above. There are some trees planted on the field. Each tree is situated on an intersection of two grid lines (a grid point). The pranksters want the vertices of their crop triangle to be located at these trees. Also, for their crop triangle to be more interesting they want the center of that triangle to be located at some grid point as well. We remind you that if a triangle has the vertices (x1, y1), (x2, y2) and (x3, y3), then the center for this triangle will have the coordinates ((x1 + x2 + x3) / 3, (y1 + y2 + y3) / 3).

You will be given a set of points with integer coordinates giving the location of all the trees on the grid. You are asked to compute how many triangles you can form with distinctvertexes in this set of points so that their center is a grid point as well (i.e. the center has integer coordinates). 

If a triangle has area 0 we will still consider it a valid triangle.

입력

The first line of input gives the number of cases, NN test cases follow. Each test case consists of one line containing the integers nABCDx0y0 and M separated by exactly one space. n will be the number of trees in the input set. Using the numbers nABCDx0y0 and M the following pseudocode will print the coordinates of the trees in the input set. mod indicates the remainder operation.

The parameters will be chosen such that the input set of trees will not have duplicates.

X = x0, Y = y0
print X, Y
for i = 1 to n-1
  X = (A * X + B) mod M
  Y = (C * Y + D) mod M
  print X, Y

Limits

  • 1 <= N <= 10, 
  • 0 <= ABCDx0y0<= 109
  • 1 <= M <= 109.
  • 3 <= n <= 100000.

출력

For each test case, output one line containing "Case #X: " where X is the test case number (starting from 1). This should be followed by an integer indicating the number of triangles which can be located at 3 distinct trees and has a center that is a grid point.

예제 입력 1

2
4 10 7 1 2 0 1 20
6 2 0 2 1 1 2 11

예제 출력 1

Case #1: 1
Case #2: 2

힌트

In the first test case, the 4 trees in the generated input set are (0, 1), (7, 3), (17, 5), (17, 7).

출처

Contest > Google > Code Jam > Google Code Jam 2008 > Round 1B A2번

채점 및 기타 정보

  • 예제는 채점하지 않는다.