「CodeForces 476A」Dreamoon and Stairs
Dreamoon and Stairs
题意翻译
题面 DM小朋友想要上一个有 \(n\) 级台阶的楼梯。他每一步可以上 \(1\) 或 \(2\) 级台阶。假设他走上这个台阶一共用了 \(x\) 步。现在DM想知道 \(x\) 是否可能为 \(m\) 的倍数。如果可能,输出 \(x\) 的最小值。如果不可能,输出 \(-1\)
输入 两个正整数 \(n,m (n \le 10000,m \le 10)\)
输出 按要求输出 \(x\) 或 \(-1\)
题目描述
Dreamoon wants to climb up a stair of nn steps. He can climb \(1\) or \(2\) steps at each move. Dreamoon wants the number of moves to be a multiple of an integer \(m\) .
What is the minimal number of moves making him climb to the top of the stairs that satisfies his condition?
输入输出格式
输入格式:
The single line contains two space separated integers \(n\) , \(m\) (\(0<n \le 10000,1<m \le 10\)).
输出格式:
Print a single integer — the minimal number of moves being a multiple of \(m\) . If there is no way he can climb satisfying condition print \(-1\) instead.
输入输出样例
输入样例#1:
10 2
输出样例#1:
6
输入样例#2:
3 5
输出样例#2:
-1
说明
For the first sample, Dreamoon could climb in 6 moves with following sequence of steps: {2, 2, 2, 2, 1, 1}.
For the second sample, there are only three valid sequence of steps {2, 1}, {1, 2}, {1, 1, 1} with 2, 2, and 3 steps respectively. All these numbers are not multiples of 5.
一句话题意
给定一个n级的台阶,开始时在第0级,每次可以向上爬1级或2级,问最少要爬多次才能爬到顶,而且爬的次数是m的倍数。
思路
很明显,爬完这个台阶的最多步数是n(每次爬1层),最少步数 \(\frac{n - 1}2 + 1\) (等价于 \(\frac n2 + n \% 2\)) (每次爬2层,如果层数是奇数,那再爬1层),并且在( \(\frac{n - 1}2 + 1\) ) ~ n 之间都可以到达。
所以只要选取( \(\frac{n - 1}2 + 1\) ) ~ n 之间最小的能被m整除的数即可。
当然,这道题还可以用DP解决,那比较费时间,比较费空间,也比较难调试(谁愿意呢),所以这里不再赘述。
代码
下面给出两种写法——
写法一
比较保险的O(\(\frac nm\))算法(我模拟赛时就用这种的)
#include<cstdio>
using namespace std;
int n, m;
int ans;
int main(){
scanf( "%d%d", &n, &m );
while( ans < n / 2 + n % 2 ) ans += m;
if ( ans > n ) ans = -1;
printf( "%d\n", ans );
return 0;
}
写法二
比较有风险的O(1)算法(就怕出错,有hack数据的请联系我)
#include<cstdio>
using namespace std;
int n, m;
int ans;
int main(){
scanf( "%d%d", &n, &m );
i if ( n == 0 ) printf( "0\n" );
ans = ( ( n / 2 + n % 2 - 1 ) / m + 1 ) * m;
if ( ans == 0 || ans > n ) ans = -1;
printf( "%d\n", ans );
return 0;
}
最新文章
- jquery 监听radio选中,取值
- 【Java】深入理解ThreadLocal
- Delphi初学者应小心的六大陷阱
- 【ruby on rail 项目之 VPS下载机】
- JDK1.5新特性(四)&hellip;&hellip;Autoboxing/Unboxing
- 求最小生成树(Prim算法)(1075)
- oracle监听服务开启
- hadoop备战:一台x86计算机搭建hadoop的全分布式集群
- Apache 日志配置,包含过滤配置
- 三、nginx301跳转302跳转
- HDU 6033 Add More Zero (数学)
- CentOS文件权限管理
- PHP基础(2)
- CF633G
- C# ENUM 字符串输出功能
- [Java练习题] -- 1. 使用java打印杨辉三角
- English trip V1 - 24. Accommodations Teacher:Maple Key: make suggestions 提出建议
- Verilog 加法器和减法器(6)
- 【Smali】Smali文件的动态调试
- 关于Unity中Mesh网格的详解