ACM程序设计 赛题样例

9 20 500 3

Sample Output 3

#include #include int p[1000];

void put(int n)//将前n个素数存入p中 {

int i,j,k=0; i=2; while(1) {

for(j=2;j<=(int)sqrt(i);j++) if(i%j==0) break;

if(j>(int)sqrt(i)) p[k++]=i; if(k>=n) return; i++; } }

int judge(int num)//判断num是否是一个平方数 {

int i=0,count; while(num!=1) {

count=0;

while(num%p[i]==0) {

num/=p[i]; count++; }

if(count%2) return 0; i++; }

return 1; }

int fun(int *p,int n,int m) {

int s,cou=0; int b[100]; int i,j,k,count; int min=0,max=0; for(i=0;i

for(j=0;j

b[j]=k%2; k/=2; if(b[j]) count++; if(count>m) break; j++; }

if(count==m) { s=1;

for(j=0;j

s*=p[j]; }

if(judge(s)) {

for(j=0;j

printf(\,p[j]); putchar('\\n'); cou++; } } }

return cou;

}

void main() {

int total=0,i,t,m; int a[100]; printf(\输入t：\); scanf(\,&t); put(t);

printf(\输入m:\); scanf(\,&m);

printf(\输入满足要求的%d个数:\,m); for(i=0;i

printf(\一共有%d组数！\\n\,total); }

国家利益

Background

没有永远的朋友，也没有永远的敌人，国家的行为取决于国家利益，国家的地位取决于国家实力 Problem

伊拉克战争结束后...

N个国家正在联合国开会商讨如何分配伊拉克的M块油田 N个国家按国家实力编号1，2，3...N，1号国家实力最强，第一个发言，N号最后一个发言，依次类推

发言国家会提出一个分配方案，所有有表决权的国家进行表决（包括发言国家自己），如果50%或以上

同意此方案，则会议结束，按照此国的方案分配油田，否则该国丧失表决权，下个国家重复上述过程

那么第一个国家提出怎样的方案才能使本国利益最大化？

Hint

每个国家分得的油田都是整数，不会出现几个国家共同拥有一块油田 每个国家都不希望别人的方案通过，但是每个国家都按照本国利益投票，比如1号国家提出一个方案， X号国家分Y油田，X号国家会进行比较， 如果该方案被否决，那么下次2号提出的方案X号国家分Z油田，而Z < Y，那么X号国家会赞成1号的方案， 否则反对

Input

每行包括2个整数N，M，（N,M <= 10^8）

Output

每行包括1个整数，1号国家能获得的最多油田数

Sample Input 7 100

Sample Output 97

我是新手，大家看看我的思路对吗？ 当只有2个国家，100个油田时： 第1国第2国 100 0

当只有3个国家，100个油田时： 第1国第2国第3国 99 0 1 当只有4个国家

第1国第2国第3国第4国 99 0 1 0 当只有5个国家

第1国第2国第3国第4国第5国 98 0 1 0 1 当只有6个国家

第1国第2国第3国第4国第5国第6国 98 0 1 0 1 0 。 。 。 。 。

看出想要让自己的方案通过，就要让第3，5，7，9。。。。的 国家有1个油田

如：只有2个国家：第一个（100），第2个（0）

3个国家时，如果第一个国家的方案不通过，就用第2个国家的，那第 三个国家就没油田，所以只要第一个国家给第3个国家1个 油田，第三国就赞成。

同理：4国家时：第一国的方案不通过，那就用就用第2个国家的，那三个国家就没油田，所以只要三个国家有一个油田，其 就同意。 其他情况类推 代码：

#include hanshu(int n,int m) {

int a[100],i,sum=0; for(i=0;i