← 返回题目列表

AtCoder · scpc2026_div2_l

L. ChannelTalk 工作流程

中文机器翻译题面 查看原题

表示言語

/ /

分数: 100 点

问题陈述

ChannelTalk 是一款一体式 AI 信使,可促进与客户的实时沟通,提供的工作流程功能使任何人都可以轻松创建聊天机器人。使用 ChannelTalk Workflow,您可以根据客户和情况组合触发器和操作,例如构建块,以自动化从咨询开始到结束的整个流程。此外,经常使用的功能可以创建为模块并多次重复使用。

Ino 打算使用 ChannelTalk Workflow 构建一个聊天机器人来处理 N 不同类型的问题。每个问题都分配有一个唯一的编号 1 to N.

井野想要添加 M 模块添加到工作流程并从 0 to M-1 按添加顺序排列。由于 Ino 无法管理太多模块,最多 可以使用 2\,048 模块。

提问时 输入 x ,模块 i 的操作如下。

  • If x = i,回答问题并结束咨询。
  • If x \neq i,进入问题 x 到模块 L_i if x \le F_i和模块 G_i if x \gt F_i.

当收到问题时,首先将其输入到模块 0,执行每个模块需要 1 第二。也就是说,处理问题所花费的时间 i 等于通过的模块总数,包括模块 0 和模块 i,直至咨询结束。如果同一个模块被多次通过,则按照被通过的次数进行计数。

Ino 希望确保磋商结束 正是 K 秒,无论来自哪个问题 询问 1 to N 。给定问题类型的数量 N 和结束时间 K,选择模块数量 M 和值 F_i, L_i,和 G_i 对于每个模块,以便咨询始终准确结束于 K 最多使用秒 2\,048 模块。 请注意 M 不需要最小化。

约束

  • 2 \le K \le N \le 1\,000
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K

输出

第一行,输出模块数量 M 使用。 (1 \le M \le 2\,048)

从第二行开始,输出 M 行。上 (i+2)第行,输出三个整数 F_i, L_i,和 G_i 代表模块 i,用空格分隔。 (0 \le F_i \le N;\ 0 \le L_i, G_i < M)

如果不存在解,则输出 -1 。


示例输入 1

6 6

示例输出 1

11
1 7 1
2 7 2
3 7 3
4 7 4
5 5 6
4 0 0
5 0 0
3 8 4
2 9 3
1 10 2
0 0 1

表示言語

/ /

점수 : 100 점

문제

고객과의 실시간 소통을 편리하게 해주는 올인원 AI 메신저 채널톡은 누구나 쉽게 챗봇을 만들 수 있도록 워크플로우 기능을 제공한다。 채널톡 워크플로우를 고객과 상황에 따라 필요한 트리거와 액션을 블록처럼 조합해 상담 시작부터 끝까지 전 과정을 자동화할 수 있다。 또한 반복적으로 필요한 기능은 모듈로 만들어 여러 번 재활용할 수도 있다。

이노는 채널톡 워크플로우를 이용해 N종류의 서로 다른 질문을 처리하는 챗봇을 제작하려 한다. 각 질문에는 1번부터 N번까지의 서로 다른 번호가 매겨져 있다.

이노는 워크플로우에 M개의 모듈을 추가하고 추가한 순서대로 0번부터 M-1번까지 번호를 매기고자 한다. 이노는 너무 많은 모듈을 관리할 능력이 없기 때문에 최대 2\,048개의 모듈만 사용할 수 있다.

i번 모듈은 x번 질문이 입력되었을 때 다음과 같이 작동한다.

  • x = i인 경우 해당 질문에 답변한 뒤 상담을 종료한다.
  • x \neq i인 경우 x \le F_i면 L_i번 모듈, x \gt F_i면 G_i번 모듈에 x번 질문을 입력한다.

질문이 들어오면 처음에 0번 모듈에 입력되며, 각 모듈을 실행하는 데에는 1초가 걸린다. 즉, i번 질문을 처리하는 데 걸리는 시간은 0번 모듈과 i번 모듈을 포함해 상담을 종료할 때까지 거쳐간 모듈의 총 개수와 같다. 같은 모듈을 여러 번 거쳐간 경우 거쳐간 횟수만큼 중복해 센다.

이노는 1번부터 N번까지 중 어느 질문을 해도 정확히 K초만에 상담이 종료되도록 만들고자 한다. 질문의 종류 N과 종료 시간 K가 주어질 때 모듈의 수 M과 각 모듈의 F_i, L_i, G_i를 적절히 정해 2\,048개 이하의 모듈로 항상 정확히 K초만에 상담이 끝나도록 만들어 보자. M을 최소화할 필요는 없음에 유의하라.

제한

  • 2 \le K \le N \le 1\,000
  • 입력으로 주어지는 수는 모두 정수이다.

입력

입력은 다음 형식으로 표준 입력으로 주어진다.

N K

출력

첫 번째 줄에 사용할 모듈의 수 M을 출력한다. (1 \le M \le 2\,048)

두 번째 줄부터 M개의 줄에 걸쳐, i+2번째 줄에 i번 모듈의 규칙을 나타내는 세 정수 F_i, L_i, G_i를 공백으로 구분하여 출력한다. (0 \le F_i \le N;\ 0 \le L_i, G_i < M)

가능한 방법이 존재하지 않는 경우 대신 -1을 출력한다.


입력 예 1

6 6

출력 예 1

11
1 7 1
2 7 2
3 7 3
4 7 4
5 5 6
4 0 0
5 0 0
3 8 4
2 9 3
1 10 2
0 0 1