做网站全屏图片拉长代码,海报设计培训,深圳物流公司收费标准,网站首页布局设计工具题目链接 [蓝桥杯 2015 省 A] 饮料换购 题目描述
乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊 C C C 型饮料#xff0c;凭 3 3 3 个瓶盖可以再换一瓶 C C C 型饮料#xff0c;并且可以一直循环下去(但不允许暂借或赊账)。
请你计算一下#xff0c;如果小明不浪费瓶盖…题目链接 [蓝桥杯 2015 省 A] 饮料换购 题目描述
乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊 C C C 型饮料凭 3 3 3 个瓶盖可以再换一瓶 C C C 型饮料并且可以一直循环下去(但不允许暂借或赊账)。
请你计算一下如果小明不浪费瓶盖尽量地参加活动那么对于他初始买入的 n n n 瓶饮料最后他一共能喝到多少瓶饮料。
输入格式
一个整数 n n n表示开始购买的饮料数量。
输出格式
一个整数表示实际得到的饮料数。
输入输出样例
输入 100 输出 149 输入 101 输出 151 数据范围 0 ≤ n ≤ 10000 0 \leq n \leq 10000 0≤n≤10000
解法模拟
由于 3 3 3 个瓶盖可以换 1 1 1 瓶饮料那么对于 n n n 瓶饮料我们直接将其转换为 n × 3 n \times 3 n×3 个瓶盖。
我们令 m n × 3 m n \times 3 mn×3。
我们可以换到的饮料瓶数为 t ⌊ m 3 ⌋ t \lfloor \frac{m}{3} \rfloor t⌊3m⌋。此时我们直接累加到答案 a n s ans ans 中。
由于我们换到了 t t t 瓶饮料所以我们消耗掉了 t × 3 t \times 3 t×3 个瓶盖需要用总的瓶盖数减去消耗掉的瓶盖数即 m m − t × 3 m m - t \times 3 mm−t×3。
由于我们获得了 t t t 瓶饮料所以还要加上 t t t 个瓶盖数。
所以最终 m m − t × 3 t m m - t \times 3 t mm−t×3t。
只要 m ≥ 3 m \geq 3 m≥3就要一直循环模拟这个过程直到换掉所有饮料。
时间复杂度 O ( l o g n ) O(logn) O(logn)
C代码
#include iostream
#include cstringusing namespace std;
using LL long long;void solve(){int n;cinn;n * 3;int ans 0;while(n 3){int t n / 3;ans t;n - (t * 3);n t;}coutans\n;
}int main(){int t 1;while(t--){solve();}return 0;
}Java代码
import java.util.*;
import java.io.*;public class Main{static BufferedReader in new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws Exception {int n Integer.parseInt(in.readLine().trim());n * 3;int ans 0;while(n 3) {int t n / 3;ans t;n - (t * 3);n t;}System.out.println(ans);}
}
