当前位置:网站首页>UVA – 11637 Garbage Remembering Exam (组合+可能性)
UVA – 11637 Garbage Remembering Exam (组合+可能性)
2022-07-05 23:02:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
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:
and
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;
}
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117532.html原文链接:https://javaforall.cn
边栏推荐
- Codeforces Global Round 19
- Registration of Electrical Engineering (elementary) examination in 2022 and the latest analysis of Electrical Engineering (elementary)
- UART Application Design and Simulation Verification 2 - TX Module Design (Stateless machine)
- Go语言实现原理——锁实现原理
- Shell: operator
- Multi camera stereo calibration
- Metasploit(msf)利用ms17_010(永恒之蓝)出现Encoding::UndefinedConversionError问题
- Nangou Gili hard Kai font TTF Download with installation tutorial
- Matlab smooth curve connection scatter diagram
- 【原创】程序员团队管理的核心是什么?
猜你喜欢
一文搞定class的微观结构和指令
Fix the memory structure of JVM in one article
Codeforces Global Round 19
fibonacci search
Error when LabVIEW opens Ni instance finder
第十七周作业
CorelDRAW plug-in -- GMS plug-in development -- new project -- macro recording -- VBA editing -- debugging skills -- CDR plug-in (2)
Using LNMP to build WordPress sites
MoCo: Momentum Contrast for Unsupervised Visual Representation Learning
数据库基础知识(面试)
随机推荐
Week 17 homework
Global and Chinese market of water treatment technology 2022-2028: Research Report on technology, participants, trends, market size and share
Déterminer si un arbre binaire est un arbre binaire complet
【Note17】PECI(Platform Environment Control Interface)
Practice of concurrent search
Negative sampling
[screen recording] how to record in the OBS area
LabVIEW打开PNG 图像正常而 Photoshop打开得到全黑的图像
ORB_ SLAM2/3
Leetcode buys and sells stocks
秒杀系统的设计与实现思路
Douban scoring applet Part-2
Finally understand what dynamic planning is
Using LNMP to build WordPress sites
UART Application Design and Simulation Verification 2 - TX Module Design (Stateless machine)
(4)UART应用设计及仿真验证2 —— TX模块设计(无状态机)
Dynamic memory management (malloc/calloc/realloc)
Expectation, variance and covariance
[speech processing] speech signal denoising and denoising based on Matlab GUI low-pass filter [including Matlab source code 1708]
Three.JS VR看房