Guest User

Untitled

a guest
Jul 16th, 2019
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.40 KB | None | 0 0
  1. import math
  2. from collections import deque
  3. def mindef(josh,lent,f):
  4.     defence=0
  5.     pos=0
  6.     lent=len(bc)
  7.     if josh%2==0:
  8.         pos=lent-1
  9.     else:
  10.         defence+=a[josh-1]
  11.         pos=lent-1
  12.     if lent&(lent-1)==0:
  13.         return defence
  14.     mult=1
  15.     while lent>1:
  16.         if lent%2==0:
  17.             if lent and (not(lent&(lent-1))):
  18.                 return defence
  19.         if lent%2==0:
  20.             pos-=mult
  21.             lent=lent//2
  22.         else:
  23.             defence+=bc[pos]
  24.             lent=lent//2+1
  25.         mult*=2
  26.     return defence
  27. t=int(input())
  28. for qwe in range(t):
  29.     n=int(input())
  30.     n=n-1
  31.     a=list(map(int,input().split(" ")))
  32.     bc=deque(a)
  33.     f=int(input())
  34.     pos_=-1
  35.     deff=10**9+7
  36.     for i in range(0,n):
  37.         if i==0:
  38.             None
  39.         elif i%2==1:
  40.             x=bc.popleft()
  41.             bc.append(x)
  42.         else:
  43.             bc.popleft()
  44.         if bc[0]<=f:
  45.             if i%2==0:
  46.                 number=n-i//2
  47.                 if number and (not(number&(number-1))):
  48.                     deff=0
  49.                     pos_=i
  50.                     break
  51.             mina=mindef(i,n,f)
  52.             if mina<deff:
  53.                 deff=mina
  54.                 pos_=i
  55.                 if deff==0:
  56.                     break
  57.     if deff==10**9+7:
  58.         print("impossible")
  59.     else:
  60.         print("possible")
  61.         print(pos_+1,deff+f)
Add Comment
Please, Sign In to add comment