HDU-Page11(2059～2062)

/*
 https://blog.csdn.net/sr_19930829/article/details/18802543
 动态规划题目。dp[i]数组用来保存从起点到当前第i个充电站所用的最短时间.  它等于dp[j] (j<i) 所用的时间加上从j到i所用的时间取最小的那个值。   在计算的时候，可以认为乌龟都是在充电站j充满电以后再走向充电站i的，可能会有疑问，题目中不是说充电站可以充电也可以选择不充电吗，
 的确是这样，这就要提前面说的最小的那个值，比如要求dp[4]， 比如要从节点2（充电站2）到4，在2充满电，经过3，这时候在节点3是不充电的，后来要从节点3到4，在3充满电，再到4，
 这样就考虑到了某一个充电站充电和不充电的情况，取最小值是指（0到4时间 +dp[0], 1到4时间+dp[1] ，2到4时间+dp[2], 3到4时间+dp[3]) 的最小值（就当前节点dp[4]来说）。
 */

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int l;                         //跑道的总长度
    int N, C, T;                   //充电站的个数，电动车冲满电以后能行驶的距离以及每次充电所需要的时间
    int VR, VT1, VT2;              //兔子跑步的速度，乌龟开电动车的速度，乌龟脚蹬电动车的速度
    int path[102];                 //各个充电站离跑道起点的距离
    double dp[102];
    
    while (scanf("%d", &l) != EOF) {
        scanf("%d %d %d", &N, &C, &T);
        scanf("%d %d %d", &VR, &VT1, &VT2);
        for (int i=1; i<=N; i++) {
            scanf("%d", &path[i]);
        }
        path[0]=0; path[N+1]=l;    //每个充电站看作一个节点，把起点和终点也看作节点
        dp[0] = 0;
        
        for (int i=1; i<=N+1; i++) {
            double min = 1000000;  //从第J到第I个充电站的最短时间
            
            for (int j = 0; j<i; j++) {
                double temp;       //temp是指从起点到节点i所用的时间
                                   //从节点j到节点i的距离大于等于C的话
                if (path[i] - path[j] > C)
                                   //时间是起点到节点j加上从j到i这一段所用的时间（分为两部分）
                    temp = dp[j] + C * 1.0 / VT1 + (path[i]-path[j]-C) * 1.0 / VT2;
                else
                    temp = dp[j] + (path[i] - path[j]) * 1.0 / VT1;
                
                // 和带着充满电的电动车的乌龟并列站在起跑线上,  一开始充满电
                if (j > 0)
                    temp += T;    //在节点j充电的时间，计算的时候看作每次都是在节点j充满电再走向节点i
                if (temp < min)
                    min = temp;
            }
            
            dp[i] = min;
        }
        
        double rt;
        rt = l * 1.0 / VR;//兔子用的时间
        if(dp[N+1] < rt)
            printf("What a pity rabbit!\n");
        else
            printf("Good job,rabbit!\n");
    }

    return 0;
}

/*
 我觉得英文的看规则的题目，不会难，难的是弄懂和逻辑
 12 * 1 (12 red-ball in one shoot) + 7 * 12(after hit a red ball, a black ball which was the most valuable ball should be the target)
 + 2 + 3 + 4 + 5 + 6 + 7(when no red ball left, make all the color ball in hole).
 然后它说的是可能赢，那么就给飞利浦第二个加数中的最好的colorball，给对手最差的喽？？？(不对，题目都有点误解)
 好吧，题目中现在给的是所有ball的数量而不是红球的数量了
 看一下解析
 */

