Sasha and the Drawing (Codeforces 1929B)
Tags: Greedy, constructive algorithms

Even in kindergarten, Sasha liked a girl. Therefore, he wanted to give her a drawing and attract her attention.As a drawing, he decided to draw a square grid of size $$$n \times n$$$, in which some cells are colored. But coloring the cells is difficult, so he wants to color as few cells as possible. But at the same time, he wants at least $$$k$$$ diagonals to have at least one colored cell. Note that the square grid of size $$$n \times n$$$ has a total of $$$4n - 2$$$ diagonals.Help little Sasha to make the girl fall in love with him and tell him the minimum number of cells he needs to color.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^8$$$, $$$1 \leq k \leq 4n - 2$$$) — the size of the square grid and the minimum number of diagonals in which there should be at least one colored cell.

Output: For each test case, output a single integer — the minimum number of cells that need to be colored.

Note: In the pictures below, the colored cells are marked in black, and all diagonals are marked in purple.In the first test case, you can color $$$2$$$ cells so that $$$4$$$ diagonals contain at least one colored cell:  In the third test case, you can color $$$6$$$ cells so that all $$$10$$$ diagonals contain at least one colored cell:  

Sample Inputs:
7
3 4
3 3
3 10
3 9
4 7
7 11
2 3

Sample Outputs:
2
2
6
5
4
6
2

Solution (Python):
t = int(input())
for q in range(t):
    (n, k) = list(map(int, input().split(' ')))
    if k <= 4 * n - 4:
        print((k + 1) // 2)
    elif k == 4 * n - 3:
        print((k + 1) // 2)
    else:
        print((k + 2) // 2)

Solution (Python):
import math

def solve():
    (n, k) = map(int, input().split())
    if k <= 4 * n - 4:
        ans = math.ceil(k / 2.0)
        print(ans)
    elif k == 4 * n - 3:
        print(k // 2 + 1)
    elif k == 4 * n - 2:
        print(k // 2 + 1)
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()

Solution (Python):
for s in [*open(0)][1:]:
    (n, k) = map(int, s.split())
    print(k + (k > 4 * n - 3) + 1 >> 1)