#P98. 【集训队互测2015】未来程序·改

【集训队互测2015】未来程序·改

在 2111 年，第 128 届全国青少年信息学奥林匹克冬令营前夕，Z君找到了 2015 年，第 32 届冬令营的题目来练习。

他打开了第三题 “未来程序” 这道题目：

“本题是一道提交答案题，一共 10 个测试点。

对于每个测试点，你会得到一段程序的源代码和这段程序的输入。你要运行这个程序，并保存这个程序的输出。

遗憾的是这些程序都效率极其低下，无法在比赛的 5 个小时内得到输出。”

Z君想了一下，决定用 2111 年的计算机来试着运行这个题目，但是问题来了，Z君已经找不到 96 年前的那次比赛的测试数据了……

没有给出输入数据的提交答案题就不成其“提交答案题”之名，为了解决这个问题，Z君决定将这个题目改造成传统题。

Z君知道 96 年前的计算机的性能比现在差多了，所以这道题的测试数据中，输入数据的规模被设计成很小，从而，做这道题的选手只需要暴力模拟源代码的工作流程就可以通过它。

现在这道题摆到了你的面前。

本题是一道传统题，一共有 10 个测试点。

对于每个测试点，你的程序会得到一段程序的源代码和这段程序的输入。你的程序需要运行这段程序，并输出这段程序的输出。

关于给出的源代码的约定

Z君是一名C++选手。为了简化这个问题，Z君在给出的源代码中去掉了C++语言的大量特性。从而这个源代码具有以下特点：

  • 第一行必定为 “<samp>#include<iostream></samp>” （不含引号）
    • 这个库中只会调用到对象 <samp>cin</samp>，<samp>cout</samp>，<samp>endl</samp>，<samp>cin</samp> 的 <samp>>>(int)</samp> 函数和 <samp>cout</samp> 的 <samp><<(int)</samp> 函数。这两个函数分别用于输入和输出一个整数，返回值分别 <samp>cin</samp> 和 <samp>cout</samp>。
  • 第二行必定为 “<samp>#include<cstdio></samp>” （不含引号）
    • 这个库中只会调用到 <samp>putchar</samp> 函数。<samp>putchar(c)</samp> 会输出 ASCII 码为 $c$ 的字符，并返回 $c$。
  • 第三行必定为 “<samp>using namespace std;</samp>” （不含引号）
    • 对象 <samp>cin</samp> 的调用不再需要通过 <samp>std::cin</samp> 进行，<samp>cout</samp> 和 <samp>endl</samp> 同理。
  • <samp>int main()</samp> 没有任何参数。
  • 所有的变量都是 <samp>int</samp> 或 <samp>int</samp> 数组（含高维数组）类型。
    • 对象 <samp>cin</samp>, <samp>cout</samp>, <samp>endl</samp> 是例外，注意 <samp>putchar</samp> 的参数也是int类型的。我们保证在运行时这个参数的值在 $0 \sim 127$ 中。
    • 在运行时，不会出现数组越界问题。
    • 没有维度的范围为 $1$。也即，不会出现 <samp>int a[1][1][1][1][1];</samp> 这样的情况。
    • 维度的范围直接由十进制常量给出。也即，不会出现 <samp>int a[(100+100)*2];</samp> 这样的情况。
  • 所有的函数都是 <samp>int</samp> 类型，函数的参数只可能是 <samp>int</samp> 类型
    • 注意函数的返回值可以被丢弃。
    • 当没有显式地返回值时，返回 $0$。
  • <samp>bool</samp> 型被认为是一种特殊的 <samp>int</samp> 型
    • <samp>==</samp> 在两个参数相同时返回 $1$，否则返回 $0$。
    • <samp>!=</samp> 在两个参数相同时返回 $0$，否则返回 $1$。
    • <samp><</samp> 在第一个参数小于第二个参数时返回 $1$，否则返回 $0$。
    • <samp><=</samp> 在第一个参数小于等于第二个参数时返回 $1$，否则返回 $0$。
    • <samp>></samp> 在第一个参数大于第二个参数时返回 $1$，否则返回 $0$。
    • <samp>>=</samp> 在第一个参数大于等于第二个参数时返回 $1$，否则返回 $0$。
    • <samp>&&</samp> 在两个参数都不为 $0$ 时返回 $1$，否则返回0。
    • <samp>||</samp> 在两个参数都为 $0$ 时返回 $0$，否则返回 $1$。
    • <samp>^</samp> 在两个参数中只有一个为 $0$ 时返回 $1$，其他时候返回 $0$。
    • <samp>!</samp> 在参数为 $0$ 时返回 $1$，否则返回 $0$。
    • 由于 <samp>bool</samp> 型被 <samp>int</samp> 型取代了，因此所有的表达式都应该被完全计算：例如在表达式 <samp>(a && (b = c))</samp>中，即使 <samp>a</samp> 已经被确定是 $0$，仍然需要计算 <samp>(b = c)</samp> 的值，尽管无论 <samp>(b = c)</samp> 的值如何，整个表达式的值都是 $0$。
  • 可能用到的运算符及其优先级如下：（从高到低排列）
    1. <samp>()</samp>, <samp>[]</samp>
    2. <samp>!</samp>, <samp>+</samp>（正号）, <samp>-</samp>（负号）
    3. <samp>*</samp>, <samp>/</samp>, <samp>%</samp>
    4. <samp>+</samp>（加法）, <samp>-</samp>（减法）
    5. <samp><=</samp>, <samp>>=</samp>, <samp><</samp>, <samp>></samp>
    6. <samp>==</samp>, <samp>!=</samp>
    7. <samp>^</samp>
    8. <samp>&&</samp>
    9. <samp>||</samp>
    10. <samp>=</samp>
    11. <samp>cout</samp> 的 <samp><<</samp> 与 <samp>cin</samp> 的 <samp>>></samp>。
  • 所有 <samp>int</samp> 常量以十进制形式给出
  • Z君没有对源代码进行混淆，所以源代码是可读的，你不必担心出现大量嵌套的花括号或此类的“垃圾代码”
  • 运行时使用的变量占用的空间的峰值不超过 $8\texttt{MB}$。也即，$2^{21}$ 个 <samp>int</samp>
  • 调用函数的深度不会超过 $10^3$ 层
  • 可能出现连续赋值，例如 <samp>a = (b = (c = 3) + 2) % c</samp>
    • 之前对 <samp>c</samp> 的赋值将会反映到之后对 <samp>c</samp> 的引用上
    • <samp>=</samp> 是右结合的，<samp>a = b = c</samp> 会被看作 <samp>a = (b = c)</samp>
    • 赋值的返回值为赋值以后的值
  • 可能出现的程序流程控制语句：
    • <samp>if (statement) statement [else statement]</samp>
    • <samp>while (statement) statement</samp>
    • <samp>for ([statement]; [statement]; [statement]) statement</samp>
    • 那些作为条件的 <samp>statement</samp> 的返回值应当被视为 <samp>bool</samp> 型的。具体的来说，若返回值为 $0$，则为 <samp>false</samp>，若返回值非 $0$，则为 <samp>true</samp>。在 <samp>for</samp> 循环中，当第二个 <samp>[statement]</samp> 取空时，视为 <samp>true</samp>。
  • 空白字符只有新行符（即 <samp>\n</samp>）和空格。
  • 声明变量时默认初始值为 $0$，声明变量的同时不会进行赋值。
  • 没有注释
  • 所有的右花括号后没有分号
  • 没有用来连接语句的逗号
  • 没有函数和变量重名

