fork(2) download
copy 
  1.  
  2. class Entry():
  3.     def __init__(self):
  4.         self.M = ''
  5.         self.lf, self.uf = False, False
  6.         self.idx = 0
  7.  
  8.     def nexts(self, bit, lf=None, uf=None):
  9.         """ Generate next Entry (idx+=1). If you need to set lf or uf, just
  10.         give it as argument."""
  11.         r = Entry()
  12.         r.M = self.M + bit
  13.         r.lf = self.lf if lf==None else lf
  14.         r.uf = self.uf if uf==None else uf
  15.         r.idx = self.idx + 1
  16.         return r
  17.  
  18.     def get(self, length):
  19.         """ Return the M filled with 1 so that len(M)==length. """
  20.         return '{1:1<{0}}'.format(length, self.M)
  21.  
  22.     def __repr__(self):
  23.         """ for debug. """
  24.         return 'Entry(M=%s, idx=%s, uf=%s ,lf=%s)'%(
  25.             repr(self.M), self.idx, self.uf, self.lf)
  26.  
  27.  
  28. def main(U, L, N):
  29.  
  30.     # translate U L to binary string.
  31.     ub = bin(U)[2:]
  32.     lb = bin(L)[2:]
  33.  
  34.     # let len(lb) == len(ub), filled with 0.
  35.     length = len(ub)
  36.     lb = '{1:0>{0}}'.format(length, lb)
  37.  
  38.     queue = [Entry()]   # start from (M='', idx=0, uf=False, lf=False)
  39.     candidates = []     # all candidates.
  40.     cnt = 0             # while counter, for test efficiency.
  41.  
  42.     while queue:        # do while the queue is not empty.
  43.         cnt += 1
  44.         now = queue.pop(0)
  45.  
  46.         # if both uf lf are set, we get a candidate.
  47.         if now.uf and now.lf:
  48.             candidates.append(now.get(length))
  49.             continue
  50.  
  51.         # if length is too large, this path is failed.
  52.         if now.idx >= length: continue
  53.  
  54.         # 4 conditions.
  55.         if   ub[now.idx] + lb[now.idx] == '10':
  56.             queue.append(now.nexts('1', lf=True))
  57.             queue.append(now.nexts('0', uf=True))
  58.  
  59.         elif ub[now.idx] + lb[now.idx] == '01':
  60.             if   now.lf:    queue.append(now.nexts('0'))
  61.             elif now.uf:    queue.append(now.nexts('1'))
  62.             else:           pass    # cut
  63.  
  64.         elif ub[now.idx] + lb[now.idx] == '00':
  65.             if not now.uf:  queue.append(now.nexts('0'))
  66.             else:           queue.append(now.nexts('1', lf=True))
  67.  
  68.         elif ub[now.idx] + lb[now.idx] == '11':
  69.             if not now.lf:  queue.qppend(now.nexts('1'))
  70.             else:
  71.                 queue.append(now.nexts('0', uf=True))
  72.                 queue.append(now.nexts('1'))
  73.  
  74.     print candidates
  75.     print 'len of candidates =', len(candidates)
  76.     print 'cnt =', cnt
  77.     print '-'*50
  78.  
  79.     ans = max((int(c,2) | N, c) for c in candidates)
  80.     print 'when M = %s(%s) has max.'%(ans[1], int(ans[1],2))
  81.     print 'M | N =', ans[0]
  82.  
  83.  
  84. if __name__=='__main__':
  85.     main(int(raw_input('U=')), int(raw_input('L=')), int(raw_input('N=')))
  86.  
Success #stdin #stdout 0.01s 7900KB
comments (?)
stdin
copy 
3567891
201310
30951344
stdout
copy 
U=L=N=['1011111111111111111111', '0111111111111111111111', '0011111111111111111111', '1100111111111111111111', '1101011111111111111111', '1101100011111111111111', '1101100101111111111111', '1101100110111111111111', '1101100111000011111111', '1101100111000100001111', '1101100111000100010001', '1101100111000100010010']
len of candidates = 12
cnt = 37
--------------------------------------------------
when M = 1011111111111111111111(3145727) has max.
M | N = 33554431
https://ideone.com/p0YzSV
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!