fork download
copy 
  1. import random
  2.  
  3. def check(n, k, s, p):
  4.   seat1 = s[0] + n - 1
  5.   best = 0
  6.   unlucky = 0
  7.  
  8.   circle = [(0, 0)] * n # (tag, index) tag: 0=empty, 1=seat, 2=person
  9.   for i, pos in enumerate(s):
  10.     circle[pos-1] = (1, i+1)
  11.   for i, pos in enumerate(p):
  12.     if (circle[pos-1][0] == 1):
  13.       circle[pos-1] = (0, 0)
  14.       if pos-1 == seat1 - n:
  15.         best = i+1
  16.     else:
  17.       circle[pos-1] = (2, i+1)
  18.   double = circle * 2
  19.  
  20.   for step in range(n):
  21.     pos = 2 * n - 1
  22.     while pos > 0:
  23.       if double[pos][0] == 1 and double[pos-1][0] == 2:
  24.         if pos == seat1:
  25.           best = double[pos-1][1]
  26.         double[pos] = (0, 0)
  27.       elif double[pos][0] != 1 and double[pos-1][0] != 1:
  28.         double[pos] = double[pos-1]
  29.         if double[pos][0] == 2:
  30.           unlucky = double[pos][1]
  31.       elif double[pos][0] == 2:
  32.         double[pos] = (0, 0)
  33.       pos -= 1
  34.     double[0] = (0, 0)
  35.  
  36.   #print(double)
  37.   return (best, unlucky)
  38.  
  39.  
  40. def solve(k, s, p):
  41.   seat1 = s[0]
  42.   best = -1
  43.   unlucky = (0, -1) # min(accum), position
  44.   accum = 1
  45.  
  46.   # process all persons between start of the array and the seat #1 position
  47.   for i, pos in enumerate(p):
  48.     if pos <= seat1:
  49.       best = i+1
  50.       accum -= 1
  51.     else:
  52.       break
  53.  
  54.   if accum < 0:
  55.     unlucky = (accum, 1)
  56.  
  57.   # process all seats/persons in reverse direction
  58.   i = k
  59.   j = k-1
  60.   while i >= 0 and p[i] > seat1:
  61.     if s[j] >= p[i]: # a seat
  62.       accum += 1
  63.       j -= 1
  64.     else: # a person
  65.       accum -= 1
  66.       i -= 1
  67.  
  68.     if best == -1 and accum == 0:
  69.       best = i+2 # +1 because indexing starts with 0 & +1 because of pre-decrement
  70.  
  71.     if accum < unlucky[0]:
  72.       unlucky = (accum, i+2)
  73.  
  74.   return (best, unlucky[1])
  75.  
  76.  
  77. #ss = [2,5,8]
  78. #pp = [3,4,6,8]
  79. k = 25
  80. ss = []
  81. pp = []
  82. v = 0
  83. for i in range(k):
  84.   v += random.randint(1, 10)
  85.   ss.append(v)
  86. v = 0
  87. for i in range(k+1):
  88.   v += random.randint(1, 10)
  89.   pp.append(v)
  90. n = max(max(ss), max(pp)) + 40
  91. print(check(n, k, ss, pp))
  92. print(solve(k, ss, pp))
  93.  
Success #stdin #stdout 0.07s 10296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(1, 3)
(1, 3)
https://ideone.com/cn12Su
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!