文档章节

sicily 1011 Lenny's Lucky Lotto

Ciel
 Ciel
发布于 2012/12/17 16:13
字数 590
阅读 44
收藏 0

 

Description

Lenny likes to play the game of lotto. In the lotto game, he picks a list of N unique numbers in the range from 1 to M. If his list matches the list of numbers that are drawn, he wins the big prize.

Lenny has a scheme that he thinks is likely to be lucky. He likes to choose his list so that each number in it is at least twice as large as the one before it. So, for example, if = 4 and = 10, then the possible lucky lists Lenny could like are:

1 2 4 8

1 2 4 9

1 2 4 10

1 2 5 10

 Thus Lenny has four lists from which to choose.

Your job, given N and M, is to determine from how many lucky lists Lenny can choose.

Input

There will be multiple cases to consider from input. The first input will be a number C (0 < C <= 50) indicating how many cases with which you will deal. Following this number will be pairs of integers giving values for N and M, in that order. You are guaranteed that 1 <= N <= 10, 1 <= M <= 2000, and N <= M. Each N M pair will occur on a line of its own. N and M will be separated by a single space.

Output

For each case display a line containing the case number (starting with 1 and increasing sequentially), the input values for N and M, and the number of lucky lists meeting Lenny’s requirements. The desired format is illustrated in the sample shown below.

Sample Input

3
4 10
2 20
2 200

Sample Output

Case 1: n = 4, m = 10, # lists = 4
Case 2: n = 2, m = 20, # lists = 100
Case 3: n = 2, m = 200, # lists = 10000

分析:

本题目为动态规划应用,或者说是递推求值(因为并非典型DP题目,并没有求某种最优解)。关键是分析问题找出递推公式,再潜入循环中求解即可。这里特别要注意题目要求对第i个选择数字,第i+1个数字应该大于或者等于第i个的2倍;同时,本题最后答案可能会很大,所以存储结果的数组数据类型要调整为usigned long long较好,防止发生溢出。

代码:

// Problem#: 1011
// Submission#: 1794222
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <cstring>
using namespace std;

#define N 11
#define M 2001
unsigned long long dp[N][M];

int main(){
    int t,n,m,count;
    unsigned long long re;
    count = 0;
    cin >> t;
    while(t--){
        cin >> n >> m;
        re = 0;
        memset(dp,0,sizeof(dp));  
        for ( int i=1 ; i<=m ; i++ ) dp[1][i]=1;  
        for ( int i=2 ; i<=n ; i++ ){
            for (int j=1 ; j<=m ; j++){
                for ( int k=i-1 ; k<=j/2 ; k++ )
                    dp[i][j] += dp[i-1][k];
            }
        }
        for ( int i=n ; i<=m ; i++ ) re += dp[n][i];
        cout << "Case " << ++count << ": n = " << n << ", m = " << m << ", # lists = " << re << endl;
    }
    return 0;
}

© 著作权归作者所有

上一篇: sicily 1034 Forest
下一篇: sicily 1004 I Conduit!
Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
【总结】使用Json4s实现Scala对象转Json

object JsonExample extends App { import org.json4s.JsonDSL._ import org.json4s.jackson.JsonMethods._ //第一部分,官网例子 case class Winner(id: Long, numbers: List[Int]) case c......

巧克力黒
2018/06/27
0
0
Intel PRO/Wireless 2100, 2200 and 2915 devices for Debian5

Intel PRO/Wireless 2100, 2200 and 2915 devices This page describes how to enable support for WiFi devices based on Intel 2100, 2200 and 2915 chipsets on Debian systems. 目录 In......

任远
2010/10/31
394
0
debian 7 下的一些错误提示解决办法

1、修改系统时间 cp /usr/share/zoneinfo/Asia/ShangHai /etc/localtime #时区为亚洲/上海 date 命令查看 2、用惯了vim,在debian下你会发现vi中无法使用delete和backspace键。 原来Debian中...

hiwill
2015/11/20
102
0
debian 5(lenny)源列表

这个多媒体的源需要额外的公钥,请参考它的官网页面一开头的说明, # 地址:http://www.debian-multimedia.org/ deb http://www.debian-multimedia.org lenny main non-free # deb ftp://ft...

神勇小白鼠
2011/08/22
638
0

没有更多内容

加载失败,请刷新页面

加载更多

java 三元表达式

例子:C=A>B ? 100 :200; 这条语句的意思是,如果A>B的话,就将100赋给C,否则就将200赋给C;

无名氏的程序员
22分钟前
3
0
针对回流和重绘的渲染优化--公司分享

如果是你,你会如何实现浏览器内核,你认为的浏览器渲染的流程是怎么样的 工作开发中,你有做过哪些关于性能优化的工作(代码),或者目前的业务中有哪些是可以做优化的 浏览器渲染机制 什么...

莫西摩西
35分钟前
3
0
html:常见行内标签,常见块级标签,常见自闭合标签

本文转载于:专业的前端网站▷html:常见行内标签,常见块级标签,常见自闭合标签 本文内容: 常见行内标签 常见块级标签 常见自闭合标签 首发日期:2018-02-12 修改: 2018-04-25:删除了不常用...

前端老手
43分钟前
3
0
终日乾乾,含章可贞@20191017

工龄7年,7年里换了两家公司,一次被动,一次主动。一次被动只有暖,一次主动冷暖皆有。第一次,只有遗憾,没有珍惜那段时光。第二次细说一下: 一、老公司 1、离职前,甲方三种态度:恭喜、...

sunny小喵
今天
4
0
zk中leader和follower启动时信息交互

QuorumPeer中读取节点状态信息,不同状态下设置不同角色 1 Leader启动Follower接收器LearnerCnxAcceptor LearnerCnxAcceptor负责接收非leader连接请求,线程中创建LearnerHandler处理器 2 Le...

writeademo
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部