P1118 [USACO06FEB]数字三角形`Backward Digit Su`…

    • 5K通过
    • 13K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 搜索 枚举,暴力 深度优先搜索,DFS USACO 2006
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    FJ and his cows enjoy playing a mental game. They write down the numbers from $1$ to$ N(1 \le N \le 10)$ in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when $N=4$) might go like this:

        3   1   2   4
          4   3   6
            7   9
             16

    Behind FJ's back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number $N$. Unfortunately, the game is a bit above FJ's mental arithmetic capabilities.

    Write a program to help FJ play the game and keep up with the cows.

    有这么一个游戏:

    写出一个$1$至$N$的排列$a_i$,然后每次将相邻两个数相加,构成新的序列,再对新序列进行这样的操作,显然每次构成的序列都比上一次的序列长度少$1$,直到只剩下一个数字位置。下面是一个例子:

    $3,1,2,4$

    $4,3,6$

    $7,9$

    $16$

    最后得到$16$这样一个数字。

    现在想要倒着玩这样一个游戏,如果知道$N$,知道最后得到的数字的大小$sum$,请你求出最初序列$a_i$,为$1$至$N$的一个排列。若答案有多种可能,则输出字典序最小的那一个。

    [color=red]管理员注:本题描述有误,这里字典序指的是$1,2,3,4,5,6,7,8,9,10,11,12$

    而不是$1,10,11,12,2,3,4,5,6,7,8,9$[/color]

    输入输出格式

    输入格式:

    两个正整数$n,sum$。

    输出格式:

    输出包括$1$行,为字典序最小的那个答案。

    当无解的时候,请什么也不输出。(好奇葩啊)

    输入输出样例

    输入样例#1: 复制
    4 16
    输出样例#1: 复制
    3 1 2 4

    说明

    对于$40\%$的数据,$n≤7$;

    对于$80\%$的数据,$n≤10$;

    对于$100\%$的数据,$n≤12,sum≤12345$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。