← 返回题目列表

Codeforces · 1510/E

E. 平衡点 /\textbackslash/\textbackslash

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

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

Equilibrium Point /\textbackslash/\textbackslash - 原题 PDF 第 1 页
原题PDF第7页
可复制的 PDF 提取文本
ICPC 2020–2021, NERC – Northern Eurasia Finals, Onsite
                              St. Petersburg, Minsk, Tbilisi, Riga – April 4th, 2021
Problem E. Equilibrium Point /\/\

    Time limit:        3 seconds
    Memory limit:     512 megabytes

Consider a balanced bracket sequence s with one type of brackets: ‘(’ and ‘)’.

There is a common geometrical representation of such a sequence. Starting at the point (0, 0), you draw
a polyline, for each bracket moving along a vector (1, 1) if it is an opening bracket, and along (1, −1) if it
is a closing bracket.


                      y                                     (         )         (         (         )         )
                       2



                       1

                                                                 (3.4,0.6)

                        0        1       2       3       4       5       6 x


Consider an area between this curve and the line y = 0. It is a set of polygons. This area has its center
of mass at some point (x, y). Note that the center of mass might be outside of the area.

You are to solve the reverse problem. Given the length n and a point (x, y), find any balanced bracket
sequence of length n such that the center of mass of its geometrical representation is located at (x, y).

Input

The first line contains three numbers n, x, and y (n is an even integer, 2 ≤n ≤36; 0 < x, y < n) — the
length of the desired sequence and the coordinates of the desired center of mass.

It is guaranteed that (x, y) is the center of mass of some balanced bracket sequence of length n, with
Euclidean-distance error of no more than 10−9.

Output

Output a balanced bracket sequence with brackets ‘(’ and ‘)’ of length n such that the center of mass
of its geometrical representation is located at the point (x, y), with Euclidean-distance error of no more
than 10−7.

Example

             standard input                         standard output
 6 3.4 0.6                               ()(())





                                         Page 7 of 14