Median Maximization solution codeforces
-
For Solution
Click Here!
You are given two positive integers nn and ss. Find the maximum possible median of an array of nn non-negative integers (not necessarily distinct), such that the sum of its elements is equal to ss.
A median of an array of integers of length mm is the number standing on the ⌈m2⌉⌈m2⌉-th (rounding up) position in the non-decreasing ordering of its elements. Positions are numbered starting from 11. For example, a median of the array [20,40,20,50,50,30][20,40,20,50,50,30] is the ⌈m2⌉⌈m2⌉-th element of [20,20,30,40,50,50][20,20,30,40,50,50], so it is 3030. There exist other definitions of the median, but in this problem we use the described definition.
The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases. Description of the test cases follows.
Each test case contains a single line with two integers nn and ss (1≤n,s≤1091≤n,s≤109) — the length of the array and the required sum of the elements.
For each test case print a single integer — the maximum possible median.
input
8 1 5 2 5 3 5 2 1 7 17 4 14 1 1000000000 1000000000 1
Median Maximization solution codeforces
5 2 2 0 4 4 1000000000 0
Possible arrays for the first three test cases (in each array the median is underlined):
- In the first test case [5–][5_]
- In the second test case [2–,3][2_,3]
- In the third test case [1,2–,2][1,2_,2]
-
For Solution
Click Here!