I tried to solve "This week's theme: Group made with number correspondence table" that Mr. Masui engineer office had asked in CodeIQ with Ruby. ..
For the content and solution of the problem, see @ angel_p_57's Nice article. As a reference, if you know that the expected value of the number of groups when the number of participants is $ m $ is the $ m $ harmonic series (the partial sum of the $ m $ harmonic series), the rest will be specified. All I had to do was find $ m $ that exceeded my expectations.
Therefore, the code of the answer is as follows.
codeiq.2928.rb
i=s=0;n=gets.to_i;until s>n;i+=1;s+=1.0/i;end;p i
Also, it is [known] that the $ m $ harmonic number can be approximated by $ \ log m + \ gamma \ (\ gamma: Euler-Mascheroni \ constant) $ (http://mathworld.wolfram.com/Euler). -MascheroniConstant.html), the minimum $ m $ that this exceeds the expected value of $ n $ is
m= \lfloor\exp(n-\gamma)\rfloor+1
You can find the answer with $ O (1) $.
This time, the expected value test cases prepared were up to 6 at most, so I was able to write it with a slight shift as follows.
codeiq.2928.approximation.rb
p Math.exp(gets.oct-0.577).round
It works fine up to $ n = 8 $. I thought I'd try golfing in various languages, but Hard Code is better for writing ...
C
codeiq.2928.c
float s;main(i,n){scanf("%d",&n);while(s<=n)s+=1./i++;printf("%d",i-1);}
codeiq.2928.approximation.c
main(n){scanf("%d",&n);printf("%d",lround(exp(n-.577)));}
D
codeiq.2928.approximation.d
import std.stdio;import std.math;int n;void main(){readf("%d",&n);write(round(exp(n-.577)));}
Go
codeiq.2928.approximation.go
package main;import(."fmt";."math");func main(){n:=.0;Scan(&n);Print(int(Exp(n-.577)+.5))}
Haskell
codeiq.2928.approximation.hs
main=do
n<-readLn
putStr.show.round.exp$n-0.577
PHP
codeiq.2928.approximation.php
<?=round(exp(fgets(STDIN)-.577));
Perl
codeiq.2928.approximation.pl
print int exp(<>-.577)+.5
Python
codeiq.2928.approximation.py
print int(2.718**(input()-.576)+.5)
R
codeiq.2928.approximation.r
cat(round(exp(scan("stdin")-.577)))
Scala
codeiq.2928.approximation.scala
import scala.math._;object Main extends App{println(round(exp(readInt-.577)))}
Bash
codeiq.2928.approximation.sh
awk '{print int(exp($1-.577)+.5)}'</dev/stdin
JavaScript(spidermonkey)
codeiq.2928.approximation.spidermonkey.js
print(Math.round(Math.exp(readline()-.577)))
Recommended Posts