错排计算器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 theroundfunction. 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
roundfunction 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$;程序中不允许使用数值常量。 - 所有运算都使用精确的分数运算,因此除法不会进行取整,并且可能产生分数。
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翻译)
样例
2
n-n/n
3
n+round(n-n*(n/(n+n)))-n
题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(gpt-6.1-sol),如有出入请以原文为准。