Codechef War

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JULY19/hindi/CHFWAR.pdf), [Bengali](http://www.codechef.com/download/translated/JULY19/bengali/CHFWAR.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JULY19/mandarin/CHFWAR.pdf), [Russian](http://www.codechef.com/download/translated/JULY19/russian/CHFWAR.pdf) and [Vietnamese](http://www.codechef.com/download/translated/JULY19/vietnamese/CHFWAR.pdf) as well. Bitland declared war on Chefland and sent an army to fight them, but Chefland defended efficiently and Bitland's army has been reduced to $N$ soldiers. They have no chance of winning the war and do not want to surrender, so they are planning to commit group suicide. Josh, the leader of Bitland's remaining soldiers, has different plans — he wants to survive and somehow escape. The soldiers are numbered $1$ through $N$; Josh is soldier $N$. The soldiers are going to stand in a circle in the order $1, 2, \ldots, P1, N, P, P+1, \ldots, N1$. Formally, they are standing in the circle in such a way that if Josh's position is $P$ ($1 \le P \le N$), then for each $i$ ($1 \le i \le N2$, $i \neq P1$), soldier $i+1$ is directly to the right of soldier $i$, soldier $P$ (if $P \le N1$) or $1$ (if $P = N$) is directly to the right of Josh and Josh is directly to the right of soldier $P1$ (if $P \ge 2$) or soldier $N1$ (if $P = 1$); if $2 \le P \le N2$, soldier $1$ is also directly to the right of soldier $N1$. For each $i$ ($1 \le i \le N1$), soldier $i$ has a sword with power $A_i$. Josh plans to take a shield with sufficiently high defense power $D$. First, the soldiers start to commit group suicide according to the following rules:  Initially, soldier $1$ is the *attacking soldier*.  If the attacking soldier is not Josh, this soldier attacks the soldier that is currently to his right.  When Josh is attacked with power $a$, the current defense power of his shield decreases by $a$, and if it becomes negative, Josh dies. When a different soldier is attacked, he does not try to defend and dies immediately. The power of the attacking soldier's sword does not change.  Then, the next living soldier to the right of the current attacking soldier becomes the attacking soldier and the process continues until there is only one soldier left. It is clear that this way, Josh cannot be the last survivor. However, Chefland's general Chef plans to interrupt this process as soon as there are exactly two living soldiers of Bitland left (Josh wants to be one of them) by attacking them with Chefland's full firepower $F$. Since this attack is unexpected, both attacked soldiers try to defend independently with the weapons they have. Josh survives if the current defense power of his shield is at least $F$. Any other soldier survives only if the power of his sword is strictly greater than $F$. Since Chefland does not attack again, if both Josh and another soldier survive, then the other soldier will kill Josh. Therefore, Josh wants to be the only survivor of Chefland's attack. Your task is to find the minimum possible value of $D$ such that Josh survives if he chooses his position $P$ optimally (or determine that he cannot survive) and the lowest position $P$ such that Josh survives if he takes a shield with this defense power $D$. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains $N1$ spaceseparated integers $A_1, A_2, \ldots, A_{N1}$.  The third line contains a single integer $F$. ### Output For each test case, first, print a line containing the string `"possible"` if Josh can survive or `"impossible"` if he cannot (without quotes). Then, if he can survive, print a second line containing two spaceseparated integers $P$ and $D$. ### Constraints  $1 \le T \le 1,000$  $2 \le N \le 1,000,000$  $1 \le A_i \le 10,000$ for each valid $i$  $1 \le F \le 10,000$  the sum of $N$ over all test cases does not exceed $1,000,005$ ### Subtasks **Subtask #1 (30 points):**  $1 \le T \le 10$  $2 \le N \le 100$  $1 \le A_i \le 100$ for each valid $i$  $1 \le F \le 100$ **Subtask #2 (70 points):** original constraints ### Example Input ``` 2 5 12 34 45 5 10 5 10 15 43 20 5 ``` ### Example Output ``` possible 4 100 impossible ``` ### Explanation **Example case 1:** When Josh is at the position $P = 4$, the soldiers' initial powers in clockwise order around the circle, starting with soldier $1$, are $[12, 34, 45, D, 5]$ ($D$ denotes Josh). Then, the following happens:  The soldier with power $12$ attacks the soldier with power $34$ and kills him.  The soldier with power $45$ attacks Josh, who defends. The living soldiers' powers are now $[12, 45, D45, 5]$ and Josh is the attacking soldier.  Josh does not attack, so the soldier to his right (with power $5$) becomes the attacking soldier. He attacks the soldier with power $12$ and kills him.  The soldier with power $45$ attacks Josh again and Josh defends again.  The soldier with power $5$ attacks the soldier with power $45$ and kills him.  Now, two soldiers are left: Josh (with a shield with defense power $D90$) and the soldier with a sword with power $5$. Each of them is attacked with firepower $F=10$, so the power of Josh's shield drops to $D100$ and the other soldier dies. If Josh survives, his shield's initial power $D$ should be at least $45+45+10 = 100$. For all other positions $P$, Josh cannot survive. **Example case 2:** Regardless of how large $D$ is and which position Josh chooses, after Chefland's attack, a soldier of Bitland other than Josh will always survive. This soldier will then attack Josh until his shield breaks and he dies.Author:  deadshot_sb 
Editorial  https://discuss.codechef.com/problems/CHFWAR 
Tags  bitwiseoperatn, cases, deadshot_sb, july19, medium 
Date Added:  23052019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions