没有合适的资源?快使用搜索试试~ 我知道了~
noip2017提高组试题(day1+day2).pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 38 浏览量
2024-03-18
21:05:34
上传
评论
收藏 1.69MB PDF 举报
温馨提示
试读
15页
全国信息学奥林匹克联赛,计算机编程,论文,历届,信息技术比赛,参考资料,极具学习价值
资源推荐
资源详情
资源评论
全国信息学奥林匹克联赛(NOIP2017)复赛 提高组 day1
第 1 页共 7 页
CCF 全国信息学奥林匹克联赛(NOIP2017)复赛
提高组 day1
(请选手务必仔细阅读本页内容)
一.题目概况
中文题目名称
小凯的疑惑
时间复杂度
逛公园
英文题目与子目录名
math
complexity
park
可执行文件名
math
complexity
park
输入文件名
math.in
complexity.in
park.in
输出文件名
math.out
complexity.out
park.out
每个测试点时限
1 秒
1 秒
3 秒
测试点数目
20
10
10
每个测试点分值
5
10
10
附加样例文件
有
有
有
结果比较方式
全文比较(过滤行末空格及文末回车)
题目类型
传统
传统
传统
运行内存上限
256M
256M
512M
二.提交源程序文件名
对于 C++语言
math.cpp
complexity.cpp
park.cpp
对于 C 语言
math.c
complexity.c
park.c
对于 pascal 语言
math.pas
complexity.pas
park.pas
三.编译命令(不包含任何优化开关)
对于 C++语言
g++ -o math
math.cpp -lm
g++ -o complexity
complexity.cpp -lm
g++ -o park
park.cpp -lm
对于 C 语言
gcc -o math math.c
-lm
gcc -o complexity
complexity.c -lm
gcc -o park park.c
-lm
对于 pascal 语言
fpc math.pas
fpc complexity.pas
fpc park.pas
注意事项:
1、文件名(程序名和输入输出文件名)必须使用英文小写。
2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。
3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) II x2 240 processor,2.8GHz,
内存 4G,上述时限以此配置为准。
4、只提供 Linux 格式附加样例文件。
5、提交的程序代码文件的放置位置请参照各省的具体要求。
6、特别提醒:评测在当前最新公布的 NOI Linux 下进行,各语言的编译器版本以其为准。
全国信息学奥林匹克联赛(NOIP2017)复赛 提高组 day1
第 2 页共 7 页
1.小凯的疑惑
(math.cpp/c/pas)
【问题描述】
小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有
无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小
凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在
小凯无法准确支付的商品。
【输入格式】
输入文件名为 math.in。
输入数据仅一行,包含两个正整数 a 和 b,它们之间用一个空格隔开,表示小凯手
中金币的面值。
【输出格式】
输出文件名为 math.out。
输出文件仅一行,一个正整数 N,表示不找零的情况下,小凯用手中的金币不能准
确支付的最贵的物品的价值。
【输入输出样例 1】
math.in
math.out
3 7
11
见选手目录下的 math/math1.in 和 math/math1.ans。
【输入输出样例 1 说明】
小凯手中有面值为 3 和 7 的金币无数个,在不找零的前提下无法准确支付价值为 1、
2、4、5、8、11 的物品,其中最贵的物品价值为 11,比 11 贵的物品都能买到,比如:
12 = 3 * 4 + 7 * 0
13 = 3 * 2 + 7 * 1
14 = 3 * 0 + 7 * 2
15 = 3 * 5 + 7 * 0
……
【输入输出样例 2】
见选手目录下的 math/math2.in 和 math/math2.ans。
【数据规模与约定】
对于 30%的数据: 1 ≤ a,b ≤ 50。
对于 60%的数据: 1 ≤ a,b ≤ 10,000。
对于 100%的数据:1 ≤ a,b ≤ 1,000,000,000。
全国信息学奥林匹克联赛(NOIP2017)复赛 提高组 day1
第 3 页共 7 页
2.时间复杂度
(complexity.cpp/c/pas)
【问题描述】
小明正在学习一种新的编程语言 A++,刚学会循环语句的他激动地写了好多程序并
给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序,
于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是
否正确。
A++语言的循环结构如下:
其中“F i x y”表示新建变量 i(变量 i 不可与未被销毁的变量重名)并初始化为 x,
然后判断 i 和 y 的大小关系,若 i 小于等于 y 则进入循环,否则不进入。每次循环结束
后 i 都会被修改成 i +1,一旦 i 大于 y 终止循环。
x 和 y 可以是正整数(x 和 y 的大小关系不定)或变量 n。n 是一个表示数据规模的
变量,在时间复杂度计算中需保留该变量而不能将其视为常数,该数
远大于
100。
“E”表示循环体结束。循环体结束时,这个循环体新建的变量也被销毁。
注:本题中为了书写方便,在描述复杂度时,使用大写英文字母“O”表示通常意
义下“Θ”的概念。
【输入格式】
输入文件名为 complexity.in。
输入文件第一行一个正整数 t,表示有 t(t ≤ 10)个程序需要计算时间复杂度。
每个程序我们只需抽取其中 “F i x y”和“E”即可计算时间复杂度。注意:循环结构
允许嵌套。
接下来每个程序的第一行包含一个正整数 L 和一个字符串,L 代表程序行数,字符
串表示这个程序的复杂度,“O(1)”表示常数复杂度,“O(n^w)”表示复杂度为𝑛
𝑤
,其
中 w是一个小于100 的正整数(输入中不包含引号),输入保证复杂度只有O(1)和 O(n^w)
两种类型。
接下来 L 行代表程序中循环结构中的“F i x y”或者 “E”。
程序行若以“F”开头,表示进入一个循环,之后有空格分离的三个字符(串)i x y,
其中 i 是一个小写字母(保证不为“n”),表示新建的变量名,x 和 y 可能是正整数或
n ,已知若为正整数则一定小于 100。
程序行若以“E”开头,则表示循环体结束。
【输出格式】
输出文件名为 complexity.out。
输出文件共 t 行,对应输入的 t 个程序,每行输出“Yes”或“No”或者“ERR”(输
出中不包含引号),若程序实际复杂度与输入给出的复杂度一致则输出“Yes”,不一致
则输出“No”,若程序有语法错误(其中语法错误只有: ① F 和 E 不匹配 ②新建的变
量与已经存在但未被销毁的变量重复两种情况),则输出“ERR”。
注意:即使在程序不会执行的循环体中出现了语法错误也会编译错误, 要输出
“ERR”。
F i x y
循环体
E
剩余14页未读,继续阅读
资源评论
阿拉伯梳子
- 粉丝: 1164
- 资源: 5391
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功