/*
 https://www.cnblogs.com/webmen/p/5739262.html
 桌上有n个球，一人得分为a，另一人为b，问如果第一个人将n个球都打进洞后，得分能否超过（或等于）第二个人。
 总共有15个红球，和6个有颜色的球，每个红球的得分为1 ，6
 个有颜色的球分别为2 ， 3， 4 ，5， 6， 7 ；

 分析：
 ① 如果n>6 ,
 那么桌上有6个彩球和n-6个红球，但是由于有色球全部打进洞后，每个球需要额外增加黑球（最高得分）的得分；所以打进n个球的得分为：
 （n-6）*1+（n-6）*7+2+3+4+5+6+7
 ② 当 m <= 6 时，
 应该由价值最高的黑球（ 7 分） 向前依
 次增加求和，又因为有色球满足等差数列 ，由前6项减去前 6 - m项和，所以
 求得为（ 7 - m + 1 + 7 ) * m / 2 ( 这里直接通过得分来计算的）。因
 此，第二种情况的得分为（ 15 - m ) *m/ 2 ;
 */

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int n, pScore, oScore, leftBallNum;
    
    scanf("%d", &n);
    while (n--) {
        scanf("%d %d %d", &leftBallNum, &pScore, &oScore);
        
        if (leftBallNum > 6)
            pScore += (leftBallNum-6) + (leftBallNum-6) * 7 + (2 + 7) * 6 / 2;
        else
            pScore += (8-leftBallNum + 7) * leftBallNum / 2;
        
        if (pScore >= oScore)
            printf("Yes\n");
        else
            printf("No\n");
    }

    return 0;
}

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int n, m;
//    int blankFlag = 0;
    double credit, score;
    char className[100];
    
    scanf("%d", &n);
    while (n--) {
//        if (blankFlag)
//            printf("\n");
//        else
//            blankFlag = 1;
        
        scanf("%d", &m);
        int flag = 1;
//        int creditSum = 0; //都是浮点呀, 因为这个wa了好久
        double sum = 0.0, creditSum = 0.0;
        
        while (m--) {
            scanf("%s %lf %lf", className, &credit, &score);
            
            if (score < 60)
                flag = 0;
//                printf("Sorry!\n")
//                
; //这里不能直接
的，因为后面还有需要读取的课程和学分，难道不读取了吗？？？
                         //也不能直接print, 因为这里直接print的话不用回车就会输出了
            
            creditSum += credit;
            sum += credit * score;
        }
        
        if (flag) printf("%.2lf\n", sum * 1.0 / creditSum);
        else printf("Sorry!\n");
        
        if (n != 0)
            printf("\n");
    }

    return 0;
}

/*
 {1}
 {1,2}
 {1,2,3}
 {1,3}
 {1,3,2}

 {2}
 {2,1}
 {2,1,3}
 {2,3}
 {2,3,1}

 {3}
 {3,1}
 {3,1,2}
 {3,2}
 {3,2,1}
 */

/*
 https://blog.csdn.net/qq_33266889/article/details/53468509
 ①设f(n)是n个数字按照字典序所产生的子集个数，f(n) = n*( f(n-1) + 1 )，f(1)=1
 这里需要强调按照字典序生成的子集，一个含有n个元素的集合真子集的个数是2^n-1，为什么按照字典序生成的子集却不符合这一规律？
 因为在按字典序生成时{1,2}和{2,1}认为是两个不同的集合，所以 f(n) >> 2^n-1。
 ②设g(n)是每一组子集的个数，g(n)=f(n)/n
 g(n-1)=f(n-1)/(n-1)，f(n) = n*( f(n-1) + 1 )，g(n)=(n-1)*g(n-1)+1

 从上面子集顺序可以得到一个思路，我们可以先输出开头数字，然后把问题规模缩小到( n-1 , m-(t-1)*g(n)-1 )，不断缩小规模直至找到答案。
 
 主要步骤：
 1、求出所在组t
 2、输出所在组t的首元素s[t](同一组首元素相同)
 3、将该子集的下一个元素到最后一个的值+1,注意这个规律：在第i组，首元素为i，删除首元素后，在第i个子集后首元素均变大+1.
 4、缩减问题规模继续执行步骤1~3
 */

#include <stdio.h>
#include <string.h>

int main(int argc, const char * argv[]) {
    // insert code here...

    int n;
    int t;                              // 所求子集位于分组后的第几组
    long long m;                        // m：位于某一组的第几个子集
    long long g[21] = {0};              // 后面将子集分组后平均每组个数，如:c[2]表示n=2时的分组每组中子集数
    int s[21];                          // 每组首元素元素,组数<=20
    
    for (int i=1; i<=20; i++) {
        g[i] = (i - 1) * g [i -1] + 1;
    }
    
    while (scanf("%d %lld", &n, &m) != EOF) {
        for(int i=0;i<21;i++)
            s[i]=i;                     // 每循环一次就重新归位每组首元素
        
        while (m && n) {
            //以下要适当加括号, 不然优先级不对的, 特别是三目出现的时候
            // 得到第m个子集在分组后的第t组
            t = (int)((m / g[n]) + (m % g[n] > 0 ? 1 : 0));
            printf("%d", s[t]);
            
            for (int i=t; i<=n; i++) {
//                s[i]++;                 // 当去掉开头数字后，大于开头数字的数+1
                s[i]=s[i+1];            //在第n组中，第2个元素在第n个时变为它的下一个数, 而并不一定是++
            }
            m -= ((t - 1) * g[n] + 1);  // 减去(t-1组总子集数+1), m变为表示在剩余子集中位于第几个
            printf(m == 0 ? "\n" : " ");
            
            n--;                        // 规模减小, 依次递减, 直到执行上面的if代码或退出
        }
    }

    return 0;
}