A computer's real numbers are binary fractions.
In a binary fraction, the first place after the point means 1/2, the second 1/4, and the third 1/8.
For example, the decimal 0.375 is 1/4 + 1/8, so in binary it is 0.011.
Some numbers, such as 0.1, go on forever when written in binary.
You are given n decimal numbers that are at least 0 and less than 1.
Take each number as exactly the value written, and print it as a binary fraction.
If the binary fraction ends, write all of it up to the last 1, even when it has more than 20 places.
If it does not end, write only the first 20 places after the point and put ... right after them. Cut it off without rounding.
If the value is 0, write just 0.
Input
The first line has n (1 ≤ n ≤ 1,000). Each of the next n lines has one number. A number is 0. followed by 1 to 60 digits. It may end with zeros
Output
One line per number, in the order given. A binary fraction starts with 0.
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
Multiply the fraction by 2: if it reaches 1 the binary digit is 1, otherwise 0. 0.375 goes 0.75 (0), 1.5 (1), 1.0 (1), so it is 0.011. The solutions in all eight languages read the number as a string, keep the decimal digits one by one, and double them the way you would by hand. The carry that leaves the top is the next binary digit. Trap one: once you read it as a float, it is already a different number. If you read 0.1 as a float and double it until it reaches 0, the third line of the first example ends after 55 places as 0.0001100110011001100110011001100110011001100110011001101. That is because the float holds 0.1000000000000000055511151231257827021181583404541015625 rather than 0.1. The first line of the second example is exactly that number, so its answer has 55 places. Trap two: nearby numbers collapse into one float. 0.500000000000000000001 in the second example becomes equal to 0.5 when read as a float, so the output is 0.1. Python float, JS Number, C strtod, Java Double.parseDouble, C# double.Parse and Craykon ToNumber all say this number equals 0.5. Trap three: reading the digits after the point as one integer fails too. With up to 60 digits it does not fit in a 64-bit integer, and JS Number loses the low digits from about 16 digits on, so the first line of the second example becomes 0.00011001100110011001.... Trap four: do not decide that it never ends after only 20 doublings. A number with d digits after the point, if it ends, ends within d places, so you have to go that far. The fourth line of the second example ends at place 21. Trap five: filling 20 places does not mean it never ends. The third line of the second example ends at exactly place 20, so it gets no .... Trap six: 0.0 has no binary digits at all. Print 0, not 0.. The same thing happens when floats are added. 0.1 + 0.2 == 0.3 is false in all eight languages. Printing the sum as it is shows 0.30000000000000004 in Python, JS, Java and C#, and 0.3 with C %g, C++ cout and Craykon. Even when what you see is the same, the value is not. When you need exact numbers, build them from a string, as in Python Fraction("0.1") or Java new BigDecimal("0.1"). Fraction(0.1) is 3602879701896397/36028797018963968 and new BigDecimal(0.1) is the 55-digit number above. C# decimal makes 0.1m + 0.2m == 0.3m true, but it holds only about 28 digits, so decimal.Parse rounds away the rest of the numbers in this problem.
Pythonmain.py · 38 lines
import sysSHOWN = 20 # 딱 떨어지지 않을 때 보여 줄 이진 자리 수def to_binary(frac): """소수점 아래 십진 숫자열 frac을 이진 소수로 바꾼다.""" # 실수로 바꾸지 않고 십진 숫자를 하나씩 수로 담는다. 끝의 0은 값에 상관없으니 뗀다 digits = [int(ch) for ch in frac.rstrip("0")] limit = max(len(digits), SHOWN) # d자리 소수가 딱 떨어진다면 d번 안에 끝난다 bits = [] while digits and len(bits) < limit: # 2를 곱한다: 손으로 하듯 맨 끝자리부터 올림을 넘겨 간다 carry = 0 for i in range(len(digits) - 1, -1, -1): v = digits[i] * 2 + carry digits[i] = v % 10 carry = v // 10 bits.append(str(carry)) # 소수점 위로 넘어간 올림이 다음 이진 자리다 while digits and digits[-1] == 0: digits.pop() if not bits: return "0" if not digits: return "0." + "".join(bits) return "0." + "".join(bits[:SHOWN]) + "..."def main(): lines = sys.stdin.read().split() n = int(lines[0]) out = [] for x in lines[1:1 + n]: out.append(to_binary(x[2:])) # 맨 앞의 "0."을 뗀다 print("\n".join(out))main()
JavaScriptmain.js · 28 lines
const lines = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const SHOWN = 20; // 딱 떨어지지 않을 때 보여 줄 이진 자리 수function toBinary(frac) { // Number로 바꾸지 않고 십진 숫자를 하나씩 수로 담는다. 끝의 0은 값에 상관없으니 뗀다 const digits = [...frac.replace(/0+$/, "")].map(Number); const limit = Math.max(digits.length, SHOWN); // d자리 소수가 딱 떨어진다면 d번 안에 끝난다 let bits = ""; while (digits.length > 0 && bits.length < limit) { // 2를 곱한다: 맨 끝자리부터 올림을 넘겨 간다 let carry = 0; for (let i = digits.length - 1; i >= 0; i--) { const v = digits[i] * 2 + carry; digits[i] = v % 10; carry = Math.floor(v / 10); } bits += carry; // 소수점 위로 넘어간 올림이 다음 이진 자리다 while (digits.length > 0 && digits[digits.length - 1] === 0) digits.pop(); } if (bits === "") return "0"; if (digits.length === 0) return "0." + bits; return "0." + bits.slice(0, SHOWN) + "...";}const n = Number(lines[0]);const out = [];for (let i = 1; i <= n; i++) out.push(toBinary(lines[i].slice(2))); // 맨 앞의 "0."을 뗀다console.log(out.join("\n"));
TypeScriptmain.ts · 28 lines
const lines: string[] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const SHOWN = 20; // 딱 떨어지지 않을 때 보여 줄 이진 자리 수function toBinary(frac: string): string { // number로 바꾸지 않고 십진 숫자를 하나씩 수로 담는다. 끝의 0은 값에 상관없으니 뗀다 const digits: number[] = [...frac.replace(/0+$/, "")].map(Number); const limit = Math.max(digits.length, SHOWN); // d자리 소수가 딱 떨어진다면 d번 안에 끝난다 let bits = ""; while (digits.length > 0 && bits.length < limit) { // 2를 곱한다: 맨 끝자리부터 올림을 넘겨 간다 let carry = 0; for (let i = digits.length - 1; i >= 0; i--) { const v = digits[i] * 2 + carry; digits[i] = v % 10; carry = Math.floor(v / 10); } bits += carry; // 소수점 위로 넘어간 올림이 다음 이진 자리다 while (digits.length > 0 && digits[digits.length - 1] === 0) digits.pop(); } if (bits === "") return "0"; if (digits.length === 0) return "0." + bits; return "0." + bits.slice(0, SHOWN) + "...";}const n: number = Number(lines[0]);const out: string[] = [];for (let i = 1; i <= n; i++) out.push(toBinary(lines[i].slice(2))); // 맨 앞의 "0."을 뗀다console.log(out.join("\n"));
JavaMain.java · 41 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static final int SHOWN = 20; // 딱 떨어지지 않을 때 보여 줄 이진 자리 수 static String toBinary(String frac) { // double이나 long으로 바꾸지 않고 십진 숫자를 하나씩 배열에 담는다 int len = frac.length(); while (len > 0 && frac.charAt(len - 1) == '0') len--; // 끝의 0은 값에 상관없으니 뗀다 int[] digits = new int[len]; for (int i = 0; i < len; i++) digits[i] = frac.charAt(i) - '0'; int limit = Math.max(len, SHOWN); // d자리 소수가 딱 떨어진다면 d번 안에 끝난다 StringBuilder bits = new StringBuilder(); while (len > 0 && bits.length() < limit) { // 2를 곱한다: 맨 끝자리부터 올림을 넘겨 간다 int carry = 0; for (int i = len - 1; i >= 0; i--) { int v = digits[i] * 2 + carry; digits[i] = v % 10; carry = v / 10; } bits.append(carry); // 소수점 위로 넘어간 올림이 다음 이진 자리다 while (len > 0 && digits[len - 1] == 0) len--; } if (bits.length() == 0) return "0"; if (len == 0) return "0." + bits; return "0." + bits.substring(0, SHOWN) + "..."; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) { out.append(toBinary(br.readLine().trim().substring(2))).append('\n'); // 맨 앞의 "0."을 뗀다 } System.out.print(out); }}
C#Main.cs · 45 lines
using System;using System.Text;class Program{ const int Shown = 20; // 딱 떨어지지 않을 때 보여 줄 이진 자리 수 static string ToBinary(string frac) { // double이나 decimal로 바꾸지 않고 십진 숫자를 하나씩 배열에 담는다 frac = frac.TrimEnd('0'); // 끝의 0은 값에 상관없으니 뗀다 int len = frac.Length; int[] digits = new int[len]; for (int i = 0; i < len; i++) digits[i] = frac[i] - '0'; int limit = Math.Max(len, Shown); // d자리 소수가 딱 떨어진다면 d번 안에 끝난다 var bits = new StringBuilder(); while (len > 0 && bits.Length < limit) { // 2를 곱한다: 맨 끝자리부터 올림을 넘겨 간다 int carry = 0; for (int i = len - 1; i >= 0; i--) { int v = digits[i] * 2 + carry; digits[i] = v % 10; carry = v / 10; } bits.Append(carry); // 소수점 위로 넘어간 올림이 다음 이진 자리다 while (len > 0 && digits[len - 1] == 0) len--; } if (bits.Length == 0) return "0"; if (len == 0) return "0." + bits; return "0." + bits.ToString(0, Shown) + "..."; } static void Main() { int n = int.Parse(Console.ReadLine()); var sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.Append(ToBinary(Console.ReadLine().Trim().Substring(2))).Append('\n'); // 맨 앞의 "0."을 뗀다 } Console.Write(sb); }}
C++main.cpp · 43 lines
#include <algorithm>#include <iostream>#include <string>#include <vector>using namespace std;const size_t SHOWN = 20; // 딱 떨어지지 않을 때 보여 줄 이진 자리 수string toBinary(const string& frac) { // double로 바꾸지 않고 십진 숫자를 하나씩 수로 담는다 vector<int> digits; for (char ch : frac) digits.push_back(ch - '0'); while (!digits.empty() && digits.back() == 0) digits.pop_back(); // 끝의 0은 값에 상관없으니 뗀다 size_t limit = max(digits.size(), SHOWN); // d자리 소수가 딱 떨어진다면 d번 안에 끝난다 string bits; while (!digits.empty() && bits.size() < limit) { // 2를 곱한다: 맨 끝자리부터 올림을 넘겨 간다 int carry = 0; for (size_t i = digits.size(); i-- > 0;) { int v = digits[i] * 2 + carry; digits[i] = v % 10; carry = v / 10; } bits += static_cast<char>('0' + carry); // 소수점 위로 넘어간 올림이 다음 이진 자리다 while (!digits.empty() && digits.back() == 0) digits.pop_back(); } if (bits.empty()) return "0"; if (digits.empty()) return "0." + bits; return "0." + bits.substr(0, SHOWN) + "...";}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { string x; cin >> x; cout << toBinary(x.substr(2)) << '\n'; // 맨 앞의 "0."을 뗀다 } return 0;}
Cmain.c · 40 lines
#include <stdio.h>#include <string.h>#define SHOWN 20 /* 딱 떨어지지 않을 때 보여 줄 이진 자리 수 */int main(void) { int n; if (scanf("%d", &n) != 1) return 0; for (int t = 0; t < n; t++) { char x[80]; if (scanf("%79s", x) != 1) return 0; /* double이 아니라 문자열로 읽는다 */ const char *frac = x + 2; /* 맨 앞의 "0."을 건너뛴다 */ int len = (int)strlen(frac); while (len > 0 && frac[len - 1] == '0') len--; /* 끝의 0은 값에 상관없으니 뗀다 */ int digits[64]; for (int i = 0; i < len; i++) digits[i] = frac[i] - '0'; int limit = len > SHOWN ? len : SHOWN; /* d자리 소수가 딱 떨어진다면 d번 안에 끝난다 */ char bits[64]; int count = 0; while (len > 0 && count < limit) { /* 2를 곱한다: 맨 끝자리부터 올림을 넘겨 간다 */ int carry = 0; for (int i = len - 1; i >= 0; i--) { int v = digits[i] * 2 + carry; digits[i] = v % 10; carry = v / 10; } bits[count++] = (char)('0' + carry); /* 소수점 위로 넘어간 올림이 다음 이진 자리다 */ while (len > 0 && digits[len - 1] == 0) len--; } if (count == 0) { printf("0\n"); } else if (len == 0) { printf("0.%.*s\n", count, bits); } else { printf("0.%.*s...\n", SHOWN, bits); } } return 0;}
Craykonmain.cray · 50 lines
보일자리 = 20; // 딱 떨어지지 않을 때 보여 줄 이진 자리 수이진으로(소수부){ // 수로 한꺼번에 바꾸지 않고 십진 숫자를 하나씩 목록에 담는다 숫자들 = NewList(0, 0); for (i = 0; i < 소수부.Length; i++) { 숫자들.Add(소수부.Substring(i, 1).ToNumber()); } // 끝의 0은 값에 상관없으니 뗀다 while (숫자들.Count > 0 && 숫자들[숫자들.Count - 1] == 0) { 숫자들.RemoveAt(숫자들.Count - 1); } 한도 = Mathf.Max(숫자들.Count, 보일자리); // d자리 소수가 딱 떨어진다면 d번 안에 끝난다 비트 = ""; while (숫자들.Count > 0 && 비트.Length < 한도) { // 2를 곱한다: 맨 끝자리부터 올림을 넘겨 간다 올림 = 0; for (i = 숫자들.Count - 1; i >= 0; i--) { v = 숫자들[i] * 2 + 올림; 숫자들[i] = v % 10; 올림 = Mathf.Quot(v, 10); } 비트 = 비트 + 올림; // 소수점 위로 넘어간 올림이 다음 이진 자리다 while (숫자들.Count > 0 && 숫자들[숫자들.Count - 1] == 0) { 숫자들.RemoveAt(숫자들.Count - 1); } } if (비트 == "") { return "0"; } if (숫자들.Count == 0) { return "0." + 비트; } return "0." + 비트.Substring(0, 보일자리) + "...";}n = Console.ReadLine().ToNumber();for (t = 0; t < n; t++){ x = Console.ReadLine().Trim(); Console.WriteLine(이진으로(x.Substring(2))); // 맨 앞의 "0."을 뗀다}