A building never uses a number that contains any of its avoided digits.
A label is an integer of 1 or more whose decimal form contains no avoided digit at all.
List the labels from smallest and count them as the 1st, 2nd, 3rd, and so on.
For example, if the only avoided digit is 4, the labels are 1, 2, 3, 5, 6, …, 13, 15, …, and the 4th label is 5.
If the avoided digits are 0 and 3, 4, 5, 6, 7, 8, 9, the labels are 1, 2, 11, 12, 21, 22, 111, ….
There are two commands.
I k: print the k-th label.
L x: print which place the label x has in the list.
Input
The first line has the avoided digits, from smallest, written together with no spaces. The avoided digits are distinct and there are 1 to 8 of them. The second line has the number of commands q (1 ≤ q ≤ 1,000). Each of the next q lines has one command: the command letter, one space, then k or x. k is an integer with 1 ≤ k ≤ 10^15. x is a label that contains no avoided digit, and its place is at most 10^15. x can have up to 50 digits
Output
One line per command, in command order. Write plain digits without commas
Example 1 · stdin
4
6
I 3
I 4
I 9
I 13
L 50
I 81
stdout
3
5
10
15
36
100
Example 2 · stdin
03456789
7
I 2
I 3
I 6
I 7
L 2112
I 1000000000000000
L 2211122121222222121211211221112212111111111111111
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
With b usable digits, a label is a base-b number whose digit values are written with the usable digits. Avoiding only 4 gives base 9, where digit values 0 to 8 become the digits 0, 1, 2, 3, 5, 6, 7, 8, 9. L 50 in the first example has digit values 4, 0, so it is 4 × 9 + 0 = 36. Trap one: if 0 is avoided, it is not ordinary base b. It is a "base b without zero" whose digit values are 1 to b, so when the remainder is 0 you use digit value b, subtract b from k, and then divide. This borrows one from the next place. In the second example, which uses only 1 and 2, ordinary base 2 turns I 2 into 21 instead of 2, and dividing without the borrow gives 12. Trap two: remainders come out from the lowest place. Without reversing, I 9 in the first example gives 01 instead of 10. Trap three: labels start at 1. Even in a building that uses 0, the number 0 is not a label, so convert k itself to base b. Converting k - 1 turns I 4 of the first example into 3 instead of 5. Trap four: a label can have 50 digits, so do not read it as a number. JS Number(x) loses the low digits from about 16 digits on, and the last line of the second example comes out wrong. The solutions in all eight languages read the label as a string and look at one character at a time. Trap five: a place can be as large as 10^15, which overflows a 32-bit int. Accumulating it in a Java int gives -1530494977 on the last line of the second example. The solutions use long long in C/C++ and long in Java/C#. JS/TS number and Craykon numbers are exact up to 2^53, so 10^15 is fine, and Python integers have no size limit. The quotient is Python k // b, JS/TS Math.floor(k / b), k / b between integers in Java/C#/C/C++, and Craykon Mathf.Quot(k, b). To find which digit value a digit has: Python allowed.index(ch), JS/TS/Java indexOf, C# IndexOf, C strchr, C++ find, Craykon IndexOf.
Pythonmain.py · 45 lines
import sysdef main(): lines = sys.stdin.read().split("\n") banned = lines[0].strip() allowed = [d for d in "0123456789" if d not in banned] # 쓰는 숫자, 작은 것부터 b = len(allowed) has_zero = allowed[0] == "0" def to_label(k): digits = [] while k > 0: r = k % b if has_zero: # 보통의 b진법: 나머지 0 ~ b-1이 그대로 자릿값이다 digits.append(allowed[r]) k //= b else: # 0이 없는 b진법: 자릿값은 1 ~ b. 나머지 0은 자릿값 b로 치고 윗자리에서 하나를 빌린다 if r == 0: r = b digits.append(allowed[r - 1]) k = (k - r) // b return "".join(reversed(digits)) # 낮은 자리부터 나왔으니 뒤집는다 def to_index(label): k = 0 for ch in label: value = allowed.index(ch) if has_zero else allowed.index(ch) + 1 k = k * b + value return k q = int(lines[1]) out = [] for line in lines[2:2 + q]: kind, arg = line.split() if kind == "I": out.append(to_label(int(arg))) else: out.append(str(to_index(arg))) # 번호표는 수로 바꾸지 않고 문자열 그대로 본다 print("\n".join(out))main()
JavaScriptmain.js · 40 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const banned = lines[0].trim();const allowed = [..."0123456789"].filter((d) => !banned.includes(d)); // 쓰는 숫자, 작은 것부터const b = allowed.length;const hasZero = allowed[0] === "0";function toLabel(k) { const digits = []; while (k > 0) { let r = k % b; if (hasZero) { // 보통의 b진법 digits.push(allowed[r]); k = Math.floor(k / b); } else { // 0이 없는 b진법: 나머지 0은 자릿값 b로 치고 윗자리에서 하나를 빌린다 if (r === 0) r = b; digits.push(allowed[r - 1]); k = (k - r) / b; } } return digits.reverse().join("");}function toIndex(label) { let k = 0; for (const ch of label) { k = k * b + allowed.indexOf(ch) + (hasZero ? 0 : 1); } return k;}const q = Number(lines[1]);const out = [];for (let i = 2; i < 2 + q; i++) { const [kind, arg] = lines[i].split(" "); // 차례 번호는 10^15 이하라 Number로 정확하다. 번호표는 50자리까지라 문자열 그대로 본다 out.push(kind === "I" ? toLabel(Number(arg)) : String(toIndex(arg)));}console.log(out.join("\n"));
TypeScriptmain.ts · 40 lines
const lines: string[] = require("fs").readFileSync(0, "utf8").split("\n");const banned: string = lines[0].trim();const allowed: string[] = [..."0123456789"].filter((d) => !banned.includes(d)); // 쓰는 숫자, 작은 것부터const b: number = allowed.length;const hasZero: boolean = allowed[0] === "0";function toLabel(k: number): string { const digits: string[] = []; while (k > 0) { let r = k % b; if (hasZero) { // 보통의 b진법 digits.push(allowed[r]); k = Math.floor(k / b); } else { // 0이 없는 b진법: 나머지 0은 자릿값 b로 치고 윗자리에서 하나를 빌린다 if (r === 0) r = b; digits.push(allowed[r - 1]); k = (k - r) / b; } } return digits.reverse().join("");}function toIndex(label: string): number { let k = 0; for (const ch of label) { k = k * b + allowed.indexOf(ch) + (hasZero ? 0 : 1); } return k;}const q: number = Number(lines[1]);const out: string[] = [];for (let i = 2; i < 2 + q; i++) { const [kind, arg] = lines[i].split(" "); // 차례 번호는 10^15 이하라 number로 정확하다. 번호표는 50자리까지라 문자열 그대로 본다 out.push(kind === "I" ? toLabel(Number(arg)) : String(toIndex(arg)));}console.log(out.join("\n"));
JavaMain.java · 58 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static String allowed; // 쓰는 숫자, 작은 것부터 static int b; static boolean hasZero; static String toLabel(long k) { StringBuilder sb = new StringBuilder(); while (k > 0) { int r = (int) (k % b); if (hasZero) { // 보통의 b진법 sb.append(allowed.charAt(r)); k /= b; } else { // 0이 없는 b진법: 나머지 0은 자릿값 b로 치고 윗자리에서 하나를 빌린다 if (r == 0) r = b; sb.append(allowed.charAt(r - 1)); k = (k - r) / b; } } return sb.reverse().toString(); } static long toIndex(String label) { long k = 0; // 10^15까지라 int로는 모자란다 for (int i = 0; i < label.length(); i++) { k = k * b + allowed.indexOf(label.charAt(i)) + (hasZero ? 0 : 1); } return k; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String banned = br.readLine().trim(); StringBuilder a = new StringBuilder(); for (char d = '0'; d <= '9'; d++) { if (banned.indexOf(d) < 0) a.append(d); } allowed = a.toString(); b = allowed.length(); hasZero = allowed.charAt(0) == '0'; int q = Integer.parseInt(br.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { String[] parts = br.readLine().split(" "); if (parts[0].equals("I")) { out.append(toLabel(Long.parseLong(parts[1]))).append('\n'); } else { out.append(toIndex(parts[1])).append('\n'); } } System.out.print(out); }}
C#Main.cs · 64 lines
using System;using System.Text;class Program{ static string allowed = ""; // 쓰는 숫자, 작은 것부터 static int b; static bool hasZero; static string ToLabel(long k) { var digits = new StringBuilder(); while (k > 0) { int r = (int)(k % b); if (hasZero) { // 보통의 b진법 digits.Insert(0, allowed[r]); k /= b; } else { // 0이 없는 b진법: 나머지 0은 자릿값 b로 치고 윗자리에서 하나를 빌린다 if (r == 0) r = b; digits.Insert(0, allowed[r - 1]); k = (k - r) / b; } } return digits.ToString(); } static long ToIndex(string label) { long k = 0; // 10^15까지라 int로는 모자란다 foreach (char ch in label) { k = k * b + allowed.IndexOf(ch) + (hasZero ? 0 : 1); } return k; } static void Main() { string banned = Console.ReadLine().Trim(); var a = new StringBuilder(); for (char d = '0'; d <= '9'; d++) { if (banned.IndexOf(d) < 0) a.Append(d); } allowed = a.ToString(); b = allowed.Length; hasZero = allowed[0] == '0'; int q = int.Parse(Console.ReadLine()); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] parts = Console.ReadLine().Split(' '); if (parts[0] == "I") sb.Append(ToLabel(long.Parse(parts[1]))).Append('\n'); else sb.Append(ToIndex(parts[1])).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 57 lines
#include <algorithm>#include <iostream>#include <string>using namespace std;string allowed; // 쓰는 숫자, 작은 것부터int b;bool hasZero;string toLabel(long long k) { string digits; while (k > 0) { int r = static_cast<int>(k % b); if (hasZero) { // 보통의 b진법 digits += allowed[r]; k /= b; } else { // 0이 없는 b진법: 나머지 0은 자릿값 b로 치고 윗자리에서 하나를 빌린다 if (r == 0) r = b; digits += allowed[r - 1]; k = (k - r) / b; } } reverse(digits.begin(), digits.end()); return digits;}long long toIndex(const string& label) { long long k = 0; // 10^15까지라 int로는 모자란다 for (char ch : label) { k = k * b + static_cast<long long>(allowed.find(ch)) + (hasZero ? 0 : 1); } return k;}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string banned; cin >> banned; for (char d = '0'; d <= '9'; d++) { if (banned.find(d) == string::npos) allowed += d; } b = static_cast<int>(allowed.size()); hasZero = allowed[0] == '0'; int q; cin >> q; for (int i = 0; i < q; i++) { char kind; string arg; // 번호표는 50자리까지라 수가 아닌 문자열로 읽는다 cin >> kind >> arg; if (kind == 'I') cout << toLabel(stoll(arg)) << '\n'; else cout << toIndex(arg) << '\n'; } return 0;}
Cmain.c · 63 lines
#include <stdio.h>#include <string.h>static char allowed[11]; /* 쓰는 숫자, 작은 것부터 */static int b;static int has_zero;/* k번째 번호표를 out에 적는다 */static void to_label(long long k, char *out) { char rev[64]; int len = 0; while (k > 0) { int r = (int)(k % b); if (has_zero) { /* 보통의 b진법 */ rev[len++] = allowed[r]; k /= b; } else { /* 0이 없는 b진법: 나머지 0은 자릿값 b로 치고 윗자리에서 하나를 빌린다 */ if (r == 0) r = b; rev[len++] = allowed[r - 1]; k = (k - r) / b; } } for (int i = 0; i < len; i++) out[i] = rev[len - 1 - i]; out[len] = '\0';}static long long to_index(const char *label) { long long k = 0; /* 10^15까지라 int로는 모자란다 */ for (int i = 0; label[i] != '\0'; i++) { int value = (int)(strchr(allowed, label[i]) - allowed); k = k * b + value + (has_zero ? 0 : 1); } return k;}int main(void) { char banned[16]; if (scanf("%15s", banned) != 1) return 0; for (char d = '0'; d <= '9'; d++) { if (strchr(banned, d) == NULL) allowed[b++] = d; } allowed[b] = '\0'; has_zero = allowed[0] == '0'; int q; if (scanf("%d", &q) != 1) return 0; for (int i = 0; i < q; i++) { char kind; char arg[64]; /* 번호표는 50자리까지라 수가 아닌 문자열로 읽는다 */ if (scanf(" %c %63s", &kind, arg) != 2) return 0; if (kind == 'I') { long long k; char label[64]; sscanf(arg, "%lld", &k); to_label(k, label); printf("%s\n", label); } else { printf("%lld\n", to_index(arg)); } } return 0;}
Craykonmain.cray · 68 lines
뺀숫자 = Console.ReadLine().Trim();// 쓰는 숫자를 작은 것부터 이어 붙인 문자열쓰는숫자 = "";for (d = 0; d <= 9; d++){ if (!뺀숫자.Contains(d + "")) { 쓰는숫자 = 쓰는숫자 + d; }}b = 쓰는숫자.Length;영있나 = 쓰는숫자.Substring(0, 1) == "0";번호표로(k){ 결과 = ""; while (k > 0) { r = k % b; if (영있나) { // 보통의 b진법 결과 = 쓰는숫자.Substring(r, 1) + 결과; k = Mathf.Quot(k, b); } else { // 0이 없는 b진법: 나머지 0은 자릿값 b로 치고 윗자리에서 하나를 빌린다 if (r == 0) { r = b; } 결과 = 쓰는숫자.Substring(r - 1, 1) + 결과; k = Mathf.Quot(k - r, b); } } return 결과;}차례로(번호표){ k = 0; for (i = 0; i < 번호표.Length; i++) { 값 = 쓰는숫자.IndexOf(번호표.Substring(i, 1)); if (!영있나) { 값 += 1; } k = k * b + 값; } return k;}q = Console.ReadLine().ToNumber();for (i = 0; i < q; i++){ 칸 = Console.ReadLine().Split(" "); if (칸[0] == "I") { Console.WriteLine(번호표로(칸[1].ToNumber())); } else { // 번호표는 50자리까지라 수로 바꾸지 않고 문자열 그대로 본다 Console.WriteLine(차례로(칸[1]) + ""); }}