Competitive Programming

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,D−45,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 D−90) 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 D−100 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.




Solution:
EDITORIAL

Pseudocode:

int Damage(int n, int a[],int p)
  int s = (n-(p+1)) + ceil(p/2)
  int d = 0
  if(p%2 != 0)
    d = d + a[p]
  int last = s
  int step = 2
  while( last != 1)
    if((last-1)%step==0)
      if(last<=(n-(p+1))
        d = d + a[last+p]
      else
        d = d + a[2*(k-n+p)+1]
    else
      last = ((last-1)-(last-1)%step)+1
    step = step*2
  return d

int n,f
n,f=input
n=n-1
int a[n+1]
a[0] = 0;
for i = 1 to n
    a[i]=input
int result[n]

initialize result with -1

for i=0 to n 
    if(a[i]<=f)
        result[i]=damage(n,a,i)
int count=0
for i=0 to n
     if(result[i]!=-1)
         count=count+1
if(count==0)
      print "impossible"
else
      int index=n+1
      int min_damage=INT_MAX
      for i = n to 0
           if(result[i] != -1 && result[i]<=min_damage)
                 index=i
                 min_damage=result[i]
      print "possible\n"
      print index+1
      print min_damage+f

Code:
CODE

For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Pastebin

#include <bits/stdc++.h>#define dbg(i,j) cout<<"I am "<<i<<" = "<<endl<<j<<end - Pastebin.com

Pastebin.com is the number one paste tool since 2002. Pastebin is a website where you can store text online for a set period of time.

www.tg-me.com/us/Competitive Programming/com.Competitive_Programming_Cpp/45

5.4K viewsSep 22, 2019 at 10:45

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,D−45,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 D−90) 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 D−100 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.




Solution:
EDITORIAL

Pseudocode:

int Damage(int n, int a[],int p)
  int s = (n-(p+1)) + ceil(p/2)
  int d = 0
  if(p%2 != 0)
    d = d + a[p]
  int last = s
  int step = 2
  while( last != 1)
    if((last-1)%step==0)
      if(last<=(n-(p+1))
        d = d + a[last+p]
      else
        d = d + a[2*(k-n+p)+1]
    else
      last = ((last-1)-(last-1)%step)+1
    step = step*2
  return d

int n,f
n,f=input
n=n-1
int a[n+1]
a[0] = 0;
for i = 1 to n
    a[i]=input
int result[n]

initialize result with -1

for i=0 to n 
    if(a[i]<=f)
        result[i]=damage(n,a,i)
int count=0
for i=0 to n
     if(result[i]!=-1)
         count=count+1
if(count==0)
      print "impossible"
else
      int index=n+1
      int min_damage=INT_MAX
      for i = n to 0
           if(result[i] != -1 && result[i]<=min_damage)
                 index=i
                 min_damage=result[i]
      print "possible\n"
      print index+1
      print min_damage+f

BY Competitive Programming