#B4028. Prize Wheel Analysis
Prize Wheel Analysis
Prize Wheel Analysis
You are given a prize wheel consisting of prizes ranked from 1st to nth. The wheel is divided into s equal parts, where
$$s=1+2+\dots+n=\frac{n(n+1)}{2}$$
Each prize of rank k occupies exactly k parts. Thus, the probability of winning the kth prize is
$$\frac{k}{s}.$$
The prizes are ordered by quality: the 1st prize is the best, the 2nd prize is the second best, and so on.
Your task is to determine, among the prizes with a winning probability of at least m%, what is the best prize (i.e. the one with the smallest rank). In other words, find the smallest integer k (with 1 \le k \le n) such that
$$\frac{k}{s} \ge \frac{m}{100}.$$
If no such prize exists, output -1
.
inputFormat
The input consists of two integers separated by a space: n and m. Here, n (1 ≤ n ≤ 10^9, for instance) represents the number of prize levels, and m (0 ≤ m ≤ 100) is the percentage threshold.
outputFormat
Output a single integer: the best prize (i.e. the smallest prize number) whose winning probability is at least m%. If no such prize exists, output -1.
sample
3 20
2