A base-b abacus shows a number by putting from 0 to b - 1 beads on each place.
The number of beads needed to put a number on a base-b abacus is the sum of all its digits when the number is written in base b.
For example, 10 is 1010 in base 2, which takes 2 beads, and 10 in base 10, which takes 1 bead.
You are given q questions. Each question has a number n and the bases of k abacuses.
For each question, print the base of the abacus that needs the fewest beads to show n, and that number of beads.
If several abacuses need the fewest beads, choose the one written first in the input among them.
Try solving it by writing one function that takes a number and a base and returns the number of beads, and calling it for every abacus. Grading only looks at the output, though, so it cannot check that you wrote a function.
Input
The first line has q. Each of the next q lines has one question: n, k and then the k bases, separated by one space. 1 ≤ q ≤ 1,000, 1 ≤ n ≤ 1,000,000,000,000,000 (10 to the power 15), 1 ≤ k ≤ 8, and a base is an integer from 2 to 1,000; the same base may be written more than once
Output
For each question print on one line the base of the chosen abacus and its number of beads, separated by one space
Example 1 · stdin
3
10 3 2 3 10
5 2 4 2
10000000000 2 7 10
stdout
10 1
4 2
10 1
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
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
The shape of a function definition differs by language. Python writes def beads(n, b):, JS writes function beads(n, b) { }, and TS adds n: number and the return type. Java and C# write every type inside a class, as in static int beads(long n, int b), and C and C++ also write the types. Craykon writes only the name and the parameters: beads(n, b) { … return total; }. The order of definition and call differs too. In C the function or its prototype (int beads(long long n, int b);) must appear above the call. Without it gcc 14 and clang report a compile error, while gcc 11 only warns and goes on. Python stops with NameError if you call before the def has run. A JS function declaration and a Craykon function can be called from above even when written below, but a JS function made with const beads = (n, b) => … gives ReferenceError when called before that line. When a number is passed as a parameter, all eight languages copy the value, so dividing n down to 0 inside the function leaves the caller's n untouched. Trap one: in C++, writing the parameter as long long& n makes it the caller's n itself, not a copy. The first call turns n into 0, and the first line of the example becomes 3 0 instead of 10 1. Trap two: n does not fit in a 32-bit integer. In C a parameter written as int n silently cuts the value when it is passed, and the third line of the example becomes 10 29. Java and C# report a compile error when a long is passed to an int parameter. Trap three: if the variable holding the sum lives outside the function, its value stays after the call ends. The next call keeps adding to the earlier sum, and the first line of the example becomes 2 2. Make a new variable that starts at 0 inside the function. Trap four: comparing with <= when the bead counts are equal switches to the abacus written later. The second line of the example becomes 2 2 instead of 4 2. JS/TS have no integer division operator, so the solution subtracts the remainder before dividing ((n - n % b) / b). Python uses // and Craykon uses Mathf.Quot.
Pythonmain.py · 26 lines
import sysdef beads(n, b): """n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)""" total = 0 while n > 0: total += n % b n //= b # 매개변수 n만 줄어든다. 부른 쪽의 수는 그대로다 return totallines = sys.stdin.read().split("\n")q = int(lines[0])out = []for line in lines[1:q + 1]: nums = list(map(int, line.split())) n, bases = nums[0], nums[2:] best_base = bases[0] best = beads(n, best_base) for b in bases[1:]: count = beads(n, b) if count < best: # 같으면 먼저 적힌 주판을 그대로 둔다 best, best_base = count, b out.append(f"{best_base} {best}")print("\n".join(out))
JavaScriptmain.js · 30 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const out = [];for (let i = 1; i <= q; i++) { const nums = lines[i].trim().split(" ").map(Number); const n = nums[0]; let bestBase = nums[2]; let best = beads(n, bestBase); // function 선언은 끌어올려져서 정의보다 먼저 부를 수 있다 for (let j = 3; j < nums.length; j++) { const count = beads(n, nums[j]); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = nums[j]; } } out.push(`${bestBase} ${best}`);}console.log(out.join("\n"));// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)function beads(n, b) { let total = 0; while (n > 0) { const digit = n % b; total += digit; n = (n - digit) / b; // JS의 /는 소수를 내므로 나머지를 먼저 뺀다 } return total;}
TypeScriptmain.ts · 32 lines
import { readFileSync } from "node:fs";// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)function beads(n: number, b: number): number { let total = 0; while (n > 0) { const digit: number = n % b; total += digit; n = (n - digit) / b; // TS의 /는 소수를 내므로 나머지를 먼저 뺀다 } return total;}const lines: string[] = readFileSync(0, "utf8").split("\n");const q: number = Number(lines[0]);const out: string[] = [];for (let i = 1; i <= q; i++) { const nums: number[] = lines[i].trim().split(" ").map(Number); const n: number = nums[0]; let bestBase: number = nums[2]; let best: number = beads(n, bestBase); for (let j = 3; j < nums.length; j++) { const count: number = beads(n, nums[j]); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = nums[j]; } } out.push(`${bestBase} ${best}`);}console.log(out.join("\n"));
JavaMain.java · 39 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { // n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합). n은 int에 담기지 않아 long이다 static int beads(long n, int b) { int total = 0; while (n > 0) { total += (int) (n % b); n /= b; } return total; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { StringTokenizer st = new StringTokenizer(in.readLine()); long n = Long.parseLong(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int bestBase = Integer.parseInt(st.nextToken()); int best = beads(n, bestBase); for (int j = 1; j < k; j++) { int b = Integer.parseInt(st.nextToken()); int count = beads(n, b); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = b; } } out.append(bestBase).append(' ').append(best).append('\n'); } System.out.print(out); }}
C#Main.cs · 42 lines
using System;using System.Text;class Program{ // n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합). n은 int에 담기지 않아 long이다 static int Beads(long n, int b) { int total = 0; while (n > 0) { total += (int)(n % b); n /= b; } return total; } static void Main() { int q = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] parts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long n = long.Parse(parts[0]); int bestBase = int.Parse(parts[2]); int best = Beads(n, bestBase); for (int j = 3; j < parts.Length; j++) { int b = int.Parse(parts[j]); int count = Beads(n, b); if (count < best) // 같으면 먼저 적힌 주판을 그대로 둔다 { best = count; bestBase = b; } } sb.Append(bestBase).Append(' ').Append(best).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 37 lines
#include <iostream>using namespace std;// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합).// n을 값으로 받으므로 여기서 줄여도 부른 쪽의 n은 그대로다int beads(long long n, int b) { int total = 0; while (n > 0) { total += (int)(n % b); n /= b; } return total;}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; for (int i = 0; i < q; i++) { long long n; int k, bestBase; cin >> n >> k >> bestBase; int best = beads(n, bestBase); for (int j = 1; j < k; j++) { int b; cin >> b; int count = beads(n, b); if (count < best) { // 같으면 먼저 적힌 주판을 그대로 둔다 best = count; bestBase = b; } } cout << bestBase << ' ' << best << '\n'; } return 0;}
Cmain.c · 36 lines
#include <stdio.h>/* 함수 원형: main보다 뒤에 정의하므로, 부르기 전에 생김새를 먼저 알려 준다 */int beads(long long n, int b);int main(void) { int q; scanf("%d", &q); for (int i = 0; i < q; i++) { long long n; int k, best_base; scanf("%lld %d %d", &n, &k, &best_base); int best = beads(n, best_base); for (int j = 1; j < k; j++) { int b; scanf("%d", &b); int count = beads(n, b); if (count < best) { /* 같으면 먼저 적힌 주판을 그대로 둔다 */ best = count; best_base = b; } } printf("%d %d\n", best_base, best); } return 0;}/* n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합) */int beads(long long n, int b) { int total = 0; while (n > 0) { total += (int)(n % b); n /= b; /* 값으로 받은 복사본만 줄어든다 */ } return total;}
Craykonmain.cray · 32 lines
q = Console.ReadLine().ToNumber();for (i = 0; i < q; i++){ nums = Console.ReadNumbers(); n = nums[0]; bestBase = nums[2]; // 함수는 아래에 정의했지만 먼저 부를 수 있다 best = beads(n, bestBase); for (j = 3; j < nums.Count; j++) { count = beads(n, nums[j]); // 같으면 먼저 적힌 주판을 그대로 둔다 if (count < best) { best = count; bestBase = nums[j]; } } Console.WriteLine(bestBase + " " + best);}// n을 b진법 주판에 올릴 때 드는 구슬 수(자리 숫자의 합)beads(n, b){ total = 0; while (n > 0) { total += n % b; n = Mathf.Quot(n, b); } return total;}