Skew Binary
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 5765 | Accepted: 3669 |
Description
When a number is expressed in decimal, the kth digit represents a multiple of 10k
. (Digits are numbered from right to left, where the least significant digit is number 0.) For example,
81307(10) = 8 * 10^4 + 1 * 10 ^3 + 3 * 10^2 + 0 * 10^1 + 7 * 10^0
= 80000 + 1000 + 300 + 0 + 7
= 81307.
When a number is expressed in binary, the kth digit represents a multiple of 2^k . For example,
10011(2) = 1 * 2^4 + 0 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0
= 16 + 0 + 0 + 2 + 1
= 19.
In skew binary, the kth digit represents a multiple of 2^(k+1)-1. The only possible digits are 0 and 1, except that the least-significant nonzero digit can be a 2. For example,
10120(skew) = 1 * (2^5-1) + 0 * (2^4-1) + 1 * (2^3-1) + 2 * (2^2-1) + 0 * (2^1-1)
= 31 + 0 + 7 + 6 + 0
= 44.
The first 10 numbers in skew binary are 0, 1, 2, 10, 11, 12, 20, 100, 101, and 102. (Skew binary is useful in some applications because it is possible to add 1 with at most one carry. However, this has nothing to do with the current problem.)
81307(10) = 8 * 10^4 + 1 * 10 ^3 + 3 * 10^2 + 0 * 10^1 + 7 * 10^0
= 80000 + 1000 + 300 + 0 + 7
= 81307.
When a number is expressed in binary, the kth digit represents a multiple of 2^k . For example,
10011(2) = 1 * 2^4 + 0 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0
= 16 + 0 + 0 + 2 + 1
= 19.
In skew binary, the kth digit represents a multiple of 2^(k+1)-1. The only possible digits are 0 and 1, except that the least-significant nonzero digit can be a 2. For example,
10120(skew) = 1 * (2^5-1) + 0 * (2^4-1) + 1 * (2^3-1) + 2 * (2^2-1) + 0 * (2^1-1)
= 31 + 0 + 7 + 6 + 0
= 44.
The first 10 numbers in skew binary are 0, 1, 2, 10, 11, 12, 20, 100, 101, and 102. (Skew binary is useful in some applications because it is possible to add 1 with at most one carry. However, this has nothing to do with the current problem.)
Input
The
input contains one or more lines, each of which contains an integer n.
If n = 0 it signals the end of the input, and otherwise n is a
nonnegative integer in skew binary.
Output
For each number, output the decimal equivalent. The decimal value of n will be at most 2^31-1 = 2147483647.
Sample Input
10120 200000000000000000000000000000 10 1000000000000000000000000000000 11 100 11111000001110000101101102000 0
Sample Output
44 2147483646 3 2147483647 4 7 1041110737
此题将Skew数字读取成一个字符串,然后倒序累加即可
import java.util.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); while(true) { String skew = cin.nextLine(); if(skew.equals("0")) break; int decimal = trans(skew); System.out.println(decimal); } } private static int trans(String skew) { int num = 0; int index = 0; for(int i = skew.length()-1; i>=0; i--) { int cnum = Integer.valueOf(skew.substring(i, i+1)); num += (Math.pow(2, index+1) - 1) * cnum; index++; } return num; } }
发表评论
-
POJ ACM习题【No.2328】
2009-07-05 19:43 898Guessing Game Time ... -
POJ ACM习题【No.3157】
2009-04-26 23:54 1634Java vs C++ Time Lim ... -
POJ ACM习题【No.2924】
2009-04-26 11:52 923Gauß in Elementary School ... -
POJ ACM习题【No.3176】
2009-04-26 10:53 1043Cow Bowling Time Lim ... -
POJ ACM习题【No.3173】
2009-04-25 23:30 902Parkside's Triangle ... -
POJ ACM习题【No.2845】
2009-04-25 22:25 121401000001 Time Limit: ... -
POJ ACM习题【No.2140】
2009-04-25 21:26 934Herd Sums Time Limit ... -
POJ ACM习题【No.1969】
2009-04-25 20:59 859Count on Canton Time ... -
POJ ACM习题【No.2840】
2009-04-25 19:24 1004Big Clock Time Limit ... -
POJ ACM习题【No.2521】
2009-04-24 22:41 847How much did the businessman l ... -
POJ ACM习题【No.1326】
2009-04-24 22:14 1010Mileage Bank Time Li ... -
POJ ACM习题【No.3325】
2009-04-24 21:15 1092ICPC Score Totalizer Software ... -
POJ ACM习题【No.2756】
2009-04-24 20:28 771Autumn is a Genius T ... -
POJ ACM习题【No.3062】
2009-04-24 20:10 808Celebrity jeopardy ... -
POJ ACM习题【No.1547】
2009-04-23 20:03 774Clay Bully Time Limi ... -
POJ ACM习题【No.1552】
2009-04-23 19:39 750Doubles Time Limit: ... -
POJ ACM习题【No.1007】
2009-04-23 19:24 849DNA Sorting Time Lim ... -
POJ ACM习题【No.2403】
2009-04-22 22:18 859Hay Points Time Limi ... -
POJ ACM习题【No.1862】
2009-04-22 20:12 700Stripies Time Limit: ... -
POJ ACM习题【No.3224】
2009-04-22 19:57 742Lab杯 Time Limit: 1 ...
相关推荐
方便大家有针对性地联系 祝大家AC愉快~
pojACM题目分类,便于各类型同学分别做题有所参考
相信大家在做poj上的题目的时候如果没有分类的话很迷茫吧....这里有一份目前比较全面的poj题目分类..
02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ题库使用指南.docx02.北大POJ...
acm数据结构总结.doc acm数据结构总结.doc
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
本文件是ACM里的一些题目的源码、原题和习题的分析及详细解答。欢迎各位下载
http://acm.pku.edu.cn/JudgeOnline/ acm的AC解题报告
POJ ACM 1015 Jury Compromise 两种解法 解题报告
西工大C语言POJ习题答案.docx
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
poj 2007 Scrambled Polygon.md
poj 1984 Navigation Nightmare.md
poj 3435 Sudoku Checker.md
poj 2900 Griddy Hobby.md
poj 2430 Lazy Cows.md
poj 3183 Stump Removal.md
poj 2403 Hay Points.md
poj 2941 Homogeneous Squares.md
poj 1313 Booklet Printing.md