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)
blank

相关推荐

  • RabbitMQ入门篇[通俗易懂]

    文章目录前言MQ的基本概念MQ的优势MQ的劣势常见的MQ产品RabbitMQRabbitMQ简介RabbitMQ中的相关概念:RabbitMQ工作模式Workqueues工作队列模式Pub/Sub订阅模式Routing路由模式Topics通配符模式工作模式总结消息确认生产者前言记录RabbitMQMQ的基本概念MQ全称MessageQueue(消息队列),是在消息的传输过程中保存消息的容器。多用于分布式系统之间进行通信MQ的优势应用解耦提高系统容错性和可维

  • YOLOv5训练自己的数据集(超详细完整版)[通俗易懂]

    YOLOv5训练自己的数据集(超详细完整版)[通俗易懂]一.Requirements本教程所用环境:代码版本V3.0,源码下载地址:https://github.com/ultralytics/yolov5.gitPytorch:1.6.0Cuda:10.1Python:3.7官方要求Python>=3.8andPyTorch>=1.6.二.准备自己的数据集(VOC格式)1.在yolov5目录下创建paper_data文件夹(名字可以自定义),目录结构如下,将之前labelImg标注好的xml文件和图片放到对应目录下paper_

  • Runnable和Callable区别[通俗易懂]

    RunnableRunnable是一个接口,该接口中只有一个run方法,实现Runnable接口的类需要重写run方法,然后可以把这个类作为Thread类的一个参数,来创建线程,具体的用法有两种:创建一个类,实现Runnable接口,重写run方法classMyThreadimplementsRunnable{@Overridepublicvoidrun(){System.out.println(“MyThread”);}}使

  • java 用户态_深入理解内核态和用户态

    java 用户态_深入理解内核态和用户态1.内核态和用户态、内核线程和用户线程等解释操作系统调度CPU的最小单元是线程,也叫轻量级进程(LightWeightProcess),在一个进程里可以创建多个线程,这些线程都拥有各自的计数器、堆栈和局部变量等属性,并且能够访问共享的内存变量。处理器在这些线程上高速切换,让使用者感觉到这些线程在同时执行。系统的用户空间和内核空间:虚拟内存被操作系统划分成两块:内核空间和用户空间,内核空间是内…

  • 入园记——我的DBA之路

    入园记——我的DBA之路

  • Postman :中文汉化界面一键配置「建议收藏」

    Postman :中文汉化界面一键配置「建议收藏」开心到飞起!!!Postman工具界面被大佬汉化啦!!Gitee和Github链接跳转地址:黄连木笛大佬的Gitee地址:PostmanCn黄连木笛大佬的Github地址:PostmanCn汉化包下载地址【2021-04-1320:22如有新版可以自己更新下载】:https://gitee.com//hlmd/PostmanCn/attach_files/670442/download/app.zip使用方法:解压并复制app文件夹到路径:C:/Users/用户名/AppData/Lo.

发表回复

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

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