URI Online Judge | 1226
Elevador Espacial
Maratona de Programação da SBC 
Brasil
Timelimit: 2 Brasil
A China está construindo um elevador espacial, que permitirá o lançamento de sondas e satélites a um custo muito mais baixo, viabilizando não só projetos de pesquisa científica como o turismo espacial.
No entanto, os chineses são muito supersticiosos, e por isso têm um cuidado muito especial com a numeração dos andares do elevador: eles não usam nenhum número que contenha o dígito “4” ou a sequência de dígitos “13”. Assim, eles não usam o andar 4, nem o andar 13, nem o andar 134, nem o andar 113, mas usam o andar 103. Assim, os primeiros andares são numerados 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, . . .
Como o elevador espacial tem muitos andares, e eles precisam numerar todos os andares do elevador, os chineses pediram que você escrevesse um programa que, dado o andar, indica o número que deve ser atribuído a ele.
No entanto, os chineses são muito supersticiosos, e por isso têm um cuidado muito especial com a numeração dos andares do elevador: eles não usam nenhum número que contenha o dígito “4” ou a sequência de dígitos “13”. Assim, eles não usam o andar 4, nem o andar 13, nem o andar 134, nem o andar 113, mas usam o andar 103. Assim, os primeiros andares são numerados 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, . . .
Como o elevador espacial tem muitos andares, e eles precisam numerar todos os andares do elevador, os chineses pediram que você escrevesse um programa que, dado o andar, indica o número que deve ser atribuído a ele.
Entrada
Cada caso de teste consiste de uma única linha, contendo um inteiro N (1 ≤ N ≤ 1018) que indica o andar cujo número deve ser determinado.
Saída
Para cada caso de teste, imprima uma linha contendo um único número inteiro indicando o número atribuído ao N-ésimo andar.
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long llu;
const int MAXN = 21;
llu dp[MAXN][2][2];
bool vis[MAXN][2][2];
vector<int> digits;
llu solve(int pos,int flag,int ultimo){
if(vis[pos][flag][ultimo]) return dp[pos][flag][ultimo];
if(pos == digits.size() - 1){
llu tot = 0;
int limite = (flag) ? (digits[pos]) : 9;
for(int i = 0;i<=limite;i++){
if(i == 4 || (i == 3 && ultimo)) continue;
tot += 1;
}
vis[pos][flag][ultimo] = true;
return dp[pos][flag][ultimo] = tot;
}
else{
llu tot = 0;
int limite = (flag) ? (digits[pos]) : 9;
for(int i = 0;i<=limite;i++){
if(i == 4 || (i == 3 && ultimo)) continue;
tot += solve(pos + 1, (flag) && (i == limite), (i == 1));
}
vis[pos][flag][ultimo] = true;
return dp[pos][flag][ultimo] = tot;
}
}
llu utilidade(llu val){
digits.clear();
memset(vis,false,sizeof(vis));
while(val != 0){
digits.push_back(val % 10);
val /= 10;
}
reverse(digits.begin(),digits.end());
return solve(0,1,0) - 1;
}
int main(){
cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
llu x;
while(cin >> x){
llu ini = 1, fim = 9330720600916705819LLU, meio,resp = 1;
while(ini <= fim){
meio = ini + (fim - ini)/2;
if(utilidade(meio) >= x){
resp = meio;
fim = meio - 1;
}
else{
ini = meio + 1;
}
}
cout << resp << endl;
}
return 0;
}
0 Comentários