第 1121 场 Codeforces Round(Div. 2)
F
错排计算器
Deranged Calculator
Codeforces
2800
原题
← E2→

错排计算器AI (CI翻译)

Hacks are disabled on this problem.

本题禁止 Hack。AI (CI翻译)

We are excited to introduce a new language for this Codeforces round: the Deranged Calculator language (DC).

我们很高兴在本场 Codeforces 比赛中介绍一种新语言:错乱计算器语言(DC)。AI (CI翻译)

The DC language is a simplified programming language with some weird constraints. It only supports a single expression on one line and only has a single positive integer $n$ as input. The syntax of the expression is similar to that of most programming languages (in fact, the expression is valid Python), but it is very limited:

DC 语言是一种带有一些奇怪限制的简化编程语言。它只支持一行中的单个表达式,并且输入只有一个正整数 $n$。表达式的语法与大多数编程语言类似(事实上,该表达式是合法的 Python 表达式),但功能非常有限:AI (CI翻译)

  • Expressions consist of the input parameter $n$, parenthesized expressions, and calls to the round function. These are joined together by the operators +, -, *, and /.
  • Grouping with parentheses () can be used to change the order of operations, as usual.
  • The operators * and / have equal precedence and take precedence over + and -, which also have equal precedence. Operators of equal precedence are evaluated from left to right.
  • The round function takes a single expression as its argument and rounds its value to the nearest integer, rounding up when the fractional part is exactly $0.5$. (For example, round(n/(n-n-n-n)) will always evaluate to $0$, because $x/(x-x-x-x)=-\frac{1}{2}$ for a positive integer $x$. The fractional part is $0.5$, so it will be rounded up to $0$.)
  • Only the input value $n$ can be used; no numeric constants are allowed in the program.
  • All operations are performed using exact fractional arithmetic, so division does not round and can produce fractions.
  • 表达式由输入参数 $n$、加括号的表达式以及对 round 函数的调用组成。这些部分通过运算符 +、-、* 和 / 连接。
  • 可以像通常一样使用括号 () 分组,以改变运算顺序。
  • 运算符 * 和 / 具有相同的优先级,且优先于 + 和 -;后两者也具有相同的优先级。相同优先级的运算符从左到右计算。
  • round 函数接受一个表达式作为参数,并将其值四舍五入到最近的整数;当小数部分恰好为 $0.5$ 时向上取整。(例如,对于正整数 $x$,round(n/(n-n-n-n)) 的结果总是 $0$,因为 $x/(x-x-x-x)=-\frac{1}{2}$。其小数部分为 $0.5$,因此向上取整为 $0$。)
  • 只能使用输入值 $n$;程序中不允许使用数值常量。
  • 所有运算都使用精确的分数运算,因此除法不会进行取整,并且可能产生分数。
AI (CI翻译)

A derangement of $n$ numbers is a permutation of those numbers in which none of the numbers appears in its original position. For example, the derangements of the sequence $[1, 2, 3]$ are $[2, 3, 1]$ and $[3, 1, 2]$.

$n$ 个数的一个错排是这些数的一个排列,其中没有任何一个数出现在其原来的位置。例如,序列 [1, 2, 3] 的错排为 [2, 3, 1] 和 [3, 1, 2]。AI (CI翻译)

You are given a single integer $k$. Your job is to make a valid DC program that, for every integer $n$ ($2 \le n \le k$), calculates the number of derangements of the sequence $[1, 2, \ldots, n]$, when $n$ is given as input to the DC program. The length of the program should not exceed $10\,000$ characters.

给定一个整数 $k$。你的任务是构造一个有效的 DC 程序,使得对于每个整数 $n$($2 \le n \le k$),当将 $n$ 作为输入传给 DC 程序时,计算序列 [1, 2, \ldots, n] 的错排数量。程序长度不得超过 $10\,000$ 个字符。AI (CI翻译)

A local testing tool is provided to help you develop your solution. It can be found under Contest Materials.

提供了一个本地测试工具,帮助你开发解决方案。你可以在比赛资料中找到它。AI (CI翻译)

Input

输入格式

AI (CI翻译)

The only line of input contains a single integer $k$ ($k \in \{2,3,50\}$).

输入仅一行,包含一个整数 $k$($k \in \{2,3,50\}$)。AI (CI翻译)

Your DC program should output the correct number of derangements for all integers $n$ such that $2 \le n \le k$.

你的 DC 程序应当对所有满足 $2 \le n \le k$ 的整数 $n$ 输出正确的错排数量。AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output a valid DC expression on a single line. The expression should only consist of the characters round()+-*/ and the length of the expression should not exceed $10\,000$ characters.

在一行中输出一个有效的 DC 表达式。表达式只能由字符 round()+-*/ 组成,且长度不得超过 $10\,000$ 个字符。AI (CI翻译)

Your expression will be run on all integers $n$ such that $2 \le n \le k$. For each such run, the DC expression should not divide by $0$ at any time, and its value must be the number of derangements of $n$.

你的表达式将在所有满足 $2 \le n \le k$ 的整数 $n$ 上运行。对于每次运行,DC 表达式都不能在任何时刻除以 $0$,并且其值必须等于 $n$ 的错排数量。AI (CI翻译)

Note

说明

AI (CI翻译)

For the first example, n-n/n is a valid DC program that calculates $n-1$. The number of derangements for $n=2$ is $1$, so this program correctly computes the answer for $n=2$.

对于第一个样例,n-n/n 是一个计算 $n-1$ 的有效 DC 程序。$n=2$ 时,错排数量为 $1$,因此该程序能够正确计算出 $n=2$ 时的答案。AI (CI翻译)

In the second example, a slightly overcomplicated expression is used, which shows all the features of the language in action. For $n=3$, the value of the expression is: $3+\text{round}(3-3 \cdot(\frac{3}{3+3}))-3 = \text{round}(3 - \frac{3}{2}) = \text{round}(\frac{3}{2}) = \text{round}(1.5)=2$. It correctly calculates the number of derangements of the sequence $[1,2,3]$. For $n=2$ it can be verified that the value of the expression becomes $1$.

在第二个样例中,使用了一个稍微复杂一些的表达式,展示了该语言的所有特性。对于 $n=3$,该表达式的值为:$3+\text{round}(3-3 \cdot(\frac{3}{3+3}))-3 = \text{round}(3 - \frac{3}{2}) = \text{round}(\frac{3}{2}) = \text{round}(1.5)=2$。它正确计算出了序列 [1,2,3] 的错排数量。对于 $n=2$,可以验证该表达式的值为 $1$。AI (CI翻译)

样例

Input #1
2
Output #1
n-n/n
InputCopy OutputCopy
Input #2
3
Output #2
n+round(n-n*(n/(n+n)))-n
InputCopy OutputCopy
题目信息
题号
2264F
时间限制
2 s
内存限制
256 MB
标签
构造
模拟
数学

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(gpt-6.1-sol),如有出入请以原文为准。