fork(1) download 
  1. import random
  2. import sys
  3. sys.setrecursionlimit(20000)
  4. nodes = 0
  5. depth = 0
  6.  
  7. def is_diff_sorted(qa):
  8.   diffs = [qa[i] - qa[i+1] for i in range(len(qa)-1)]
  9.   for i in range(len(diffs)-1):
  10.     if diffs[i] > diffs[i+1]:
  11.       return False
  12.   return True
  13.  
  14. def is_concave_end(a, x):
  15.   return a[-2] - a[-1] <= a[-1] - x
  16.  
  17. def append_element(sa, halves, labels, which, x):
  18.   labels.append(which)
  19.   halves[which].append(x)
  20.   if len(labels) == len(sa) or split_to_halves(sa, halves, labels):
  21.     return True
  22.   if which == 1 or not is_concave_end(halves[1], halves[0][-1]):
  23.     halves[which].pop()
  24.     labels.pop()
  25.     return False
  26.   labels[-1] = 1
  27.   halves[1].append(halves[0][-1])
  28.   halves[0].pop()
  29.   if split_to_halves(sa, halves, labels):
  30.     return True
  31.   halves[1].pop()
  32.   labels.pop()
  33.  
  34. def split_to_halves(sa, halves, labels):
  35.   global nodes, depth
  36.   nodes += 1
  37.   depth = max(depth, len(labels))
  38.  
  39.   x = sa[len(labels)]
  40.   if len(halves[0]) < 2 or is_concave_end(halves[0], x):
  41.     return append_element(sa, halves, labels, 0, x)
  42.   if is_concave_end(halves[1], x):
  43.     return append_element(sa, halves, labels, 1, x)
  44.  
  45. def make_concave(a):
  46.   sa = sorted(a, reverse = True)
  47.   halves = [[sa[0]], [sa[0], sa[1]]]
  48.   labels = [0, 1]
  49.   if split_to_halves(sa, halves, labels):
  50.     return list(reversed(halves[1][1:])) + halves[0]
  51.  
  52. #a = [10, 2, 7, 4]
  53.  
  54. h = [[], []]
  55. v = [0, 0]
  56. d = [0, 0]
  57. for i in range(5000):
  58.   for w in range(2):
  59.     if v[w] <= v[1-w]:
  60.       r = 5
  61.     else:
  62.       r = 10 + (v[w] - v[1-w]) * 2
  63.  
  64.     d[w] = random.randint(d[w], d[w] + r)
  65.     v[w] -= d[w]
  66.     h[w].append(v[w])
  67. a = h[0] + h[1]
  68.  
  69. print is_diff_sorted(make_concave(a))
  70. #print make_concave(a)
  71. print "depth", depth, "nodes", nodes
Success #stdin #stdout 0.27s 15192KB
comments (?)
stdin 
Standard input is empty
stdout 
True
depth 9999 nodes 11830
https://ideone.com/G39E48
language:
Python (cpython 2.7.16)
created:
9 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!