算法题:UVA 10081

Problem B: Tight words

Given is an alphabet {0, 1, ... , k}, 0 <= k <= 9 .We say that a word of length n over this alphabet istight if any two neighbour digits in the word do not differby more than 1.

Input is a sequence of lines, each line contains two integer numbersk and n, 1 <= n <= 100. For eachline of input, output the percentage of tight words of lengthn over the alphabet {0, 1, ... , k} with 5 fractional digits.

Sample input

4 1

2 5

3 5

8 7

Output for the sample input

100.00000

40.74074

17.38281

0.10130

时间: 2024-11-01 12:37:26

算法题:UVA 10081的相关文章

算法题之UVA 763

Fibinary Numbers The standard interpretation of the binary number 1010 is 8 + 2 = 10. An alternate way to view the sequence ``1010'' is to use Fibonacci numbers as bases instead of powers of two. For this problem, the terms of the Fibonacci sequence

算法题:uva 10318

题目链接: 首先,可以确定每个格子只能选一次,因为选任何大于0的偶数次,等于没有效果 一样. 然后,就可以把这题理解成从r*c的矩阵中选择一些格子进行"点亮"操作,使得最终所 有格子都是"亮"的状态.那么,每个格子要么有点亮操作,要么没有,总共复杂度为2^25,显然必须 进行减枝. 假设从第一行第一列开始,从左往右,从上往下一次依次选择,对于当前所在位置( x, y),它已经不能影响到x-2以前的行数了,所以当到x行时,如果第x-2行没有全部点亮,则进行减枝 . 此

算法题:uva 1330

题目链接: http://uva.onlinejudge.org/index.php? option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4076 以前做过一道一维的,这题只是变成了二维的,其他方法都一样.HDU 1506  Largest Rectangle in a Histogram   题解 代码1: #include<cstdio> #include<cs

一个算法题,求答案啊啊啊啊

问题描述 一个算法题,求答案啊啊啊啊 白班 09:00-18:00 通班 09:00-21:00 每个人每个月通班数量必须等于早中班和中晚班数量之和 早中班 09:00-15:00 中晚班 15:00-21:00 假设:每月按照30计算. 排班规则: 1.每个人每个月固定休息6天连续上班天数不超过7天. 2.每天各班次上班的人数最低需求:8个白班5个通班1个早中班,2个中晚班. 3.每个月每个人的通班天数安排不超过8天. 4.每个人每个月早中班和中晚班的天数之和需要与通班天数相等. 5.每月最多

算法题:把阿拉伯金额转化为汉字表示的金额

n年没写算法题了,今天用了20分钟写了一个,要求如题,感觉算法有所退步,老了 using System; using System.Text; namespace money { class Program { static void Main(string[] args) { StringBuilder sb=new StringBuilder(); var strValue = Console.ReadLine(); var strlist = strValue.Split('.'); if

算法题:poj 2541 Binary Witch(KMP水过,逆序转换)

链接: http://poj.org/problem?id=2541 分析与总结: 做这题估算了下复杂度,觉得无论KMP再怎么快,这题暴力也肯定要超时的. 想了很久也没想出个好办法,于是决定暴力之,但是TLE了....于是就放了几天.之后看了下discuss ,这题的正解应该是状态压缩dp,不过目前我还不懂,跪了. 之后百度发现也可以用KMP水过,虽然是因为数据水才过的,不过这种思路很巧妙,值得借鉴! 直接暴力是枚举字符串的后面13个的字母,然后再用KMP匹配,这样的话,就绪要枚举多次,分别是

算法题:HDU 2594 Simpsons’ Hidden Talents(KMP)

链接: http://acm.hdu.edu.cn/showproblem.php?pid=2594 题目大意: 给两个字符串s1和s2, 求出是s1的前缀并且是s2的后缀的最长的字符串. 分析与总结: 真正理解好KMP算法,这题就是水题. 首先求出s1的失配函数,然后在s2中 寻找s1字符串. 在寻找字符串过程中,会有一个状态值j,这个值表示的是当前在s2中已经匹配 了多少个s1的字符. 所以,全部匹配完后,最后j的值就是以s2的最后一个字符结尾,和s1的前缀相匹 配的最长字符串.也就是所求的

求一个面试算法题答案。

问题描述 求一个面试算法题答案. 已知函数f()以相同的概率返回0或者1,求一个函数g()以相同的概率返回0-7之间的任意一个数字. 解决方案 其实这个题不难,可以考虑用2进制的方式来做.g(){return 4*f()+2*f()+f();} 希望能帮到你. 解决方案二: #includeint g(){srand(time(NULL));ret = rand()%8;return ret;}

经典算法题每日演练——第七题 KMP算法

原文:经典算法题每日演练--第七题 KMP算法       在大学的时候,应该在数据结构里面都看过kmp算法吧,不知道有多少老师对该算法是一笔带过的,至少我们以前是的, 确实kmp算法还是有点饶人的,如果说红黑树是变态级的,那么kmp算法比红黑树还要变态,很抱歉,每次打kmp的时候,输 入法总是提示"看毛片"三个字,嘿嘿,就叫"看毛片算法"吧. 一:BF算法      如果让你写字符串的模式匹配,你可能会很快的写出朴素的bf算法,至少问题是解决了,我想大家很清楚的知

java算法题,公司的笔试题

问题描述 java算法题,公司的笔试题 suppose you have N cakes, N is an interger>0 // at each time, you can either eat 1 cake, or 2 cakes or 3 cakes // PROBLEM: How many ways can you eat all N cakes // for example, N = 4, (1,2,1) and (1,1,2) are considered to be diffe