输入格式

输入文件分为两个部分。

第一行，有一个整数 $N$。它描述了源代码对应的输入文件 <samp>program.in</samp> 中包含的整数数目。

以下 $N$ 个整数构成了源代码对应的输入文件 <samp>program.in</samp>。

这之后的部分构成了源代码 <samp>program.cpp</samp>。

输出格式

输出文件是将 <samp>program.cpp</samp> 编译后输入 <samp>program.in</samp> 后所得到的输出。

2
1 2
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{int a, b; cin >> a >> b; cout << a + b << endl;}

3

10
9
6 1 7 5 1 7 2 2 4
#include<iostream>
#include<cstdio>
using namespace std;
int n, a[100];


int main()
{
    cin >> n;
    int i, j, this_VARIABLE_is_NOT_used;
    for (i = 1; i <= n; i = i + 1) cin >> a[i];
    for (i = 1; i <= n; i = i + 1)
    for (j = i + 1; j <= n; j = j + 1)
    if (a[i] > a[j])
    {
        int t;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    for (i = 1; i <= n; i = i + 1)
    {
        cout << a[i];
        if (i == n) cout << endl; else putchar(32);
    }
    return 0;
}

1 1 2 2 4 5 6 7 7

限制与约定

输入的所有 <samp>program.cpp</samp> 都是手打的，每个输入文件的大小不超过 $7\texttt{KB}$。

测试点#1的 <samp>program.cpp</samp> 见样例数据及附加文件下载。

测试点#2到#4的 <samp>program.cpp</samp> 符合以下格式：

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    cout << <1> << endl;
}

