📄 problem 1712.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0047)http://acm.zju.edu.cn/show_problem.php?pid=1712 -->
<HTML><HEAD><TITLE>Problem 1712</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2900.3157" name=GENERATOR></HEAD>
<BODY>
<CENTER><IMG src="Problem 1712.files/logo.gif" align=center></IMG></CENTER>
<HR>
<CENTER><FONT color=blue size=+2>Skew Binary</FONT></CENTER>
<HR>
<CENTER><FONT color=green>Time limit:</FONT> 1 Seconds <FONT
color=green>Memory limit: </FONT>32768K </FONT><BR><FONT
color=green>Total Submit:</FONT> 2159 <FONT color=green>Accepted
Submit:</FONT> 1486 </CENTER>
<HR>
When a number is expressed in decimal, the kth digit represents a multiple of 10
k. (Digits are numbered from right to left, where the least significant digit is
number 0.) For example,
<P>81307(10) = 8 * 10^4 + 1 * 10 ^3 + 3 * 10^2 + 0 * 10^1 + 7 * 10^0<BR>= 80000
+ 1000 + 300 + 0 + 7<BR>= 81307.</P>
<P>When a number is expressed in binary, the kth digit represents a multiple of
2^k . For example,</P>
<P>10011(2) = 1 * 2^4 + 0 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0<BR>= 16 + 0 + 0 +
2 + 1<BR>= 19.</P>
<P>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,</P>
<P>10120(skew) = 1 * (2^5-1) + 0 * (2^4-1) + 1 * (2^3-1) + 2 * (2^2-1) + 0 *
(2^1-1)<BR>= 31 + 0 + 7 + 6 + 0<BR>= 44.</P>
<P>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.)</P>
<P><BR><B>Input</B></P>
<P>The input file 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.</P>
<P><BR><B>Output </B></P>
<P>For each number, output the decimal equivalent. The decimal value of n will
be at most 2^31-1 = 2147483647.</P>
<P><BR><B>Sample Input</B></P>
<P>10120<BR>200000000000000000000000000000<BR>10<BR>1000000000000000000000000000000<BR>11<BR>100<BR>11111000001110000101101102000<BR>0</P>
<P><BR><B>Sample Output</B></P>
<P>44<BR>2147483646<BR>3<BR>2147483647<BR>4<BR>7<BR>1041110737<BR></P>
<HR>
<FONT color=green size=+1>Problem Source: </FONT><I>Mid-Central USA 1997</I>
<HR>
<CENTER><A href="http://acm.zju.edu.cn/submit.php?pid=1712">Submit</A>
<A href="http://acm.zju.edu.cn/list_problem.php?vol=8">Back</A>
<A
href="http://acm.zju.edu.cn/problem_status.php?pid=1712">Status</A> </CENTER>
<HR>
<CENTER>
<TABLE width="100%" border=0>
<TBODY>
<TR>
<TD align=right width="65%"><A href="http://acm.zju.edu.cn/"><FONT
color=red>Zhejiang University Online Judge</FONT></A> <A
href="http://acm.zju.edu.cn/"><FONT color=red>V1.0</FONT></A></TD>
<TD align=right width="35%"><A href="http://www.zzhang.cn/"><FONT
color=#ffffff
size=-3>Book</FONT></A></TD></TR></TBODY></TABLE></CENTER></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -