CF42C.Safe cracking

普及/提高-

通过率:0%

AC君温馨提醒

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

题目描述

Right now you are to solve a very, very simple problem — to crack the safe. Four positive integers stand one by one on a circle protecting the safe. You know that to unlock this striking safe you have to make all four numbers equal to one. Operations are as follows: you may choose two adjacent numbers and increase both by one; you may choose two adjacent even numbers and divide both by two. Nothing else. Crack the safe!

现在,你需要解决一个非常非常简单的问题——破解保险箱。四个正整数按顺时针(或逆时针)顺序排列在一个圆圈上,共同保护着该保险箱。你已知:要打开这个令人惊叹的保险箱,必须使这四个数全部变为 11。允许的操作如下:

  • 你可以选择两个相邻的数,并将它们同时加一
  • 你可以选择两个相邻的偶数,并将它们同时除以二
    除此之外,不允许任何其他操作。破解保险箱!

输入格式

The single line of the input contains four space-separated integer positive numbers not greater than 109 each — four numbers on the circle in consecutive order.

输入仅一行,包含四个用空格分隔的正整数,每个数都不超过 10910^9 —— 这四个数按顺时针(或逆时针)顺序依次位于圆周上。

输出格式

The output should contain "-1" (quotes for clarity) if the safe is secure, that is it's impossible to crack it. Otherwise, output should contain the sequence of operations (one operations per line) leading to unlocking the safe. You don't have to minimize the number of operations, but it should not exceed 1000. To make things clear, assume numbers stand on positions 1 through 4. Each operation is encoded by two symbols. If the following operation is dividing then first symbol is '/'; otherwise it's '+' (addition). The second symbol is the position of the first number in pair in consecutive order. (see samples for clarification).

If there are several solutions, output any of them.

如果保险箱是安全的(即无法破解),则输出 "-1"(引号仅用于明确显示)。否则,输出解锁保险箱所需的操作序列(每行一个操作)。你无需最小化操作次数,但操作总数不得超过 1000。为明确起见,假设数字位于位置 1 至 4 上。每个操作由两个符号编码:若该操作为除法,则第一个符号为 /;否则为 +(加法)。第二个符号表示连续序对中第一个数字所在的位置。(参见样例以进一步澄清)

若存在多种解法,输出任意一种即可。

输入输出样例

  • 输入#1

    1 1 1 1

    输出#1

  • 输入#2

    1 2 4 2

    输出#2

    /2
    /3
  • 输入#3

    3 3 1 1

    输出#3

    +1
    /1
    /1
  • 输入#4

    2 1 2 4

    输出#4

    /3
    /4

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

首页