当前位置:首页 > 题解目录 > 正文内容

小苹果(apple)

亿万年的星光11个月前 (10-01)题解目录1325

【题目描述】

小 Y 的桌子上放着n个苹果从左到右排成一列,编号为从1到n。

小苞是小 Y 的好朋友,每天她都会从中拿走一些苹果。

每天在拿的时候,小苞都是从左侧第1个苹果开始、每隔2个苹果拿走2个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。

小苞想知道,多少天能拿完所有的苹果,而编号为n的苹果是在第几天被拿走的?

【输入描述】

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

【输出描述】

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

【样例输入】

8

【样例输出】

5 5

【提示】

说明/提示

【样例 1 解释】

小苞的桌上一共放了8个苹果。

小苞第一天拿走了编号为1、4、7的苹果。

小苞第二天拿走了编号为2、6的苹果。

小苞第三天拿走了编号为3的苹果。

小苞第四天拿走了编号为5的苹果。

小苞第五天拿走了编号为8的苹果。

【数据范围】

1n109 

测试点n≤特殊性质
1∼210
3∼5103
6∼7106
8∼9106
10109


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

【题目分析】

  1. 题目有点“约瑟夫环”的感觉。

  2. 简单找找取模的规律。




【参考代码】

#include <bits/stdc++.h>
using namespace std;
int n, ans, num;
//n是苹果数量,ans记录天数,num记录第一次n%3==1的时间。
int main() {
  cin >> n;
  while (n) {
    ans++;
    //每过一天ans++。
    if (n % 3 == 1 && !num) {
      num = ans;
    }
    //如果n%3==1并且是第一次出现,记录num。
    n = n - (n + 2) / 3;
    //n每次减少1/3 n个苹果。
  }
  cout << ans << ' ' << num;
  //输出天数和拿走第n个苹果的时间。
  return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】背包问题3

【题目描述】完全背包定义有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。本题要求是背...

【题解】光荣的梦想

【题目描述】Prince对他在这片大陆上维护的秩序感到满意,于是决定启程离开艾泽拉斯。在他动身之前,Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代,平...

【题解】最长上升子序列

【题目描述】一个数的序列bi,当b1<b2<...<bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN),我们可以得到一些上升的子序列(ai1,ai2,...

【题解】泥泞路(2019青岛市程序设计竞赛)

【题目描述】大雨过后,从小A的农场到镇上的公路上有一些泥泞路段,为了方便出行,他决定将若干块长度为L的木板可以铺在这些泥泞路段上,问他至少需要多少块木板,才能将所有的泥泞路段覆盖住。【输入】第一行为正...

【动态规划】完全背包

【题目描述】设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为m,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于m,而价值的和...

【题解】老王赛马

【题目描述】赛马是一古老的游戏,早在公元前四世纪的中国,处在诸侯割据的状态,历史上称为“战国时期”。在魏国作官的孙膑,因为受到同僚庞涓的迫害,被齐国使臣救出后,到达齐国国都。 赛马是当时最受...