← 返回题目列表

Codeforces · 2052/L

L. 旧版屏幕保护程序

中文机器翻译题面 查看原题

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

Legacy Screensaver - 原题 PDF 第 1 页
原题PDF第16页
Legacy Screensaver - 原题 PDF 第 2 页
原题PDF第17页
可复制的 PDF 提取文本
ICPC 2024–2025, NERC – Northern Eurasia Finals
                        St. Petersburg, Novosibirsk, Astana, Tbilisi, December 15th, 2024
Problem L. Legacy Screensaver

    Time limit:        3 seconds
    Memory limit:     1024 megabytes

On a very old operating system, a screensaver consists of two rectangles flying around the screen. The
screen is W pixels wide and H pixels high. Consider the origin to be in the top-left corner of the screen,
the x-axis to go from the origin to the right, and the y-axis to go from the origin to the bottom.

Rectangle i (i = 1, 2) has a width of wi pixels, a height of hi pixels, initially its top-left corner has
coordinates (xi, yi), and its initial movement direction is (δxi, δyi), where each of δxi and δyi is either −1
or 1. At the end of each second, rectangle i’s top-left corner coordinates instantly change by (δxi, δyi).

Whenever rectangle i touches the left or the right border of the screen, the value of δxi changes sign before
the next second. Similarly, whenever rectangle i touches the top or the bottom border of the screen, the
value of δyi changes sign before the next second. Whenever rectangle i touches two borders of the screen
at the same time (which can only happen at the corner of the screen), both δxi and δyi change sign.

As a result of the above, both rectangles stay fully within the screen at all times. Informally, collisions
of the rectangles with the screen borders are perfectly elastic. Note, however, that rectangle movement is
still discrete: each rectangle moves instantly by 1 pixel in both directions at the end of each second.

You are curious how often these two rectangles overlap. The rectangles are considered to be overlapping
if their intersection has a positive area.

Let f(t) be the number of integers τ = 0, 1, . . . , t −1 such that the rectangles overlap during second τ
(where second 0 is before the rectangles start moving).

                        f(t)
Find the limit of     as t →∞as an irreducible fraction. It can be shown that this limit is a rational                              t
number.

Input

Each test contains multiple test cases. The first line contains the number of test cases T (1 ≤T ≤1000).
The description of the test cases follows.

The first line of each test case contains two integers W and H, denoting the width and the height of the
screen (3 ≤W, H ≤4000).

The next two lines describe the two rectangles. Each rectangle is described by six integers wi, hi, xi, yi,
δxi, δyi, describing the i-th rectangle and denoting its width, its height, the coordinates of its top-left
corner, and its initial movement direction (1 ≤wi ≤W −2; 1 ≤hi ≤H −2; 0 < xi < W −wi;
0 < yi < H −hi; δxi, δyi ∈{−1, 1}).

The sum of the values of W + H across all test cases is guaranteed to not exceed 8000.

Output

For each test case, print a non-negative integer p and a positive integer q, separated by a slash (‘/’)
                                                       f(t)                         p
without spaces, meaning that the limit of     as t →∞is equal to   The fraction must be irreducible —                                                                   t                           q.
that is, the greatest common divisor of p and q must be equal to 1.

Example

             standard input                          standard output
 2                                       1/2
 3 3                                     1/3
 1 1 1 1 1 1
 1 1 1 1 1 -1
 5 4
 2 2 1 1 -1 -1
 2 1 2 2 1 -1


                                        Page 16 of 19

ICPC 2024–2025, NERC – Northern Eurasia Finals
                        St. Petersburg, Novosibirsk, Astana, Tbilisi, December 15th, 2024

Note

For the second test case, the state of rectangles during the first few seconds is shown in the following
pictures. The rectangles overlap during seconds τ = 0 and τ = 6. Thus, for example, f(8) = 2.


                            τ = 0                                    τ = 1

               0    1    2    3    4    5   x          0    1    2    3    4    5   x


               1                                      1

               2                                      2

               3                                      3

               4                                      4

              y                                    y


                            τ = 2                                    τ = 3

               0    1    2    3    4    5   x          0    1    2    3    4    5   x


               1                                      1

               2                                      2

               3                                      3

               4                                      4

              y                                    y


                            τ = 4                                    τ = 5

               0    1    2    3    4    5   x          0    1    2    3    4    5   x


               1                                      1

               2                                      2

               3                                      3

               4                                      4

              y                                    y


                            τ = 6                                    τ = 7

               0    1    2    3    4    5   x          0    1    2    3    4    5   x


               1                                      1

               2                                      2

               3                                      3

               4                                      4

              y                                    y



                                        Page 17 of 19