Sequências e Subsequências Binárias
Você tem uma sequencia binária (ou seja, formada apenas por zeros e uns).
Sua tarefa é dividir a sequência no menor número de subsequências , ou seja cada subsequência se parece com ou , ou seja, não pode haver zeros ou uns adjacentes. Além disso, todos os números devem estar em exatamente uma subsequência.
Lembre-se que uma subsequência de é uma sequência que pode ser extraída de removendo algum número, possivelmente zero, de elementos de , sem trocar a ordem relativa entre os elementos que sobraram. Por exemplo, algumas subsequências de são , , , , etc. Porém, , e não são.
Entrada:
A primeira linha de entrada contém um inteiro , o número de casos de teste. casos seguem.
A primeira linha de cada caso de teste contém um inteiro , o tamanho de . Então segue a sequência .
Saída
Para cada caso de teste, imprima duas linhas:
Na primeira linha, imprima um inteiro , o total de subsequências necessárias.
Na segunda linha, imprima inteiros em qual subsequência o -ésimo número de deve pertencer.
Se houver mais de uma resposta possível, imprima qualquer uma.
Restrições:
- Garante-se também que a soma dos s em todos os casos de teste não ultrapassa .
Entrada | Saida |
4 4 0011 6 111111 5 10101 8 01010000 |
2 1 2 2 1 6 1 2 3 4 5 6 1 1 1 1 1 1 4 1 1 1 1 1 2 3 4 |
Para submeter sua solução, use esse link.