以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Problem I
Squares on Grid Lines
Time limit: 4 seconds
You have a square of side length n on a 2D plane, partitioned into a grid of 1 × 1 square cells, totaling n2 cells.
Your task is to answer q queries, numbered from 1 to q, described below. In query i, you are given a real number si,
and you must count the number of ways to place four points on the plane such that
• each point lies on the boundary of a cell (not necessarily the same), and
• the four points form the vertices of a square with area si.
Here, the edges of the square formed by these points do not need to be parallel to the edges of the cells. If there are
infinitely many valid placements, you must report that as your answer.
Two placements are considered different if there exists a point that appears in one placement but not in the other.
Input
The first line of input contains two integers n and q (1 ≤n ≤2000, 1 ≤q ≤100 000). The i-th of the next q lines
contains a real number si (0.01 ≤si ≤n2), given with exactly two digits after the decimal point.
Output
Output q lines. The i-th line should contain the number of valid placements for query i. If infinitely many exist, output
-1 instead.
Sample Input #1 Sample Output #1
3 4 2
6.90 4
0.26 10
2.65 -1
1.00
Explanation for the sample input/output #1
For queries 1 and 2, the valid placements are illustrated in Figure I.1. The top two placements correspond to query 1,
and the bottom four correspond to query 2. In each placement, the shaded region represents a square formed by the
points.
The 2025 ICPC Asia Pacific Championship Problem I: Squares on Grid Lines
Figure I.1: Illustrations of Sample Input #1.
Sample Input #2 Sample Output #2
1 5 0
0.49 1
0.50 2
0.51 2
0.99 1
1.00
The 2025 ICPC Asia Pacific Championship Problem I: Squares on Grid Lines