主题：第43次编程比赛第一题题目
thomas [专家分：180] 发布于 2006-10-01 09:15:00
PROBLEM:
N个1和N个0组成一个2N位的二进制数,要求从左到右扫描,1的累计数不小于0的累计数,试求满足这种条件的数的个数P
INPUT:
输入文件为:DATA1.IN
内有[color=FF0000]一个[/color]整数N(N<=100)
OUTPUT
输出文件为:ANS1.OUT
输出一个数P,P精确到个位,即输出所有数位
SAMPLE INPUT
3
SAMPLE OUTPUT
5
解释:
例如N=3时,P=5,为
111000
110100
110010
101010
101100
HINT:不要想复杂了[em2]
回复列表 （共19个回复）
沙发
thomas [专家分：180] 发布于 2006-09-30 19:32:00
test
板凳
lc1222 [专家分：0] 发布于 2006-09-30 20:31:00
有没有答案啊！
3 楼
yrqingpf [专家分：0] 发布于 2006-09-30 23:25:00
n
4 楼
liren0 [专家分：260] 发布于 2006-10-01 00:04:00
#include <stdio.h>
#define true 1
#define MAX 100
char data[MAX], n;
void next();
char comp();
int main()
{
int i, resu = 0, count = 0;
FILE *pf_in = NULL;
FILE *pf_out = NULL;
pf_in = fopen("DATA1.IN","r");
pf_out = fopen("ANS1.OUT","w");
if (pf_in == NULL || pf_out == NULL)
{
printf("打开文件失败!");
return 0;
}
fscanf(pf_in,"%d",&n);
for (i=n*2-1; i>=0; i--)
{
data[i] = i%2; /*高高低低存取*/
}
count++;
while (true)
{
next();
resu = comp();
if (resu == 0)
continue;
if (resu == 1)
{
count++;
continue;
}
if (resu == 2)
{
count++;
break;
}
}
fprintf(pf_out,"%d",count);
fclose(pf_in);
fclose(pf_out);
return 0;
}
void next()
{
int i = 0, j = 1, f_con = 0;
while (i < n * 2)
{
if (data[i] == 1) break;
i++;
}
while (i < n * 2)
{
if (data[i] == 1)
{
data[i] = 0;
f_con++;
}
else
{
data[i] = 1;
f_con--;
break;
}
i++;
}
while (f_con > 0)
{
data[j] = 1;
j += 2;
f_con--;
}
}
char comp()
{
int con_i = 0, con_j = 0, k = 2 * n - 1;
while (k>=0)
{
data[k] ? con_i++ : con_j++;
if (con_i < con_j)
return 0;
if (con_i == n && con_j == 0)
return 2;
k--;
}
return 1;
}
5 楼
liren0 [专家分：260] 发布于 2006-10-01 00:06:00
大大款土土土土土土土土
6 楼
older [专家分：0] 发布于 2006-10-01 07:28:00
[em20][em19][em16][em12][em9][em13][em15][em19][em6][em5][em2][em1][em10][em13][em14][em16][em16][em18]
7 楼
older [专家分：0] 发布于 2006-10-01 07:29:00
[em20][em19][em16][em12][em9][em13][em15][em19][em6][em5][em2][em1][em10][em13][em14][em16][em16][em18]
8 楼
iAkiak [专家分：8460] 发布于 2006-10-01 10:48:00
#include <cassert>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
template<typename T, T Base>
struct BigUInt
{
typedef vector<T> data_type;
vector<T> data;
bool bValid;
BigUInt() : bValid(false)
{
}
BigUInt(T n)
{
*this = n;
}
BigUInt operator + (const BigUInt &o) const
{
assert(Base * 3 < UINT_MAX);
BigUInt a;
size_t i, len = min(data.size(), o.data.size());
T carry = 0, t;
a.data.reserve(max(data.size(), o.data.size()));
for (i = 0; i < len; i++)
{
t = data[i] + o.data[i] + carry;
a.data.push_back(t % Base);
carry = t / Base;
}
for (; i < data.size(); i++)
{
t = data[i] + carry;
a.data.push_back(t % Base);
carry = t / Base;
}
for (; i < o.data.size(); i++)
{
t = o.data[i] + carry;
a.data.push_back(t % Base);
carry = t / Base;
}
if (carry)
a.data.push_back(carry);
a.bValid = true;
return a;
}
BigUInt& operator = (T n)
{
data.clear();
while(n >= Base)
{
data.push_back(n);
n /= Base;
}
data.push_back(n);
bValid = true;
return *this;
}
bool valid() const
{
return bValid;
}
};
typedef BigUInt<unsigned long, 100000000> Number;
Number gCount[101][101];
void println(const Number &o)
{
if (!o.valid() || o.data.empty())
printf("0\n");
else
{
Number::data_type::const_reverse_iterator t = o.data.rbegin();
printf("%d", *t++);
while(t != o.data.rend())
{
printf("%08d", *t++);
}
printf("\n");
}
}
const Number& t(int n1, int n0)
{
int former1 = n0 - n1;
if (former1 < 0 || n0 < 0 || n1 < 0)
return gCount[0][0];
if (!gCount[n1][n0].valid())
gCount[n1][n0] = t(n1-1, n0) + t(n1, n0-1);
return gCount[n1][n0];
}
const Number& f(int n)
{
gCount[0][0] = 0;
gCount[0][1] = 1;
return t(n, n);
}
int main()
{
int n;
freopen("DATA1.IN", "r", stdin);
freopen("ANS1.OUT", "w", stdout);
while(scanf("%d", &n) == 1)
{
println(f(n));
}
return 0;
}
9 楼
wlsss [专家分：150] 发布于 2006-10-01 17:09:00
//结果为(2N)!/((N)!(N+1)!)
//即(N+2)*(N+3)*(N+4)...(2N-1)*2N/ (2*3*4*5...(N-1)*N)
#include <fstream>
#include <memory.h>
using namespace std;
int maxgys(int a,int b)
{
int c=a%b;
if(c==0)
return b;
else
return maxgys(b,c);
}
void yuefen(int *a,int *b)
{
int c=maxgys(*a,*b);
*a/=c;
*b/=c;
}
int main()
{
int N,*Result,used=0;
int i,j,t;
char temp[]="0000";
ifstream in("DATA1.IN");
ofstream out("ANS1.OUT");
in>>N;
int *N1=new int[N-1];
int *N2=new int[N-1];
Result=new int[2500]; //可以设有2500*4=10000位数字，N=2000,才597位数字
memset(Result,0,2000*sizeof(int));
Result[0]=1;
for(i=0;i<N-1;i++)
{
N1[i]=N+2+i;
N2[i]=2+i;
}
for(i=0;i<=N-2;i++)
{
for(j=N-2;j>=0;j--)
{
yuefen(&N1[j],&N2[i]);
if(N2[i]==1) break; //一定能把全部的N2[i]约成1，否则，结果不是整数
}
}
for(i=0;i<=N-2;i++)
{
t=0;
for(j=0;j<=used;j++)
{
Result[j]*=N1[i];
Result[j]+=t;
if(Result[j]>=10000)
{
t=Result[j]/10000;
Result[j]%=10000;
if(j==used) used++;
}
}
}
out<<Result[used];
for(i=used-1;i>=0;i--)
{
t=Result[i];
temp[0]='0'+t/1000;
temp[1]='0'+(t%1000)/100;
temp[2]='0'+(t%100)/10;
temp[3]='0'+(t%10);
out<<temp;
}
return 0;
}
10 楼
bood [专家分：490] 发布于 2006-10-01 19:12:00
#include <fstream>
#include <iostream>
using namespace std;
const char * input="DATA1.IN";
const char * output="ANS1.OUT";
long long m[101][201];
//r: number of 1 left, n: digits left
long long find_ans(int r, int n)
{
if(m[r][n]>=0) return m[r][n];
m[r][n]=find_ans(r-1,n-1)+find_ans(r,n-1);
return m[r][n];
}
int main()
{
ifstream fin(input);
ofstream fout(output);
for(int n=0;n<=200;n++)
{
for(int r=0;r<=100;r++)
{
if(n<2*r) m[r][n]=0;
else if(r==0&&n!=0) m[r][n]=1;
else if(n==0) m[r][n]=0;
else m[r][n]=-1;
}
}
int n;
fin>>n;
fout<<find_ans(n,2*n)<<endl;
return 0;
}
我来回复
您所在位置：