【CSP】202209-1_如此編碼Python實現

文章目錄

@[toc]
試題編號
試題名稱
時間限制
內存限制
題目背景
題目描述
輸入格式
輸出格式
樣例1輸入
樣例1輸出
樣例2輸入
樣例2輸出
樣例3輸入
樣例3輸出
樣例3解釋
子任務
提示
`Python`實現

試題編號

202209-1

試題名稱

如此編碼

時間限制

1.0s

內存限制

512.0MB

題目背景

某次測驗后，頓頓老師在黑板上留下了一串數字 $23333$ 便飄然而去，凝望著這個神秘數字，小 $P$ 同學不禁陷入了沉思

題目描述

已知某次測驗包含 $n$ 道單項選擇題，其中第 $i$ 題 $\leq i \leq n)$ 有 $a_{i}$ 個選項，正確選項為 $b_{i}$ ，滿足 $a_{i} \geq 2$ 且 $\leq 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}$ 的前綴乘積，當 $\leq i \leq n$ 時，滿足：

$c_{i} = a_{1} \times a_{2} \times \cdots \times a_{i}$

特別地，定義 $c_{0} = 1$
于是 $m$ 便可按照如下公式算出

$\begin{aligned} m &= \displaystyle\sum\limits_{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{aligned}$

易知， $\leq 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解釋

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$a_{i}$	$3$	$5$	$20$	$10$	$4$	$3$	$10$
$b_{i}$	$2$	$2$	$15$	$7$	$3$	$1$	$0$
$c_{i - 1}$	$1$	$3$	$15$	$300$	$3000$	$12000$	$36000$

子任務

$50\%$ 的測試數據滿足： $a_{i}$ 全部等于 $2$ ，即每道題均只有兩個選項，此時 $c_{i} = 2^{i}$
全部的測試數據滿足： $\leq n \leq 20$ ， $a_{i} \geq 2$ 且 $c_{n} \leq 10^{9}$ （根據題目描述中的定義 $c_{n}$ 表示全部 $a_{i}$ 的乘積）

提示

對任意的 $\leq j \leq n$ ，因為 $c_{j + 1}$ ， $c_{j + 2}$ ， $\cdots$ 均為 $c_{j}$ 的倍數，所以 $m$ 除以 $c_{j}$ 的余數具有如下性質：

$\% c_{j} = \displaystyle\sum\limits_{i = 1}^{j}{c_{i - 1} \times b_{i}}$

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

$\begin{aligned} 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{aligned}$

`Python`實現

n, m = map(int, input().split())
a = list(map(int, input().split()))b = []
c = 1for i in range(n):temp = cc *= a[i]b.append((m % c) // temp)print(*b)

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/207770.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/207770.shtml
英文地址，請注明出處：http://en.pswp.cn/news/207770.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！