#P12642. [KOI 2024 Round 1] 加倍
[KOI 2024 Round 1] 加倍
题目背景
试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。
按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。
题目描述
给定一个长度为 的正整数序列 。现在希望将该序列变为升序排列。所谓升序排列,是指对于所有的 (),都有 。
为了将序列 排成升序,可以对序列执行以下操作若干次(可为零次):
- 对于某个 (),将 乘以 。
你的任务是以最小的操作次数将序列 排成升序,并输出所需的最小操作次数。
输入格式
第一行输入一个整数 。
第二行输入 个整数,表示 ,以空格分隔。
输出格式
输出一个整数,表示将序列变为升序所需的最小操作次数。
5
3 1 4 1 5
4
5
3 1 5 1 5
6
5
1 2 3 4 5
0
提示
样例 1 说明
对 和 各执行两次操作后,序列变为 。
样例 2 说明
对 操作两次, 操作三次, 操作一次,最终序列为 。
约束条件
- 所有给定的数均为整数。
- ,其中
子问题
- (12 分)对于所有 (), 或
- (10 分)对于所有 (),存在非负整数 ,使得
- (11 分)
- (19 分)对于所有 (), 或
- (20 分)对于所有 (),
- (28 分)无额外限制条件
翻译由 ChatGPT-4o 完成