当前位置:网站首页>UVA – 11637 garbage remembering exam (combination + possibility)
UVA – 11637 garbage remembering exam (combination + possibility)
2022-07-05 23:16:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack
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 |
---|
The question : Input n and k, Your task is to calculate the average . Number of invalid words , The calculation method is : The position of two words after another arrangement does not exceed k
Ideas : Let's calculate the effective position first . After enumeration . Choose from the rest 2*k To calculate , use log To calculate
#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;
}
Copyright notice : This article is an original blog article , Blog , Without consent , Shall not be reproduced .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117532.html Link to the original text :https://javaforall.cn
边栏推荐
- Registration and skills of hoisting machinery command examination in 2022
- [speech processing] speech signal denoising and denoising based on Matlab GUI low-pass filter [including Matlab source code 1708]
- From the perspective of quantitative genetics, why do you get the bride price when you get married
- 3D point cloud slam
- [speech processing] speech signal denoising based on Matlab GUI Hanning window fir notch filter [including Matlab source code 1711]
- Use of metadata in golang grpc
- MySQL (1) -- related concepts, SQL classification, and simple operations
- Use the rewrite rule to rewrite all accesses to the a domain name to the B domain name
- Creative mode 1 - single case mode
- Element positioning of Web Automation
猜你喜欢
Realize reverse proxy client IP transparent transmission
查看网页最后修改时间方法以及原理简介
数据库基础知识(面试)
Tensor attribute statistics
Marginal probability and conditional probability
Selenium+pytest automated test framework practice
CJ mccullem autograph: to dear Portland
Mathematical formula screenshot recognition artifact mathpix unlimited use tutorial
Debian 10 installation configuration
Registration and skills of hoisting machinery command examination in 2022
随机推荐
Thoroughly understand JVM class loading subsystem
How to quickly understand complex businesses and systematically think about problems?
一文搞定JVM的内存结构
Object detection based on impulse neural network
LeetCode——Add Binary
Element positioning of Web Automation
leecode-学习笔记
Go语言实现原理——Map实现原理
openresty ngx_ Lua request response
Summary of binary tree recursive routines
Use the rewrite rule to rewrite all accesses to the a domain name to the B domain name
查看网页最后修改时间方法以及原理简介
Use of shell:for loop
Yiwen gets rid of the garbage collector
openresty ngx_lua请求响应
数学公式截图识别神器Mathpix无限使用教程
一文搞定class的微觀結構和指令
Three. JS VR house viewing
第十七周作业
Selenium+Pytest自动化测试框架实战