Skip to content

11352: 【原1352】梓喵打酱油

题目

题目描述

author: SSY 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1352

Description

梓喵去买瓶装酱油。老板丁姐最近在搞优惠活动,用X瓶空的酱油瓶能换1瓶新的酱油。但是丁姐又是奇怪的人,每次换购需要的空瓶数量又不一定一样,也就是说每次X的值可能不同。对于每一次,梓喵都尽可能多地换新酱油。X变化只有n次,只有当梓喵换一次酱油后,X的值才会变。如果n次变化以后还能换酱油,则以后每次换购需要的空瓶数量均为最后一次X的值。老板丁姐也是个抠门的人,他不会借你酱油。梓喵想知道她最终究竟能打到多少瓶酱油,最后剩多少空瓶子,答案保证在long long范围内。第一次机考,这题打打酱油就能满分了。

Input Format

第一行有两个数m,n,分别表示梓喵一开始买的酱油数量和丁姐的变化次数。

第2-n+1行,每行一个正整数,表示第i次换的时候X(X≥1)的值,最后一次X>1。

Output Format

输出一行,两个数用空格隔开,表示梓喵总共能打到多少瓶酱油(包括一开始的m瓶)和最后手上剩下的空瓶数量。

Sample Input 1

100 3
10
1
2

Sample Output 1

129 1

Sample Input 2

100 4
10
11
2
3

Sample Output 2

110 10

yyong119's solution

#include <iostream>
#include <cstring>
using namespace std;

long long n, m, sum, rest;
int flag;

int main() {

    cin >> m >> n;
    sum = m;
    rest = m;
    long long x[n];
    memset(x, 0, sizeof(x));

    for (int i = 0; i < n; ++i)
        cin >> x[i];

    for (int i = 0; i < n - 1; ++i) {

        if (rest < x[i]) {
            flag = 1;
            break;
        }
        long long change = rest / x[i];
        sum += change;
        rest = rest % x[i] + change;
    }

    if (!flag)
        while (rest >= x[n - 1]) {

            long long change = rest / x[n - 1];
            sum += change;
            rest = rest % x[n - 1] + change;
        }

    cout << sum << " " << rest << endl;

    return 0;
}