CSP-J 2023 复赛第1题:小苹果

2024-02-21 04:52
文章标签 2023 csp 复赛 小苹果

本文主要是介绍CSP-J 2023 复赛第1题:小苹果,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目来源】
https://www.luogu.com.cn/problem/P9748
https://www.acwing.com/problem/content/5310/

【题目描述】
小 Y 的桌子上放着 n 个苹果从左到右排成一列,编号为从 1 到 n。
小苞是小 Y 的好朋友,每天她都会从中拿走
一些苹果。
每天在拿的时候,小苞都是从左侧第 1 个苹果开始、每隔 2 个苹果拿走 1 个苹果。
随后小苞会将剩下的苹果按原先的顺序重新排成一列。
小苞想知道,多少天能拿完所有的苹果,而编号为 n 的苹果是在第几天被拿走的?

【输入格式】
输入的第一行包含一个正整数 n,表示苹果的总数。

【输出格式】
输出一行包含两个正整数,两个整数之间由一个空格隔开,分别表示小苞拿走所有苹果所需的天数以及拿走编号为 n 的苹果是在第几天。

【数据范围】
对于所有测试数据有:1≤n≤10^9。

测试点n≤特殊性质
1∼210
3∼510^3
6∼710^6
8∼910^6
1010^9

特殊性质:小苞第一天就取走编号为 n 的苹果。

【输入样例】
8

【输出样例】
5 5

【样例解释】
小苞的桌上一共放了 8 个苹果。
小苞第一天拿走了编号为 1、4、7 的苹果。
小苞第二天拿走了编号为 2、6 的苹果。
小苞第三天拿走了编号为 3 的苹果。
小苞第四天拿走了编号为 5 的苹果。
小苞第五天拿走了编号为 8 的苹果。

【算法分析】
● 由于数据规模为 10^9,所以一个一个枚举拿走的苹果必然会超时。不过可考虑一天一天枚举拿走的苹果。
● 可推算出每天拿走的苹果数为 ceil(n/3),即每天拿走
(n+2)/3 个苹果,拿完后剩余 n-ceil(n/3) 个苹果。如果 n%3==1,那么第 n 个苹果此轮会被拿走。其中,ceil() 为 C++ 中的向上取整函数。而 floor() 为 C++ 中的向下取整函数。

【算法代码】

#include <bits/stdc++.h>
using namespace std;int days,cnt;
int main() {int n;cin>>n;while(n) {days++;if(cnt==0 && n%3==1) cnt=days;n-=(n+2)/3;}cout<<days<<" "<<cnt;return 0;
}/*
in:8
out:5 5
*/




【参考文献】
https://www.acwing.com/solution/content/220247/
https://blog.csdn.net/m0_59925573/article/details/136106743
https://mp.weixin.qq.com/s/zckJsihxsDT2JNBFK1ipxA






 

这篇关于CSP-J 2023 复赛第1题:小苹果的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/730624

相关文章

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

HNU-2023电路与电子学-实验3

写在前面: 一、实验目的 1.了解简易模型机的内部结构和工作原理。 2.分析模型机的功能,设计 8 重 3-1 多路复用器。 3.分析模型机的功能,设计 8 重 2-1 多路复用器。 4.分析模型机的工作原理,设计模型机控制信号产生逻辑。 二、实验内容 1.用 VERILOG 语言设计模型机的 8 重 3-1 多路复用器; 2.用 VERILOG 语言设计模型机的 8 重 2-1 多

CSP-J基础之数学基础 初等数论 一篇搞懂(一)

文章目录 前言声明初等数论是什么初等数论历史1. **古代时期**2. **中世纪时期**3. **文艺复兴与近代**4. **现代时期** 整数的整除性约数什么样的整数除什么样的整数才能得到整数?条件:举例说明:一般化: 判断两个数能否被整除 因数与倍数质数与复合数使用开根号法判定质数哥德巴赫猜想最大公因数与辗转相除法计算最大公因数的常用方法:举几个例子:例子 1: 计算 12 和 18

CSP-J基础之数学基础 初等数论 一篇搞懂(二)

文章目录 前言算术基本定理简介什么是质数?举个简单例子:重要的结论:算术基本定理公式解释:举例: 算术基本定理的求法如何找出质因数:举个简单的例子: 重要的步骤:C++实现 同余举个例子:同余的性质简介1. 同余的自反性2. 同余的对称性3. 同余的传递性4. 同余的加法性质5. 同余的乘法性质 推论 总结 前言 在计算机科学和数学中,初等数论是一个重要的基础领域,涉及到整数

CSP-J基础之cmath常见函数

文章目录 前言1. **`sin` 函数**2. **`cos` 函数**3. **`exp` 函数**4. **`log` 函数**5. **`fabs` 函数**6. **`pow` 函数**7. **`sqrt` 函数**8. **`ceil` 函数**9. **`floor` 函数** 总结 前言 在计算机科学与编程中,数学函数是解决各种计算问题的基础工具。C++标准

CSP-J选择题 - 排列组合

排列问题:有5名学生参加比赛,要求排成一排拍照,有多少种不同的排列方式?组合问题:从10本书中选出3本书送给朋友,有多少种不同的选择方式?排列问题:一个教室有7个座位,5个学生需要坐下,有多少种不同的排列方式?组合问题:从12个人中选出4个人组成一个团队,有多少种不同的方式?排列问题:一个密码由4个字母组成,字母可以重复使用,有多少种不同的排列组合?组合问题:从8个不同颜色的球中选出3个,不考虑顺

2023 CCPC(秦皇岛)现场(第二届环球杯.第 2 阶段:秦皇岛)部分题解

所有题目链接:Dashboard - The 2023 CCPC (Qinhuangdao) Onsite (The 2nd Universal Cup. Stage 9: Qinhuangdao) - Codeforces 中文题面: contest-37054-zh.pdf (codeforces.com) G. Path 链接: Problem - G - Codeforces

百度之星 2015 复赛 1001 (数长方形)

数长方形    Accepts: 595    Submissions: 1225  Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description 小度熊喜欢玩木棒。一天他在玩木棒的时候,发现一些木棒会形成长方形

CSP-J 之C++常用英文缩写

文章目录 C++常用英文缩写前言常用缩写解析C++ 基础缩写输入输出相关控制台 命名与类型常用函数在线测评相关 总结 C++常用英文缩写 前言 在编程比赛和日常开发中,C++是一门广泛使用的编程语言,许多英文缩写贯穿其中。了解这些缩写不仅有助于提高编程效率,还能加深对编程语言及其工作机制的理解。本文将介绍C++中常见的英文缩写,以及它们在编程中的实际含义和应用。 常用

HNU-2023电路与电子学-实验1

写在前面: 这是电路与电子学课程的第一次实验,按照指导书的需求在Multisim软件搭建一个电路传感器模型,难度较小,细心完成就没有问题。 小tips:22级实验是采用上传到测试平台来进行功能检测,如果不通过则会打回修改后再重新提交,(我们那时候的评测系统特别特别慢,一次只能测一个同学,剩下同学就排队等着,久的时候甚至超过10个小时),这里列举一个常见的错误:热噪声有+号这端需要连接有源滤波器