어느 건물은 꺼리는 숫자가 하나라도 들어간 번호를 쓰지 않는다.
번호표는 1 이상의 정수 가운데, 십진법으로 적었을 때 꺼리는 숫자가 한 번도 나오지 않는 수다.
번호표를 작은 것부터 늘어놓고 1번째, 2번째, 3번째, … 로 차례를 센다.
예를 들어 꺼리는 숫자가 4 하나이면 번호표는 1, 2, 3, 5, 6, …, 13, 15, … 이고 4번째 번호표는 5다.
꺼리는 숫자가 0과 3, 4, 5, 6, 7, 8, 9이면 번호표는 1, 2, 11, 12, 21, 22, 111, … 이다.
명령은 두 가지다.
I k: k번째 번호표를 출력한다.
L x: 번호표 x가 몇 번째인지 출력한다.
입력
첫 줄에 꺼리는 숫자들이 작은 것부터 빈칸 없이 붙어서 주어진다. 꺼리는 숫자는 서로 다르고 1 ~ 8개다. 둘째 줄에 명령 수 q (1 ≤ q ≤ 1,000)가 주어진다. 이어지는 q줄에 명령이 한 줄에 하나씩, 명령 글자와 k 또는 x를 빈칸 하나로 띄워 주어진다. k는 정수이고 1 ≤ k ≤ 10^15 이다. x는 꺼리는 숫자가 들어 있지 않은 번호표이고, 그 차례는 10^15 이하다. x는 50자리까지 될 수 있다
출력
명령마다 한 줄씩, 명령 차례대로 출력한다. 쉼표 없이 숫자만 쓴다
예시 1 · stdin
4
6
I 3
I 4
I 9
I 13
L 50
I 81
stdout
3
5
10
15
36
100
예시 2 · stdin
03456789
7
I 2
I 3
I 6
I 7
L 2112
I 1000000000000000
L 2211122121222222121211211221112212111111111111111
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
쓰는 숫자가 b개이면 번호표는 b진법 수의 자릿값을 쓰는 숫자로 바꿔 적은 것이에요. 4만 빼면 9진법이고 자릿값 0 ~ 8이 숫자 0, 1, 2, 3, 5, 6, 7, 8, 9가 돼요. 첫 예시의 L 50은 자릿값이 4, 0이라 4 × 9 + 0 = 36이에요. 함정 하나: 0을 뺐다면 보통의 b진법이 아니에요. 자릿값이 1 ~ b인 '0 없는 b진법'이라서, 나머지가 0이면 자릿값 b를 쓰고 k에서 b를 뺀 뒤 나눠요. 윗자리에서 하나를 빌리는 셈이에요. 1과 2만 쓰는 둘째 예시에서 보통의 2진법으로 바꾸면 I 2가 2가 아니라 21이 되고, 빌리지 않고 그냥 나누면 12가 돼요. 함정 둘: 나머지는 낮은 자리부터 나와요. 뒤집지 않으면 첫 예시의 I 9가 10이 아니라 01이 돼요. 함정 셋: 번호표는 1부터예요. 0을 쓰는 건물에서도 0은 번호표가 아니라서 k를 그대로 b진법으로 바꿔요. k - 1을 바꾸면 첫 예시의 I 4가 5가 아니라 3이 돼요. 함정 넷: 번호표는 50자리까지라 수로 읽으면 안 돼요. JS Number(x)는 16자리쯤부터 아랫자리를 잃어서 둘째 예시의 마지막 줄이 틀려요. 풀이는 여덟 언어 모두 번호표를 문자열로 읽어 한 글자씩 봐요. 함정 다섯: 차례는 10^15까지라 32비트 int에 담으면 넘쳐요. Java에서 int에 모으면 둘째 예시의 마지막 줄이 -1530494977이 돼요. 풀이는 C·C++에서 long long, Java·C#에서 long을 써요. JS·TS number와 크레이콘 수는 2^53까지 정확해서 10^15는 괜찮고, Python 정수는 크기 제한이 없어요. 몫은 Python k // b, JS·TS Math.floor(k / b), Java·C#·C·C++ 정수끼리의 k / b, 크레이콘 수학.몫(k, b)예요. 숫자가 몇 번째 자릿값인지는 Python allowed.index(ch), JS·TS·Java indexOf, C# IndexOf, C strchr, C++ find, 크레이콘 자리찾기로 찾아요.
Pythonmain.py · 45 줄
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 줄
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 줄
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 줄
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 줄
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 줄
#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 줄
#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 줄
뺀숫자 = 콘솔.줄읽기().공백제거();// 쓰는 숫자를 작은 것부터 이어 붙인 문자열쓰는숫자 = "";반복 (d = 0; d <= 9; d++){ 만약 (!뺀숫자.있나(d + "")) { 쓰는숫자 = 쓰는숫자 + d; }}b = 쓰는숫자.길이;영있나 = 쓰는숫자.부분문자열(0, 1) == "0";번호표로(k){ 결과 = ""; 동안 (k > 0) { r = k % b; 만약 (영있나) { // 보통의 b진법 결과 = 쓰는숫자.부분문자열(r, 1) + 결과; k = 수학.몫(k, b); } 아니면 { // 0이 없는 b진법: 나머지 0은 자릿값 b로 치고 윗자리에서 하나를 빌린다 만약 (r == 0) { r = b; } 결과 = 쓰는숫자.부분문자열(r - 1, 1) + 결과; k = 수학.몫(k - r, b); } } 돌려주기 결과;}차례로(번호표){ k = 0; 반복 (i = 0; i < 번호표.길이; i++) { 값 = 쓰는숫자.자리찾기(번호표.부분문자열(i, 1)); 만약 (!영있나) { 값 += 1; } k = k * b + 값; } 돌려주기 k;}q = 콘솔.줄읽기().수로변환();반복 (i = 0; i < q; i++){ 칸 = 콘솔.줄읽기().나누기(" "); 만약 (칸[0] == "I") { 콘솔.쓰기(번호표로(칸[1].수로변환())); } 아니면 { // 번호표는 50자리까지라 수로 바꾸지 않고 문자열 그대로 본다 콘솔.쓰기(차례로(칸[1]) + ""); }}