在#2中：<samp><1></samp> 处是一个仅包含加、减、乘、除、模运算和自然数常数的没有括号的表达式。

在#3和#4中：<samp><1></samp> 处是一个不保证以上性质的表达式。

测试点#5中：没有除 <samp>main</samp> 以外的函数，并且整个程序中只有顺序结构。

测试点#6和#7中：没有除 <samp>main</samp> 以外的函数。

测试点#8中：所有的变量都是全局变量。

测试点#9和#10不保证任何特别的性质。

所有 <samp>program.cpp</samp> 都可以用 MinGW GCC 4.7.2 编译运行。这就是说，所有的 <samp>program.cpp</samp> 中都没有语法错误。然而由于编译命令的不同，直接编译得到的 <samp>program.exe</samp> 在运行时有可能会因未为声明的变量和未设置返回值的函数设置 $0$ 的缺省值以及 <samp>bool</samp> 类型的处理方式不同而与标程产生不同的输出。

为了更准确地说明程序可能出现的要素，也作为提示，下面给出了一个上下文无关文法，其初始符号为 <samp>PROGRAM</samp>。保证每个 <samp>program.cpp</samp> 都可被下面的文法生成，但是并非每个可被生成的程序都是合法的程序。

PROGRAM ::= # include < iostream > # include < cstdio > using namespace std ; FUNC_AND_VAR

FUNC_AND_VAR ::=
| ε
| int NAME ( OPTPARAMS ) { STATEMENTS } FUNC_AND_VAR
| int DEFINEVAR DEFINEVARS ; FUNC_AND_VAR


OPTPARAMS ::=
| ε
| int NAME PARAMS


PARAMS ::=
| ε
| , int NAME PARAMS


STATEMENTS ::=
| ε
| STATEMENT STATEMENTS


STATEMENT ::=
| EXPRESSION ;
| { STATEMENTS }
| int DEFINEVAR DEFINEVARS ;
| if ( EXPRESSION ) STATEMENT
| if ( EXPRESSION ) STATEMENT else STATEMENT
| for ( STATEMENT_IN_FOR ; OPTEXPRESSION ; STATEMENT_IN_FOR ) STATEMENT
| while ( EXPRESSION ) STATEMENT
| return EXPRESSION ;


STATEMENT_IN_FOR ::=
| OPTEXPRESSION
| int DEFINEVAR DEFINEVARS


OPTEXPRESSION ::=
| ε
| EXPRESSION


EXPRESSION ::=
| UNIT9
| EXPRESSION << UNIT9
| EXPRESSION >> UNIT9


UNIT0 ::=
| INT_CONSTANT
| UNIT0 [ EXPRESSION ]
| ( EXPRESSION )
| NAME ( OPTARGUS )    // 注：此处的 NAME 是一个函数名
| NAME    // 注：此处的 NAME 是一个变量名
| cin
| cout
| endl


UNIT1 ::=
| UNIT0
| + UNIT1
| - UNIT1
| ! UNIT1


UNIT2 ::=
| UNIT1
| UNIT2 * UNIT1
| UNIT2 / UNIT1
| UNIT2 % UNIT1


UNIT3 ::=
| UNIT2
| UNIT3 + UNIT2
| UNIT3 - UNIT2


UNIT4 ::=
| UNIT3
| UNIT4 < UNIT3
| UNIT4 <= UNIT3
| UNIT4 > UNIT3
| UNIT4 >= UNIT3


UNIT5 ::=
| UNIT4
| UNIT5 == UNIT4
| UNIT5 != UNIT4


UNIT6 ::=
| UNIT5
| UNIT6 ^ UNIT5


UNIT7 ::=
| UNIT6
| UNIT7 && UNIT6


UNIT8 ::=
| UNIT7
| UNIT8 || UNIT7


UNIT9 ::=
| UNIT8
| UNIT8 = UNIT9


OPTARGUS ::=
| ε
| EXPRESSION ARGUS


ARGUS ::=
| ε
| , EXPRESSION ARGUS


DEFINEVARS ::=
| ε
| , DEFINEVAR DEFINEVARS


DEFINEVAR ::=
| NAME
| DEFINEVAR [ INT_CONSTANT ]


NAME ::= 仅包含大小写字母、数字、下划线的非空字符串，且不以数字开头。


INT_CONSTANT ::= 仅包含数字的非空字符串，且不以0开头，或这个字符串就是0。
</p>

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

来源

中国国家集训队互测2015 - By 卢啸尘

下载

样例数据及附加文件下载

统计

  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  7. 兼容模式
  8. 主题
  2. © 2021-2024 Hydro.ac
  4. Worker 0 in 42ms
  5. Hydro v4.11.2 Professional