| Submeter | Todas submissőes | Melhores | Voltar |
FEIJOEMG - Feijões |
A Companhia ACME acabou de desenvolver seu mais novo produto, Feijões Mágicos\texttrademark, disponíveis em vários tamanhos e cores. Baseado nos custos de desenvolvimento e nas espectativas de vendas, o departamento de finanças estipulou os menores preços pelos quais cada tipo de feijão mágico pode ser vendido.
O CEO da companhia, porém, é um tanto quanto excêntrico. Para cada tipo de feijão, ele decidiu um valor K entre 1 e 10 e decidiu que o preço de venda daquele produto deve possuir exatamente K dígitos distintos em sua representação decimal. Por exemplo, se K=3, preços válidos seriam 102, 753, 3000009003, 76666661. Porém, 888 seria um preço inválido (pois só possui um dígito distinto).
Sua tarefa é agradar tanto ao departamento de finanças quanto ao CEO. Dado um inteiro P que representa o menor preço com o qual um produto pode ser vendido e um inteiro K que representa o número de dígitos distintos que o preço final deve ter, você deve descobrir qual o menor inteiro T que é maior ou igual a P e possui exatamente K dígitos distintos em sua representação decimal.
Entrada
A primeira linha da entrada contém o número de casos de teste. Cada caso de teste é dado em uma linha contendo dois inteiros P (1 ≤ P ≤ 1018) e K (1 ≤ K ≤ 10).
Saída
Para cada caso de teste, imprima uma linha no formato Caso <X>: <T>, onde <X> é o número do caso de teste (sequencial, a partir de 1) e <T> é o menor inteiro que satisfaz tanto ao departamento de finanças quanto ao CEO.
Exemplos
Entrada: 5 36 1 74 2 2 3 997 3 14678 3 Saída: Caso 1: 44 Caso 2: 74 Caso 3: 102 Caso 4: 1002 Caso 5: 14711
No primeiro caso, números de dois algarismos com apenas um dígito são 11, 22, 33, 44, etc. O menor deles que é maior ou igual a 36 é 44.
No segundo caso, 74 já possui dois digitos distintos, e portanto o valor ideal é ele mesmo.
No terceiro caso, números com 3 dígitos distintos têm necessariamente que ter pelo menos 3 algarismos. O menor com 3 dígitos distintos é 102 (porque 100 e 101 só possuem dois dígitos distintos).
No quarto caso, 997 e 998 possuem apenas 2 dígitos distintos, e 999 apenas 1. Assim, precisamos considerar números de 4 algarismos. O menor deles com 3 algarismos distintos é 1002.
| Adicionado por: | Wanderley Guimarăes |
| Data: | 2012-03-14 |
| Tempo limite: | 0.100s |
| Tamanho do fonte: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Linguagem permitida: | Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL |
| Origem: | Seletiva UFMG 2011 |
hide comments
|
2017-07-08 16:27:44
“Deuses são reais se acredita neles” |
|
|
2017-05-27 18:46:18
Gente em java da pra usar a classe BigInteger, não? |
|
|
2013-09-22 02:56:04 Kleber Vianna [FATEC/SP]
Que tipo nativo do C aceita 10^18??? Nem definindo como double está dando certo. Last edit: 2013-09-22 02:57:07 |
|
|
2013-08-28 05:30:37 Alexandre Henrique Afonso Campos
O meu ainda năo deu certo, mas algo que reduziu o tempo de execuçăo do meu código foi redefinir P como min(P,10^K). Assim, ao procurar pelo menos 3 algarismos distintos, ele começa direto no 100. Ao procurar 4, ele começa no 1000, etc. |
|
|
2012-07-30 14:34:37 chrislucas
Escrevi um algoritmo tăo simples e to tomando TLE,alguém tem uma dica????? |