当前位置:网站首页>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
边栏推荐
- Idea rundashboard window configuration
- Realize reverse proxy client IP transparent transmission
- 一文搞定class的微观结构和指令
- February 13, 2022 -5- maximum depth of binary tree
- Three. JS VR house viewing
- Dynamic memory management (malloc/calloc/realloc)
- Leetcode weekly The 280 game of the week is still difficult for the special game of the week's beauty team ~ simple simulation + hash parity count + sorting simulation traversal
- golang代码检查工具
- Data analysis - Thinking foreshadowing
- Initial experience | purchase and activate typora software
猜你喜欢
Mathematical formula screenshot recognition artifact mathpix unlimited use tutorial
[speech processing] speech signal denoising based on Matlab GUI Hanning window fir notch filter [including Matlab source code 1711]
【经典控制理论】自控实验总结
透彻理解JVM类加载子系统
Registration and skills of hoisting machinery command examination in 2022
2:第一章:认识JVM规范1:JVM简介;
东南亚电商指南,卖家如何布局东南亚市场?
2022 R2 mobile pressure vessel filling review simulation examination and R2 mobile pressure vessel filling examination questions
Masked Autoencoders Are Scalable Vision Learners (MAE)
Go语言实现原理——锁实现原理
随机推荐
VS2010编写动态链接库DLL和单元测试,转让DLL测试的正确性
Hcip day 12 (BGP black hole, anti ring, configuration)
实现反向代理客户端IP透传
asp.net弹出层实例
golang代码检查工具
Data type, variable declaration, global variable and i/o mapping of PLC programming basis (CoDeSys)
Registration of Electrical Engineering (elementary) examination in 2022 and the latest analysis of Electrical Engineering (elementary)
Practice of concurrent search
Thoroughly understand JVM class loading subsystem
2022 registration examination for safety management personnel of hazardous chemical business units and simulated reexamination examination for safety management personnel of hazardous chemical busines
Starting from 1.5, build a micro Service Framework -- log tracking traceid
2: Chapter 1: understanding JVM specification 1: introduction to JVM;
AsyncSocket长连接棒包装问题解决
透彻理解JVM类加载子系统
如何快速理解复杂业务,系统思考问题?
[untitled]
Roman numeral to integer
Multi view 3D reconstruction
UVA – 11637 Garbage Remembering Exam (组合+可能性)
Masked Autoencoders Are Scalable Vision Learners (MAE)