Um dos problemas da final das Olimpíadas Nacionais de Informática do ano 2016. Para compreender bem o problema devemos ler o enunciado original (To understand the problem well we must read the original statement).
"Muitas culturas têm superstições com números. Em Portugal, tal como noutros países ocidentais, o 13 é considerado um número azarado. Em muitos países do este Asiático o número do azar é o 4, sendo evitado a todos os custos, pois a maneira como é pronunciado é muita semelhante à palavra morte. Já na Rússia o número a evitar é o 40. Estas superstições são tão fortes que os números são evitados quando possível. Existem aviões sem fila 13, prédios sem 13º andar e e urbanizações onde o número da habitação passa diretamente do 12 para o 14.
Num qualquer país onde o número do azar seja A, um número sortudo é um número inteiro positivo que não tenha nenhuma ocorrência de A nos seus dígitos. Por exemplo, se A=13, os números 14, 123, 5153 ou 789 seriam números sortudos, ao passo que 13, 1132, 513 ou 13913 não o seriam.
Existem mesmo muitos números sortudos! Por exemplo, a sequência de números sortudos na China (onde A=4) é a seguinte:
1 2 3 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 21 22 23 25 26 ...
Se num prédio chinês apenas fossem usados números sortudos, o andar marcado como 16º seria na realidade o 14º andar, ou seja, o 16 é o 14º número da sequência de números sortudos. E se estivesses por exemplo no andar marcado como 80, qual seria o verdadeiro andar? No fundo o que queres saber é, dado um qualquer número sortudo, qual a sua posição, ou o seu número de ordem, na sequência crescente de números sortudos.
Tens de fazer um programa para te ajudar a resolver este dilema! Claro que gostavas que o programa fosse usável em qualquer parte do mundo, e por isso tem de aceitar um qualquer número azarado a evitar.
O problema é: dado um número do azar A e Q questões, cada uma com um número sortudo Ni, a tua tarefa é calcular qual a posição Pi (nº ordem) de cada um dos Ni na sequência de números sortudos, ou seja, números que não contenham ocorrências de A."
Many cultures have superstitions about numbers. In Portugal, as in other Western countries, 13 is considered an unlucky number. In many East Asian countries, the unlucky number is 4, which is avoided at all costs, as the way it is pronounced is very similar to the word death. In Russia, the number to avoid is 40. These superstitions are so strong that numbers are avoided when possible. There are planes without a queue 13, buildings without a 13th floor and urbanizations where the number of dwellings goes directly from 12 to 14.
In any country where the unlucky number is A, a lucky number is a positive integer that does not have any occurrence of A in its digits. For example, if A=13, the numbers 14, 123, 5153 or 789 would be lucky numbers, while 13, 1132, 513 or 13913 would not be.
There are really many lucky numbers! For example, the sequence of lucky numbers in China (where A=4) is as follows: 1 2 3 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 21 22 23 25 26 ...
If in a Chinese building only lucky numbers were used, the floor marked as 16th would actually be the 14th floor, that is, 16 is the 14th number in the sequence of lucky numbers. And if you were, for example, on the floor marked 80, what would the real floor be? Basically, what you want to know is, given any lucky number, what is its position, or its order number, in the increasing sequence of lucky numbers.
You have to make a program to help you solve this dilemma! Of course you would like the program to be usable anywhere in the world, so you have to accept any unlucky number to avoid.
The problem is: given an unlucky number A and Q questions, each with a lucky number Ni, your task is to calculate the Pi position (order number) of each of the Ni in the sequence of lucky numbers, that is, numbers that do not contain occurrences of A.