例46  巧妙称重

题目描述

有N个篮子，编号1~N，篮子中有很多金币，每个重w。但是有一个编号的篮子中，每个金币重d。现从第一个篮子中拿1个金币，第二个篮子中拿2个，…，第N-1中拿N-1个，第N中不拿，给出这些金币的总重量wei，问：是第几个篮子中的金币重量较轻？

输入格式

输入文件将由一行或多行组成；每行包含四个正整数，由一个空格分隔。前三个整数分别是数字N、w和d，如上所述。第四个整数是所选硬币称重的结果。

N至少为2，但不超过8000。w的值最多为30。d的值将小于w。

输出格式

对于每组测试数据输出一行，由一个正整数组成：装有比其他篮子中金币轻的金币的篮子编号。

输入样例

10 25 8 1109

10 25 8 1045

8000 30 12 959879400

输出样例

2

10

50

        （1）编程思路。

        这是一道数学题分析题。若设1~N-1这N-1个篮子中放的金币均为重量为w的金币，则应有的总重量为：w*（1+n-1)*(n-1)/2（简单的等差数列求和），所求的和减去实际称出的重量wei，得到金币重量的差值sum = ((n-1)*(n-1+1)/2)*w-wei。若sum为0，则装有重量为d的篮子编号必为N；若sum不为0，除以d，得到较轻金币的个数，即为所求编号。

（2）源程序。

#include <stdio.h>

int main()

{

     int n,w,d,p;

     while (scanf("%d%d%d%d",&n,&w,&d,&p)!=EOF)

     {

         int sum = ((n-1)*(n-1+1)/2)*w-p;

         if(sum==0)

             printf("%d\n",n);

         else

             printf("%d\n",sum/d);

     }

     return 0;

}

习题46

46-1  鬼谷子的钱袋

        本题选自洛谷题库 （https://www.luogu.org/problem/P2320）

题目描述

鬼谷子非常聪明，正因为这样，他非常繁忙，经常有各诸侯车的特派员前来向他咨询时政。

有一天，他在咸阳游历的时候，朋友告诉他在咸阳最大的拍卖行（聚宝商行）将要举行一场拍卖会，其中有一件宝物引起了他极大的兴趣，那就是无字天书。

但是，他的行程安排得很满，他已经买好了去邯郸的长途马车票，不巧的是出发时间是在拍卖会快要结束的时候。于是，他决定事先做好准备，将自己的金币数好并用一个个的小钱袋装好，以便在他现有金币的支付能力下，任何数目的金币他都能用这些封闭好的小钱的组合来付账。

鬼谷子也是一个非常节俭的人，他想方设法使自己在满足上述要求的前提下，所用的钱袋数最少，并且没有两个钱袋装有相同的大于1的金币数。假设他有m个金币，你能猜到他会用多少个钱袋，并且每个钱袋装多少个金币吗？

输入格式

包含一个整数，表示鬼谷子现有的总的金币数目m。其中，1≤m ≤1000000000。

输出格式

两行，第一行一个整数h，表示所用钱袋个数

第二行表示每个钱袋所装的金币个数，由小到大输出，空格隔开

输入样例

3

输出样例

2

1 2

       （1）编程思路。

先看看金币数目m为1~10怎么表示。

m=1，显然1个钱袋，装1个金币；m=2，用2个钱袋，各装1个金币；

m=3，用2个钱袋，分别装1个和2个金币；

m=4，用3个钱袋，分别装1个、1个和2个金币；

m=5，用3个钱袋，分别装1个、1个和3个金币；

m=6，用3个钱袋，分别装1个、2个和3个金币；

m=7，用3个钱袋，分别装1个、2个和4个金币；

m=8，用4个钱袋，分别装1个、1个、2个和4个金币；

m=9，用4个钱袋，分别装1个、1个、2个和5个金币；

m=10，用4个钱袋，分别装1个、1个、3个和5个金币；

