#B4028. Prize Wheel Analysis

    ID: 11685 Type: Default 1000ms 256MiB

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