如此编码 202201-1 【CSP】

喜欢ヅ旅行 2023-09-28 21:23 49阅读 0赞

### 题目背景 ###

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

### 题目描述 ###

已知某次测验包含 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 时，满足：  
ci=a1×a2×⋯×ai

特别地，定义 c0=1。

于是 m 便可按照如下公式算出：  
![55fb6388b69b4335b761d2ba46a6d1fb.png][]

易知，0≤m<cn，最小值和最大值分别当 bi 全部为 0 和 bi=ai−1 时取得。

试帮助小 P 同学，把测验的正确答案 b1,b2,⋯,bn 从顿顿老师留下的神秘整数 m 中恢复出来。

### 输入格式 ###

从标准输入读入数据。

输入共两行。

第一行包含用空格分隔的两个整数 n 和 m，分别表示题目数量和顿顿老师的神秘数字。

第二行包含用空格分隔的 n 个整数 a1,a2,⋯,an，依次表示每道选择题的选项数目。

### 输出格式 ###

输出到标准输出。

输出仅一行，包含用空格分隔的 n 个整数 b1,b2,⋯,bn，依次表示每道选择题的正确选项。

### 样例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

Data

### 样例3解释 ###

### 子任务 ###

50% 的测试数据满足：ai 全部等于 2，即每道题均只有两个选项，此时 ci=2i；

全部的测试数据满足：1≤n≤20，ai≥2 且 cn≤10^9（根据题目描述中的定义 cn 表示全部 ai 的乘积）。

### 提示 ###

对任意的 1≤j≤n，因为 cj+1,cj+2,⋯ 均为 cj 的倍数，所以 m 除以 cj 的余数具有如下性质：

![86e5aac9399f4e778a3c477b71e5cfd2.png][]

## 代码： ##

# include<iostream>
    using namespace std;
    int main() {
    	// cout << "\n\t\t  CSP总决赛，加油！！！！\n";
    	int n,a[21], c[21], b[21];
    	long long int m;
    	cin >> n>> m;
    	c[0] = 1;
    	int sum_c_b = 0;
    	for (int i = 1; i <= n; i++) {
    		cin >> a[i];
    		c[i] = c[i - 1] * a[i];
    		b[i] = (m % c[i] - sum_c_b) / c[i - 1];
    		sum_c_b += c[i - 1] * b[i];
    		cout << b[i];
    		if (i != n)
    			cout << " ";
    	}
    	return 0;
    }

[55fb6388b69b4335b761d2ba46a6d1fb.png]: https://img-blog.csdnimg.cn/55fb6388b69b4335b761d2ba46a6d1fb.png
[86e5aac9399f4e778a3c477b71e5cfd2.png]: https://img-blog.csdnimg.cn/86e5aac9399f4e778a3c477b71e5cfd2.png