【CSP】202209-1_如此编码Python实现

文章目录

• • @[toc]
  • • 试题编号
    • 试题名称
    • 时间限制
    • 内存限制
    • 题目背景
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例$1$输入
    • 样例$1$输出
    • 样例$2$输入
    • 样例$2$输出
    • 样例$3$输入
    • 样例$3$输出
    • 样例$3$解释
    • 子任务
    • 提示
    • `Python`实现

试题编号

试题名称

时间限制

内存限制

题目背景

• 某次测验后，顿顿老师在黑板上留下了一串数字$23333$便飘然而去，凝望着这个神秘数字，小$P$同学不禁陷入了沉思

题目描述

• 已知某次测验包含$n$道单项选择题，其中第$i$题$(1\le i\le n)$有$a_i$个选项，正确选项为$b_i$，满足$a_i\ge 2$且 $0\le b_i<a_i$
• 比如说，$a_i=4$表示第$i$题有$4$个选项，此时正确选项$b_i$的取值一定是$0$、$1$、$2$、$3$其中之一
• 顿顿老师设计了如下方式对正确答案进行编码，使得仅用一个整数$m$便可表示$b_1$，$b_2$，$\cdots$，$b_n$
• 首先定义一个辅助数组$c_i$，表示数组$a_i$的前缀乘积，当$1\le i\le n$时，满足：

$$c_i=a_1\times a_2\times \cdots \times a_i$$

• 特别地，定义$c_0=1$
• 于是$m$便可按照如下公式算出

$$\begin{array}{rl}m& =\sum _{i=1}^n{c}_{i-1}\times b_i\\ & =c_0\times b_1+c_1\times b_2+\cdots +c_{n-1}\times b_n\end{array}$$

• 易知，$0\le m<c_n$，最小值和最大值分别当$b_i$全部为$0$和$b_i=a_i-1$时取得
• 试帮助小$P$同学，把测验的正确答案$b_1$，$b_2$，$\cdots$，$b_n$从顿顿老师留下的神秘整数$m$中恢复出来

输入格式

• 从标准输入读入数据
• 输入共两行
• 第一行包含用空格分隔的两个整数$n$和$m$，分别表示题目数量和顿顿老师的神秘数字
• 第二行包含用空格分隔的$n$个整数$a_1$，$a_2$，$\cdots$，$a_n$，依次表示每道选择题的选项数目

输出格式

• 输出到标准输出
• 输出仅一行，包含用空格分隔的$n$个整数$b_1$，$b_2$，$\cdots$，$b_n$，依次表示每道选择题的正确选项

样例$1$输入

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

样例$2$输入

4 0
2 3 2 5

样例$2$输出

0 0 0 0

样例$3$输入

7 23333
3 5 20 10 4 3 10

样例$3$输出

2 2 15 7 3 1 0

样例$3$解释

子任务

• $50\%$的测试数据满足：$a_i$全部等于$2$，即每道题均只有两个选项，此时$c_i=2^i$
• 全部的测试数据满足：$1\le n\le 20$，$a_i\ge 2$且$c_n\le 10^9$（根据题目描述中的定义$c_n$表示全部$a_i$的乘积）

提示

• 对任意的$1\le j\le n$，因为$c_{j+1}$，$c_{j+2}$，$\cdots$均为$c_j$的倍数，所以$m$除以$c_j$的余数具有如下性质：

$$m\%c_j=\sum _{i=1}^j{c}_{i-1}\times b_i$$

• 其中$\%$表示取余运算，令$j$取不同的值，则有如下等式：

$$\begin{array}{rl}m\%c_1& =c_0\times b_1\\ m\%c_2& =c_0\times b_1+c_1\times b_2\\ m\%c_2& =c_0\times b_1+c_1\times b_2+c_2\times b_3\end{array}$$

Python实现

n, m = map(int, input().split())
a = list(map(int, input().split()))

b = []
c = 1

for i in range(n):
    temp = c

    c *= a[i]

    b.append((m % c) // temp)

print(*b)