AT_kupc2020_d.Stick Combination

通过率:0%

AC君温馨提醒

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

题目描述

你有 NN 根棒子,长度分别为 1,3,5,7,…,2N−11, 3, 5, 7, \ldots, 2N-1。你的任务是用胶水将这些棒子粘接在一起,以便获得若干等长的棒子,并且至少要剩下两根长度相同的棒子。

如果可以实现,请输出任意一种粘接方案;如果无法做到,请输出 impossible。

注意,粘接过程中,每根新棒子的长度是粘接的原始棒子长度之和。你不能丢弃或切断任何棒子。

输入格式

标准输入中包含一个整数 NN,表示原始的棒子数。

输出格式

如果存在满足条件的粘接方案,第一行输出粘接后的棒子数 MM。接下来的 MM 行,每行描述一根新棒子:

  • 每行第一个数字是该根棒子由多少根原始棒子粘接而成 lml_m;
  • 接着输出这 lml_m 根原始棒子的长度,用空格分隔。

输出中允许有多个符合条件的方案,只需输出任意一个即可。

如果不存在符合条件的方案,输出 impossible。

输入输出样例

  • 输入#1

    4

    输出#1

    2
    2 1 7
    2 3 5
  • 输入#2

    2

    输出#2

    impossible
  • 输入#3

    3

    输出#3

    impossible

说明/提示

  • 输入保证为整数。
  • 2≤N≤1052 \leq N \leq 10^5

说明

示例1:可以将长度为 1,3,5,71, 3, 5, 7 的棒子分别粘接成两个长为 88 的棒子(1+71+7 和 3+53+5)。

示例2:仅有长度为 11 和 33 的两根棒子时,无法粘接成两根或更多相同长度的棒子。

示例3:即使有三根长度为 1,3,51, 3, 5 的棒子,依然不能找到满足条件的粘接方法。

本翻译由 AI 自动生成

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

首页