Uma das tarefas de preparar um problema das Olimpíadas Nacionais de Informática é criar casos de teste para testar os programas dos concorrentes. Hoje essa tarefa será invertida, é a tua vez de criar os casos de teste.
O problema para o qual irás criar casos de teste é o problema clássico da "Maior Subsequência Crescente" (também conhecido como Longest Increasing Subsequence). Neste problema é dada uma permutação de comprimento N, ou seja, uma sequência de N inteiros distintos de 1 a N. O objetivo é determinar o comprimento da maior subsequência crescente. Por exemplo, se a permutação for [4 2 3 1 5], a maior subsequência crescente tem comprimento 3, e é dada pelos elementos [2 3 5].
Para criar bons casos de teste a tua tarefa consiste no seguinte: são te dados dois inteiros K e Q. O objetivo é construir uma permutação de comprimento no máximo Q que tenha exatamente K subsequências crescentes máximas, ou seja, sequências crescentes distintas com tamanho igual ao da maior subsequência crescente.
Se K = 5, a seguinte permutação de 9 elementos tem exatamente 5 subsequências crescentes máximas:
7 9 8 5 6 3 4 1 2
O tamanho da maior subsequência crescente é 2, e as 5 subsequências são as seguintes: [7, 9], [7, 8], [5, 6], [3, 4], [1, 2].
O input contém apenas uma linha com dois inteiros, K e Q.
O output deve conter primeiro uma linha com um inteiro N, o comprimento da permutação que construíram.
De seguida deve conter uma linha com N inteiros separados por espaços, representando a permutação.
Se o valor de N for superior a Q o resultado da submissão será Wrong Answer.
São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:
| 1 ≤ K ≤ 1018 | Número de sequências |
Os casos de teste deste problema estão organizados em 4 grupos com restrições adicionais diferentes:
| Grupo | Número de Pontos | Restrições adicionais |
|---|---|---|
| 1 | 20 | K ≤ 1 000, Q = 20 000 |
| 2 | 20 | K ≤ 1012, Q = 20 000 |
| 3 | 30 | Q = 5 000 |
| 4 | 30 | Q = 400 |
5 20000
9 7 9 8 5 6 3 4 2 1
Este exemplo corresponde ao exemplo mencionado no enunciado.
3 20000
3 3 2 1
1 20000
4 1 2 3 4