Xenny and Coin Rankings
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Xenny reverse-engineered all the binaries released by the International Security Agency (ISA) during summer vacation just to pass time. As a reward, the ISA gave him infinite ByteCoins.
Out of sheer boredom and a sense of purposelessness in life, Xenny decided to arrange the Coins on a 2-Dimensional Euclidean Plane. The boredom was so strong that he arranged these coins in a specific pattern, as opposed to the usual, monotonous way of storing coins in a Piggy Bank.
On each integer co-ordinate (x, y) where x ≥ 0 and y ≥ 0, a single coin was placed. And each coin was assigned a rank. The following pattern was followed in the arrangement:
Let's denote the co-ordinates of the kth coin by (xk, yk) and its rank by Rk.
For any 2 coins i, j:
if (xi + yi) < (xj + yj) or ( (xi + yi) == (xj + yj) and xi < xj)
then Ri < Rj. We sort all the coins by this comparison.
The index of the coin (C) in this sorted list of coins (1-indexed) is its rank.
Each query is as follows: Given (U, V). Among the coins that are lying on or inside the rectangle with its diagonal end-points being (0, 0) and (U, V), which is the coin that has the maximum rank?
The first line contains an integer, T - the number of testcases.
Each testcase contains 2 space-separated integers: U, V.
OutputFor each testcase, print the rank of the maximum ranked coin, on a new line.
Subtask 1: (40 points)
- 1 ≤ T ≤ 100
- 1 ≤ U, V ≤ 100
Subtask 2: (60 points)
- 1 ≤ T ≤ 100
- 1 ≤ U, V ≤ 109
Input: 1 1 2 Output: 8
|Tags||june17, simple, wittyceaser|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.