Tile area table
Statement
A tile factory presses tiles whose width and height are both natural numbers. The values the width can take run from 1 to N, and the values the height can take run from 1 to N as well. The factory can therefore press N×N kinds of tile in all.
The area of each tile is worked out as (width × height). The inspector at the factory writes down the areas of all N×N kinds of tile and then lines the written values up in ascending order, from the smallest to the largest. Several kinds of tile may share the same area, and each one of them is counted separately and put in the line. The line therefore always holds N×N values.
Write a program that finds the area that lands in position K from the front of this line.
For example, suppose N=3. There are 9 kinds of tile that can be pressed, and the area of each one is as in the following table.
| Width | Height 1 | Height 2 | Height 3 |
|---|---|---|---|
| 1 | 1 | 2 | 3 |
| 2 | 2 | 4 | 6 |
| 3 | 3 | 6 | 9 |
Lining the 9 values in the table up in ascending order gives the following table.
| Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| Area | 1 | 2 | 2 | 3 | 3 | 4 | 6 | 6 | 9 |
So if K=7 the answer is 6. In the same example, if K=2 the answer is 2, and if K=9 the answer is 9.
The answer can be pinned down without lining the whole thing up. Take some value as a threshold and count only how many kinds of tile have an area at most that value. Counting that way with the threshold moved from 1 to 9 in the N=3 example above gives the following table.
| Threshold area | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| Number of tiles with an area at most the threshold | 1 | 3 | 5 | 6 | 6 | 8 | 8 | 8 | 9 |
Find the case K=7 in this table. With the threshold at 1, 2, 3, 4 and 5 the count is smaller than 7, so the seventh value has not come up yet. At the threshold 6 the count reaches 7 or more for the first time, so the area that lands in position 7 is 6.
As N grows, the line comes to hold N×N values. If N is 100,000 that is 10 billion values, so writing down every area and sorting them cannot produce the answer in time.
Input and Output Examples
Example 1
Input
3 7
Output
6
Example 2
Input
2 2
Output
2
Example 3
Input
10 50
Output
24
Input
The largest value N that a tile length can take is given first as a natural number. (N is a natural number less than or equal to 100,000.)
The next line then holds K, which says which position in the line the area is wanted for, as a natural number. K is a natural number from 1 to 1,000,000,000, and it is not larger than N×N, the number of values in the line.
The input is therefore two lines, with one natural number on each line.
Output
Print the area that lands in position K from the front on the first line, as a natural number. This value is from 1 to 10,000,000,000.
Only one newline follows the number you print. Do not attach a space before or after the number, and do not add a blank line after the newline either.
Requirements
- Several kinds of tile may share the same area, and each one of them is counted separately and put in the line
- The line always holds N×N values
- K is not larger than N×N
- Writing down every area and sorting them cannot produce the answer in time
- You must write a program that reads from standard input and writes to standard output
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
- There are 15 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 15 cases to solve this.
Examples
3 public cases. Judging also uses hidden cases. You have to pass all 15 cases to solve this.
2 2
2
3 7
6
10 50
24
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 3 public cases. Submitting runs the hidden cases too.
People who solved this problem
The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.
Log in and you can see the code once you solve this problem.