UVA – 11637 Garbage Remembering Exam (组合+可能性)

UVA – 11637 Garbage Remembering Exam (组合+可能性)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

 

Little Tim is now a graduate,and is thinking about higher studies. However, he first needs to appear in anexam whose preparation alone includes memorizing the meanings of over 3500words!

After going through the list afew times, however, he sees trouble – he can remember all the word-meanings aslong as they keep coming in the same order. When quizzed in random order,however, he is at a complete loss. So, as any decent programmer would, hewrites a random shuffler to help him quiz himself.

To his dismay, however, hefinds that words that were near each other in the original list quite often endup being close together in the shuffled list as well. He does not like this atall, and suspects that his random shuffler may have some kind of a bug. Butbefore he recodes his shuffler he wants your help to make sure that theshuffler is indeed faulty.

So he is asking for your helpin determining how likely such events are even if the list is indeed gettingcompletely randomly shuffled, and even if his program is working perfectly.

 

Given the size of the list N,and a proximity factor K, you are to determine the expected number of wastedwords in a shuffled list assuming that all possible shufflings are equallylikely. Informally, two words are considered wasted if they appear at adistance less than or equal to K in both the lists. Assume that theoriginal list is cyclical and shuffled list is linear (non-cyclical).

Formally, let us suppose thattwo words A and B have indices oa and ob inthe original list and indices sa and sb inthe shuffled list, respectively (all indices are 0-based). Then both the wordsare considered wasted if:

UVA - 11637 Garbage Remembering Exam (组合+可能性)and UVA - 11637 Garbage Remembering Exam (组合+可能性)

 

Input

The input consists of a seriesof cases. Each case consists of two integers N and K on a singleline. You may assume that 1≤K≤N≤100000.Input is terminated by a line containing two 0s, and has at most 125 lines ofinput.

 

Output

Output oneline for each test case except the last one. Each line of output should be ofthe form “Case X: Y”, where X is the serial number of output and Y is  the expected number of wasted words in theshuffled list, printed with exactly four digits after the decimal point, withrounding if necessary.

 

SampleInput                             Outputfor Sample Input

5 2

5 1

0 0

Case 1: 5.0000

Case 2: 3.5000

 

题意:输入n和k,你的任务是计算平均情况下。无效单词的个数,计算方法是:两个单词在又一次排列后的位置不超过k

思路:我们先计算有效的位置。枚举后。从剩下的选出2*k来计算,用log来计算

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 100005;

int n, k;
long double f[maxn];

void solve() {
	if (n == 1) {
		printf("0.0000\n");
		return;
	}
	if (n <= 2 * k + 1) {
		printf("%d.0000\n", n);
		return;
	}

	int N = k << 1, p;
	long double sum = 0;
	for (int i = 1; i <= n; i++) {
		p = max(i-1-k, 0) + max(n-k-i, 0);
		if (p < N)
			continue;
		sum += exp(f[p] + f[n - N - 1] - f[n - 1] - f[p - N]);
	}
	printf("%.4lf\n", (double)(n - sum));
}

int main() {
	f[0] = f[1] = 0;
	for (int i = 2; i <= maxn; i++)
		f[i] = f[i-1] + log((long double) i); 

	int cas = 1;
	while (scanf("%d%d", &n, &k) != EOF && n) {
		printf("Case %d: ", cas++);
		solve();
	}
	return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117532.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • NFV指的是_以致和以至的区别

    NFV指的是_以致和以至的区别这几年由于网路虚拟化技术的快速发展,很多网元设备都从传统的特定硬件转到通用硬件上的软件形态,那NFV和VNF这两个概念是有什么区别呢?NFV指网路功能虚拟化技术,通过IT虚拟化,实现传统通信网络的功能;VNF就是虚拟出来的一个个网元,实现某个网络功能单元,NF;NFV发展分为初级和高级阶段;初级阶段是基于传统硬件的软件执行环境转换为基于通用硬件的VM的专用虚拟化环境…

  • rabbitmq集群搭建_mongodb集群搭建

    rabbitmq集群搭建_mongodb集群搭建docker单容器部署创建桥接网络,用于容器间通信$dockernetworkcreatemq-network首先启动3个rabbitmq容器$dockerrun–namerabbit01\ -eRABBITMQ_SERVER_ADDITIONAL_ERL_ARGS=”-setcookieCOUBJLKLQCIAPKIQZGGJ”\ –hostnamerabbit01–networkmq-network\ -p5672:5672-p1567

  • pytorch lstm时间序列预测问题踩坑「建议收藏」

    这里写目录标题1.做时间序列问题2.问题1.数据集自己做,为多个输入对应多个或一个输出2.损失函数注意:不能用交叉熵nn.CrossEntropyLoss()3.准确率1.做时间序列问题2.问题1.数据集自己做,为多个输入对应多个或一个输出2.损失函数注意:不能用交叉熵nn.CrossEntropyLoss()nn.CrossEntropyLoss()要求target目标值即真实值是标签,是torch.int64类型数据,即整数,不允许小数,如果输入小数会强行取整,应该用nn.MSELo

  • .net 调用java WebService简单教程

    .net 调用java WebService简单教程java滴WebService配置比较复杂tomcat+jdk+cxf+spring+(strtus)看你心情吧==首先·创建一个··WebProject把cxf里面的lib再再里面的库复制到你的工程下···我java菜吖··不知道哪些必须滴···懒人全都放进去额接着开始写代码啦··packagecom.ws;importjavax.jws.WebService;@WebServicepublicinterfaceIHello{ publicStringHelloWord(

  • vim的配置文件_vim编辑文件命令

    vim的配置文件_vim编辑文件命令vimcfg.tar.bz2.txtvimbase64格式常用配制文件

  • Shiro框架:授权流程、授权方式、Shiro授权入门程序、自定义Realm进行授权

    Shiro框架:授权流程、授权方式、Shiro授权入门程序、自定义Realm进行授权

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号