CSP 202209-1 如此编码 C++ 100

2023-01-07

题目

【题目描述】己知某次测验包含n道单项选择题，其中第i题(1≤i≤n)有ai个选项，正确选项为bi,满足ai≥2且 0≤bi<ai。比如说，ai=4表示第i题有4个选项，此时正确选项bi,的取值一定是0、1、2、3其中之一。顿顿老师设计了如下方式对正确答案进行编码，使得仅用一个整数m便可表示b1，b2,···,bn 首先定义一个辅助数组ci,表示数组ai的前缀乘积。当1≤i≤n时，满足：

$C_i=a_1×a_2×···×a_i$

特别地，定义c0=1。于是 m 便可按照如下公式算出：

$m=\sum_{i=1}^{n}c_i×b_i\
=c_0b_1+c_1b_2+···+c_{n-1}b_n$
易知，0≤m<cn,最小值和最大值分别当bi全部为0和bi=ai-1时取得。试帮助小P同学，把测验的正确答案b1,b2,···,bn从顿顿老师留下的神秘整数m中恢复出来。

【输入格式】从标准输入读入数据。输入共两行。第一行包含用空格分隔的两个整数n和m,分别表示题目数量和顿顿老师的神秘数字。第二行包含用空格分隔的n个整数a1,a2,···,an,依次表示每道选择题的选项数目。

【输出格式】输出到标准输出。输出仅一行，包含用空格分隔的n个整数b1,b2,···,bn,依次表示每道选择题的正确选项。【样例输入】

1 2	15 32767 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

【样例输出】

1	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

代码

#include <bits/stdc++.h>

using namespace std;
using ll=long long;
const ll N=100;

int main()
{
    ll n,m;
    ll c[N];
    ll a,t;
    cin>>n>>m;
    c[0]=1;
    for(ll i=1;i<=n;i++)
    {
        cin>>a;
        c[i]=c[i-1]*a;
    }

    for(ll i=1;i<=n;i++)
    {
        t=m%c[i]-m%c[i-1];
        cout<<t/c[i-1]<<' ';
    }

    return 0;
}