CF402B.Trees in a Row

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

The Queen of England has n trees growing in a row in her garden. At that, the i-th (1 ≤ i ≤ n) tree from the left has height a__i meters. Today the Queen decided to update the scenery of her garden. She wants the trees' heights to meet the condition: for all i (1 ≤ i < n), a__i + 1 - a__i = k, where k is the number the Queen chose.

Unfortunately, the royal gardener is not a machine and he cannot fulfill the desire of the Queen instantly! In one minute, the gardener can either decrease the height of a tree to any positive integer height or increase the height of a tree to any positive integer height. How should the royal gardener act to fulfill a whim of Her Majesty in the minimum number of minutes?

英国女王的花园中有一排共 nn 棵树。其中,从左往右数第 ii 棵(1≤i≤n1 \le i \le n)树的高度为 aia_i 米。今天,女王决定更新花园的景致,希望所有树的高度满足如下条件:对所有 ii(1≤i<n1 \le i < n),均有 ai+1−ai=ka_{i+1} - a_i = k,其中 kk 是女王选定的一个常数。

不幸的是,皇家园丁并非机器,无法瞬间实现女王的愿望!园丁每分钟最多可执行以下操作之一:将某棵树的高度降低至任意一个正整数高度,或将某棵树的高度升高至任意一个正整数高度。那么,园丁应如何操作,才能以最少的分钟数满足女王的心愿?

输入格式

The first line contains two space-separated integers: n, k (1 ≤ n, k ≤ 1000). The second line contains n space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 1000) — the heights of the trees in the row.

第一行包含两个用空格分隔的整数:nn、kk(1 ≤ n, k ≤ 10001 ≤ n, k ≤ 1000)。第二行包含 nn 个用空格分隔的整数 a1, a2, ..., ana_1, a_2, ..., a_n(1 ≤ ai ≤ 10001 ≤ a_i ≤ 1000)—— 表示一行中各棵树的高度。

输出格式

In the first line print a single integer p — the minimum number of minutes the gardener needs. In the next p lines print the description of his actions.

If the gardener needs to increase the height of the j-th (1 ≤ j ≤ n) tree from the left by x (x ≥ 1) meters, then print in the corresponding line "+ j x". If the gardener needs to decrease the height of the j-th (1 ≤ j ≤ n) tree from the left by x (x ≥ 1) meters, print on the corresponding line "- j x".

If there are multiple ways to make a row of trees beautiful in the minimum number of actions, you are allowed to print any of them.

第一行输出一个整数 pp —— 园丁所需的最少分钟数。接下来的 pp 行输出其操作的描述。

若园丁需要将从左往右数第 jj 棵树(1 ≤ j ≤ n1 \le j \le n)的高度增加 xx(x ≥ 1x \ge 1)米,则在对应行中输出 + j x;
若园丁需要将从左往右数第 jj 棵树(1 ≤ j ≤ n1 \le j \le n)的高度减少 xx(x ≥ 1x \ge 1)米,则在对应行中输出 - j x。

如果存在多种方式能在最少操作次数下使树排成“美观”的形态,你可以输出其中任意一种方案。

输入输出样例

  • 输入#1

    4 1
    1 2 1 5

    输出#1

    2
    + 3 2
    - 4 1
  • 输入#2

    4 1
    1 2 3 4

    输出#2

    0

输入解题思路,AI测评打分。不知道怎么写?

首页