J - ChannelTalk Workflow Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

表示言語

/ /

Score : 100 points

Problem Statement

ChannelTalk, an all-in-one AI messenger that facilitates real-time communication with customers, offers a workflow feature that allows anyone to easily create chatbots. Using ChannelTalk Workflow, you can combine triggers and actions like building blocks based on the customer and the situation to automate the entire process from the start to the end of a consultation. Additionally, frequently used functions can be created as modules and reused multiple times.

Ino intends to build a chatbot using ChannelTalk Workflow to handle N different types of questions. Each question is assigned a unique number from 1 to N.

Ino wants to add M modules to the workflow and number them from 0 to M-1 in the order they are added. Since Ino cannot manage too many modules, at most 2\,048 modules can be used.

When question x is entered, module i operates as follows.

  • If x = i, it answers the question and ends the consultation.
  • If x \neq i, it enters question x to module L_i if x \le F_i, and module G_i if x \gt F_i.

When a question is received, it is first input to module 0, and executing each module takes 1 second. That is, the time taken to process question i is equal to the total number of modules passed through, including module 0 and module i, until the consultation ends. If the same module is passed through multiple times, it is counted as many times as it was passed through.

Ino wants to ensure that the consultation ends in exactly K seconds regardless of which question from 1 to N is asked. Given the number of question types N and the ending time K, choose the number of modules M and the values of F_i, L_i, and G_i for each module so that the consultation always ends exactly at K seconds using at most 2\,048 modules. Note that M does not need to be minimized.

Constraints

  • 2 \le K \le N \le 1\,000
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K

Output

On the first line, output the number of modules M to use. (1 \le M \le 2\,048)

From the second line, output M lines. On the (i+2)-th line, output three integers F_i, L_i, and G_i representing module i, separated by spaces. (0 \le F_i \le N;\ 0 \le L_i, G_i < M)

If no solution exists, output -1 instead.

Sample Input 1

6 6

Sample Output 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

表示言語

/ /

配点 : 100 点

問題文

顧客とのリアルタイムなコミュニケーションを便利にするオールインワン AI メッセンジャー ChannelTalk は，誰でも簡単にチャットボットを作れるようにワークフロー機能を提供している．ChannelTalk Workflow を利用すると，顧客や状況に応じて必要なトリガーとアクションをブロックのように組み合わせ，相談の開始から終了までの全過程を自動化できる．また，繰り返し必要な機能はモジュールとして作り，何度も再利用できる．

イノは ChannelTalk Workflow を利用して，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

出力

1行目に使用するモジュール数 M を出力する．(1 \le M \le 2\,048)

2行目から M 行にわたり，i+2 行目に i 番モジュールを表す 3 つの整数 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