……

        由上面规律可以看出，n以内的任何数字可以用1到n/2以内的数字表示，n/2以内的任何数字可以用1到n/4以内的数字表示，……。

        例如，为了表示15，一个袋子装（15+1）/2=8个金币，剩下7个金币；为了表示7，用一个袋子装（7+1）/2=4个金币，剩下3个金币；为了表示3，用一个袋子装(3+1)/2=2个金币，剩下2个金币，可用两个袋子，各装1个金币。即m=15，用4个钱袋，分别装1个、2个、4个金币和8个金币；

        M=29时，一个袋子装(29+1)/2=15个金币，剩下14个金币用4个袋子，分别装1个、2个、4个金币和7个金币。

        M=30时，一个袋子装(30+1)/2=15个金币，剩下15个金币用4个袋子，分别装1个、2个、4个金币和8个金币。

        M=31时，一个袋子装(31+1)/2=16个金币，剩下15个金币用4个袋子，分别装1个、2个、4个金币和8个金币。

        ……

       （2）源程序。

#include <stdio.h>

int main()

{

    int a[32];

    int n;

    scanf("%d",&n);

    int cnt=0;

    while (n>0)

    {

        a[cnt++]=(n+1)/2;

        n=n/2;

    }

    printf("%d\n",cnt);

    for (int i=cnt-1;i>=0;i--)

        printf("%d ",a[i]);

    printf("\n");

    return 0;

}

46-2  圆桌会议

题目描述

N个哲学家围坐在一张圆形的桌子旁进行交流。在一天在讨论的时候，哲学家Eddy想出了一个极为古怪的想法，如果他们在每一分钟内，一对相邻的两个哲学家交换一下位子，那么要多少时间才能得到与原始状态相反的座位顺序呢?

输入格式

对于给定数目N（1<=N<=32767），表示有N个哲学家，求要多少时间才能得到与原始状态相反的座位顺序，即对于每个人，原先在他左边的人后来在他右边，原先在他右边的人在他左边。

输出格式

对每个数据输出一行，表示需要的时间（以分钟为单位）。

输入样例

4

5

6

输出样例

2

4

6

       （1）编程思路。

        若n个哲学家坐成一排，123…n逆序变为n…321，需要交换位置1+2+…+(n-1)=n*(n-1)/2次，即1右移n-1步，2右移n-2步，……。

       现在n个哲学家在圆桌边围成一圈，所以可以双向移动，因而可将n分成两部分，n/2和n-n/2，两部分分别按一排独自逆序，可以达到时间最少。

       例如1234，可分成12和34，2分钟后可得到2143，由于成圈，所以也是逆序。

       再如12345，可分成123和45，123逆序为321用2分钟，45逆序为54用1分钟，3分钟后可得到32154，由于成圈，所以也是逆序。

      （2）源程序。

#include <stdio.h>

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        int a=n/2;

        int b=n-a;

        printf("%d\n",a*(a-1)/2+b*(b-1)/2);

    }

    return 0;

}

46-3  取木棍

题目描述

有边长分别为1~n的n根小木棍，现在要求拿走尽量少的小木棍，使得剩下的小木棍任意取三根都不能组成三角形。

输入格式

输入第一行包含一个整数T（T≤20），表示测试用例的数量。

对于每个测试用例，只有一行描述给定的整数n（1≤N≤20）。

输出格式

对于每个测试用例，输出一行“case#x:y”，其中x是用例编号（从1开始），y是应取走的最小木棍数目。

输入样例

3

4

5

6

输出样例

Case #1: 1

Case #2: 1

Case #3: 2

        （1）编程思路。

        边长为1~n的n根小木棍取走一些后，若最后剩下的小木棍的边长构成Fib（斐波那契）数列，则一定可以保证任意三根木棍都不能组成三角形。

      （2）源程序。

#include <stdio.h>

int main()

{

    int a[22]={0};

    a[1]=a[2]=a[3]=a[5]=a[8]=a[13]=a[21]=1;

    int i;

    for (i=2;i<22;i++)

        a[i]+=a[i-1];

    int t;

    scanf("%d",&t);

    for (i=1; i<=t; i++){

        int n;

        scanf("%d",&n);

        printf("Case #%d: %d\n", i,n-a[n]);

    }

    return 0;

}