主题：第59次编程比赛----有趣的二进制
AntiMicrosoft [专家分：3740] 发布于 2007-08-06 17:50:00
开始时间: 2007年8月6日 晚6点
结束时间: 2007年8月8日 晚8点
提交代码方式: 直接回复本帖子
提交时间或者修改时间以论坛显示的时间为准
结束时间之后 回复的代码无效
结束时间之后 修改已提交的代码将视为主动退出比赛
[url=http://www.programfan.com/club/post-245722.html]对题目本身有疑问的在此提出[/url]
问题描述:
在一个k位补码表示的二进制数中，从0到k-1位是有效位，权值最大的有效
位(第k-1位)是 -2^(k-1)，其余的位中，第i位的权值是2^i (0 ≤ i < k-1).
举个例子，101 = -2^2 + 0 + 2^0 = -3，权值是负数的位被称为“n-bit”，
权值是正数的位被称为"p-bit"。
Prog-Fan是著名的程序设计论坛Programfan设计的一个二进制数字系统，每
一位都可以是正或者是负。举个例子，一个3位的Prog-Fan数字系统fan3，
假设第0位和第2位是正数，第1位是负数。 (110)fan3 = 2^2 - 2^1 + 0 = 3
现在你可以来尽情的体验一下Prog-Fan数字系统。给你一个k位Prog-Fan数字
系统fank，和一个整数(可能是正数，可能是负数)，你的任务是找出一种方
式用fank去表示这个整数。举个例子，在上面定义的那个fan3系统下，-1可
以表示为011 (0 - 2^1 + 2^0)，6在fan3系统下是不可以表示的。
输入:
所有的数据从标准输入读取，输出到标准输出。
输入的第一行有一个整数 t, (1 ≤ t ≤ 10)，代表你的程序接下来要处理的数
据的组数。
每一组数据由3行组成，
第1行是1个正整数k(1 ≤ k ≤ 64)。
第2行是一个长度为k的字符串，仅仅包含字符'p'和'n'，用来描述这个fank数
字系统，'p'表示对应的位为正，'n'表示对应的位为负。
第3行有一个整数N (-2^63 ≤ N < 2^63), 你要做的就是把这个数N用fank表示。
输出:
对于每一组数据，输出一行长度为k的01字符串，或者输出 Impossible。
假如N能用fank系统表示，输出这个k位的表示方法(k位的01序列)。
假如N不能用fank系统表示，输出Impossible。
每一个输出占一行。
输入样例:
5
3
nnn
0
3
pnn
1
6
nnpnpp
-2
1
p
-1
2
pp
-2
输出样例:
000
111
000110
Impossible
Impossible
要求:
运行环境为Linux(2.6.20 AMD64), 编译器:gcc 4.1.2
内存使用不能超过1G，一个测试用例运行时间不能超过10s
不能输出任何题目没有要求输出的东西，包括提示信息等。
提示:
64bit整型使用 long long, 不要用__int64，格式控制字符串使
用"%lld"，不要用"%I64d"
不用一次读入所有数据，每处理一组数据，输出一个解。
所有的输入都是正确的，不需要判错。
部分测试用例比较弱，即使是最慢的代码也不会超时，新手不要
放弃，给自己一个锻炼的机会。
代码框架示例(C语言):
[code=c]
int cases;
scanf("%d", &cases);
while(cases--){
.........//读入一组数据
.........//处理数据
.........//输出一个结果
}
[/code]
最后更新于：2007-08-06 17:55:00
回复列表 （共8个回复）
沙发
AntiMicrosoft [专家分：3740] 发布于 2007-08-06 17:57:00
参考代码:
[code=c]
/* 算法很简单，从最右一位利用奇偶性向左推导*/
#include <stdio.h>
int main( )
{
long long n;
int cases, k;
char pn[70];
scanf("%d", &cases);
while(cases--){
scanf("%d%s%lld", &k, pn, &n);
while(k--){
if(n&0x1){
n += (pn[k]=='p')?-1:1;
pn[k]='1';
}else pn[k]='0';
n /= 2;
}
puts(n?"Impossible":pn);
}
}
[/code]
板凳
crossbow [专家分：150] 发布于 2007-08-06 19:55:00
[code=c]#include <stdio.h>
int main(void)
{
int t;
scanf("%d", &t);
while (--t >= 0)
{
int n;
char s[65];
long long x;
scanf("%d%s%I64d", &n, s, &x);
while (--n >= 0)
{
if ((x & 1) == 0)
s[n] = '0';
else
{
if (s[n] == 'n')
x++;
else
x--;
s[n] = '1';
}
x >>= 1;
}
puts(x == 0 ? s : "Impossible");
}
return 0;
}[/code]
3 楼
flyee [专家分：340] 发布于 2007-08-06 23:08:00
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int t, k, ans[100];
long long n;
char fan[100];
cin >> t;
while( t-- ){
cin >> k >> fan >> n;
memset( ans, 0, sizeof(ans) );
for(int i=0; (n) && (i<k); i++){
if( n%2 == 0 ){
ans[i] = 0;
}else{
ans[i] = 1;
if( fan[k-i-1] == 'p' ){
n -= 1;
}else{
n += 1;
}
}
n /= 2;
}
if( n ){
cout << "Impossible";
}else{
for(int i=k-1;i>=0;i--){
cout << ans[i];
}
}
cout << endl;
}
return 0;
}
4 楼
小黑骑DK [专家分：610] 发布于 2007-08-07 11:32:00
//不知道为什么在VS2003里，我不能从键盘读取long long型的值。
//不知道代码有没有错 ？
#include <stdio.h>
#include <string.h>
int get_p(int charNum,char *pFank, long long *p, int *pPos);
int get_n(int charNum,char *pFank, long long *p, int *pPos);
int get_diff(long long num, char *pDiff);
void print(char *p, int num);
int main(void)
{
int dataNum;
int charNum;
char fank[64];
long long Num;//前四个都是要读取的数据
char result[64] = {0};//记录结果
char diff[64] = {0};//记录差值
long long p[64] = {0};
int pPos[64] = {0};
int pEnd,diffEnd;
int i;
long long sum;
scanf("%d",&dataNum);
while (dataNum--)
{
scanf("%d",&charNum);
scanf("%s",fank);
scanf("%lld",&Num);
charNum -= 1;
if (Num == 0)
{
print(result,charNum);
memset(result,0,64);
continue;
}
else if (Num < 0)
{
pEnd = get_n(charNum,fank,p,pPos);
Num = 0 - Num;
}
else
{
pEnd = get_p(charNum,fank,p,pPos);
}
for (sum=0,i=pEnd; i>=0&&sum<Num; i--)
{
result[pPos[i]] = 1;
sum += p[i];
}
if (sum < Num)
{
printf("Impossible\n");
}
else
{
sum -= Num;
diffEnd = get_diff(sum,diff);
for (i=0; i<diffEnd; i++)
{
if (diff[i] == result[i])
{
result[i] = 0;
}
else
{
result[i] = 1;
}
}
print(result,charNum);
}
memset(result,0,64);
}
return 0;
}
int get_p(int charNum,char *pFank, long long *p, int *pPos)
{
int pIndex = 0;
for (int i=0; i<=charNum; i++)
{
if (pFank[i] == 'p')
{
p[pIndex] = 1<<(charNum-i);
pPos[pIndex++] = charNum-i;
}
}
return pIndex-1;
}
int get_n(int charNum,char *pFank, long long *p, int *pPos)
{
int pIndex = 0;
for (int i=0; i<=charNum; i++)
{
if (pFank[i] == 'n')
{
p[pIndex] = 1<<(charNum-i);
pPos[pIndex++] = charNum-i;
}
}
return pIndex-1;
}
int get_diff(long long num, char *pDiff)
{
int i = 0;
while (num)
{
pDiff[i++] = (char)num%2;
num /= 2;
}
return i;
}
void print(char *p, int num)
{
while (num > -1)
{
printf("%c",p[num--]+'0');
}
printf("\n");
}
5 楼
nwpuzhl [专家分：0] 发布于 2007-08-07 14:32:00
[code=c]
#include <stdio.h>
#include <string.h>
#define N 65
int k;
long long number;
char str[N],answer[N];
int solve();
int main() {
int i,test;
scanf("%d",&test);
for(i=0;i<test;i++) {
scanf("%d%s%lld",&k,str,&number);
solve();
}
return 0;
}
int solve() {
int i=0,m,j=0;
long long temp=number;
memset(answer,0,sizeof(answer));
for(i=k-1,j=0;i>-1;i--) {
m=temp&1;
if(m) {
if(str[i]=='n')
temp=(temp+1)/2;
else
temp=(temp-1)/2;
answer[i]='1';
}
else {
answer[i]='0';
temp=temp/2;
}
}
if(temp)
printf("Impossible\n");
else
printf("%s\n",answer);
return 0;
}[/code]
6 楼
vfdff [专家分：740] 发布于 2007-08-07 23:29:00
还 不是 很明白 ，对于理论应多介绍些
7 楼
cocu31 [专家分：0] 发布于 2007-08-07 23:40:00
#include <stdio.h>
#include <string.h>
int fank(int , char *, long);
int main()
{
int i;
int t;
int k;
char buf[64];
long N;
memset(buf, '\0', 64);
scanf("%d", &t);
for(i=0; i<t; i++)
{
scanf("%d",&k);
scanf("%s", buf);
scanf("%ld", &N);
fank(k, buf, N);
memset(buf, '\0', 64);
}
return 0;
}
int fank(int k, char b[], long n)
{
long i;
long i_tmp;
int j=0;
int m=0;
int len;
int pow_tmp;
long total=0;
int flag=0;
char a[64];
char tmp[64];
len=strlen(b);
memset(a, '0', 64);
memset(tmp, '0', 64);
for(i=0;i<(1<<k);i++)
{
j=0;
total=0;
i_tmp=i;
memset(tmp, '0', 64);
while(i_tmp!=0)
{
tmp[j]=i_tmp%2+'0';
i_tmp=i_tmp/2;
j++;
}
for(m=0;m<len;m++)
{
a[m]=tmp[len-m-1];
}
a[m]='\0';
for(m=0;m<len;m++)
{
pow_tmp=len-m-1;
if(b[m]=='p')
total=total+(1<<pow_tmp)*(a[m]-'0');
else
total=total-(1<<pow_tmp)*(a[m]-'0');
}
if(total == n)
{
flag=1;
printf("%s\n",a);
break;
}
}
if(flag==0)
printf("Impossible\n");
return 0;
}
8 楼
zhangc511 [专家分：310] 发布于 2007-08-08 00:36:00
//不知道有没有long long 型数，我在linux下没试出long long型，在vc里也没有，
//所以，就用long 型代替。
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
int main()
{
int cases,k;
char *str,*str1;
int *data,*data1;
long min,max,n;
int i;
scanf("%d", &cases);
while(cases--)
{
min=max=0;
scanf("%d",&k);
str=(char*)malloc((k+1)*sizeof(char));
scanf("%s",str);
scanf("%d",&n);//读入一组数据
str1=str;
data=(int *)malloc(k*sizeof(int));
i=k-1;
while(*str1!='\0')
{
if(*str1=='n')
{
min-=1<<i;
data[i]=0;
}
else {
max+=1<<i;
data[i]=1;
}
i--;
str1++;
}
if(n>max||n<min)
{
printf("Impossible");
}
else
{
n=max-n;
data1=(int *)malloc(sizeof(int)*k);
for(i=0;i<k;i++)
{
data1[i]=n%2;
n=n/2;
}
for(i=k-1;i>=0;i--)
{
if(data1[i]==1)
data[i]=1-data[i];
printf("%d",data[i]);
}
free(data1);
}
putchar('\n');
free(str);
free(data);
}
while(1);
return 0;
}
我来回复
您所在位置：