import random
import math
random.seed("regional-2016/day02/game")

def random_array(N, DIFF, MAX_VAL, MIN_CNT, MAX_CNT):
  if not ((1 <= N) and (1 <= DIFF) and (1 <= MIN_CNT) and (DIFF * MIN_CNT <= N) and (N <= MAX_CNT * DIFF) and (DIFF <= MAX_VAL)):
    raise "Invalid parameters"
  counts = [0] * DIFF
  lost = N
  for i in range(DIFF - 1, -1, -1):
    cur_min_cnt = max(MIN_CNT, lost - MAX_CNT * i)
    cur_max_cnt = min(MAX_CNT, lost - MIN_CNT * i)
    assert(MIN_CNT <= cur_min_cnt and cur_min_cnt <= cur_max_cnt and cur_max_cnt <= MAX_CNT)
    counts[i] = random.randint(cur_min_cnt, cur_max_cnt)
    lost -= counts[i]
  random.shuffle(counts)
  values = set()
  while len(values) < DIFF:
    values.add(random.randint(1, MAX_VAL))
  values = list(values)

  array = list()
  for i in range(DIFF):
    for j in range(counts[i]):
      array.append(values[i])
  random.shuffle(array)
  return array

class TestGen:
  def __init__(self):
    self.test_number = 0
    self.subtask = ""
    self.desc_file = open("../tests.desc", "w")

  def generate_samples(self):       
    self.print_test(2, [1, 1, 2, 2, 3], "preliminary")

  def generate_first_group_of_tests(self, folder):
    self.subtask = folder
    self.print_test(1, [1, 1, 1])
    self.print_test(1, [100000, 99999, 99998])
    self.print_test(1, [100000, 1, 99999])
    self.print_test(1, [99999] * 3)
    self.print_test(1, [100000] * 100000)
    self.print_test(1, list(range(1, 100001, 1)))
    self.print_test(1, list(range(100000, 0, -10)) * 10)
    self.print_test(1, random_array(100000, 100000, 100000, 1, 1))
    self.print_test(1, random_array(100000, 40000,  100000, 2, 3))
    self.print_test(1, random_array(100000, 10000,  100000, 10, 10))
    self.print_test(1, random_array(100000, 4, 100000, 10, 40000))

  def generate_second_group_of_tests(self, folder):
    self.subtask = folder
    self.print_test(3, [1, 2, 4])
    self.print_test(99, [100, 99, 2, 1])
    self.print_test(99, [100, 99, 2, 1, 100, 99, 2, 1])
    self.print_test(99, [100, 99, 2, 1, 100, 99, 2, 1, 100, 99, 2, 1])
    self.print_test(99, random_array(23, 13, 100, 1, 4))
    self.print_test(10, random_array(50, 20, 100, 1, 3))
    self.print_test(17, random_array(50, 1, 100, 1, 50))
    self.print_test(17, random_array(100, 2, 100, 1, 50))
    self.print_test(17, random_array(100, 3, 100, 1, 50))
    self.print_test(2, random_array(100, 40, 100, 1, 4))
    self.print_test(5, random_array(50, 50, 100, 1, 1))
    self.print_test(100, random_array(50, 50, 100, 1, 1))
    self.print_test(49, random_array(50, 50, 50, 1, 1))
    self.print_test(7, random_array(48, 16, 100, 3, 3))
    self.print_test(20, random_array(100, 50, 100, 2, 2))
    self.print_test(2, random_array(50, 13, 100, 3, 4))

  def generate_second_group_of_tests_old(self, folder):
    self.subtask = folder
    self.print_test(3, [1, 2, 4])
    self.print_test(99, [100, 99, 2, 1])
    self.print_test(99, [100, 99, 2, 1, 100, 99, 2, 1])
    self.print_test(99, [100, 99, 2, 1, 100, 99, 2, 1, 100, 99, 2, 1])
    
    self.print_test(5, random_array(100, 100, 100, 1, 1))
    self.print_test(6, random_array(200, 100, 100, 2, 2))
    self.print_test(7, random_array(300, 100, 100, 3, 3))
    self.print_test(7, random_array(250, 100, 100, 1, 4))
    self.print_test(17, random_array(100000, 100, 100, 1, 50000))
    self.print_test(99, random_array(100000, 100, 100, 1, 10000))
    self.print_test(2, random_array(100000, 100, 100, 1, 5000))
    self.print_test(7, random_array(100000, 100, 100, 1000, 1000))

  def generate_third_group_of_tests(self, folder):
    self.subtask = folder
    self.print_test(3, [1, 2, 4])
    self.print_test(999999999, [1000000000, 999999999, 2, 1])
    
    self.print_test(50, list(range(1000000000, 0, -10000)))
    self.print_test(990000000, random_array(100000, 100000, 1000000000, 1, 1))
    self.print_test(100000, random_array(100000, 100000, 1000000000, 1, 1))
    self.print_test(1798, random_array(100000, 100000, 1000000000, 1, 1))
    self.print_test(174512, random_array(100000, 100000, 1000000000, 1, 1))
    self.print_test(2000, random_array(100000, 100000, 1000000000, 1, 1))
    self.print_test(1000000000, random_array(100000, 100000, 1000000000, 1, 1))
    self.print_test(7000, random_array(100000, 100000, 10000000, 1, 1))
    self.print_test(5, random_array(100000, 100000, 10000000, 1, 1))

  def generate_fourth_group_of_tests(self, folder):
    self.subtask = folder
    self.print_test(3, [1, 2, 4])
    self.print_test(999999999, [1000000000, 999999999, 2, 1])
    self.print_test(999999999, [1000000000, 999999999, 2, 1, 1000000000, 999999999, 2, 1])
    self.print_test(999999999, [1000000000, 999999999, 2, 1, 1000000000, 999999999, 2, 1, 1000000000, 999999999, 2, 1])
    
    self.print_test(50, list(range(1000000000, 0, -10000)))
    self.print_test(990000000, random_array(23470, 13000, 1000000000, 1, 4))
    self.print_test(100000, random_array(100000, 40000, 1000000000, 1, 3))
    self.print_test(1, random_array(100000, 1, 1000000000, 1, 100000))
    self.print_test(1798, random_array(100000, 2, 1000000000, 1, 100000))
    self.print_test(174512, random_array(100000, 3, 1000000000, 1, 100000))
    self.print_test(2000, random_array(100000, 40000, 1000000000, 1, 4))
    self.print_test(1, random_array(100000, 40000, 1000000000, 1, 4))
    self.print_test(57834, random_array(100000, 100000, 1000000000, 1, 1))
    self.print_test(100, random_array(100000, 100000, 1000000000, 1, 1))
    self.print_test(1000000000, random_array(100000, 100000, 1000000000, 1, 1))
    self.print_test(200, random_array(99999, 33333, 10000000, 3, 3))
    self.print_test(7000, random_array(100000, 50000, 10000000, 2, 2))
    self.print_test(5, random_array(100000, 26000, 10000000, 3, 4))

  
  def print_test(self, k, arr, dirname="tests"):
    self.test_number += 1
    print("Generating test %d" % self.test_number)

    n = len(arr)
    description = "n = %d, k = %d, minx = %d, maxx = %d, diff = %d" % (n, k, min(arr), max(arr), len(set(arr)))
    
    folder = "../" + dirname + self.subtask
    test_name = folder + "/{0:0=2d}".format(self.test_number)
    if not os.path.exists(folder):
      os.makedirs(folder)
    test_file = open(test_name, "w")
    print(n, k, file=test_file)
    print(*arr, file=test_file)
    print(test_name + "\t" + description, file=self.desc_file)
    test_file.close()

  def generate_all_tests(self):
    self.generate_samples() 
    self.test_number = 0
    
    self.generate_first_group_of_tests("/subtask1")
    self.generate_second_group_of_tests("/subtask2")
    self.generate_third_group_of_tests("/subtask3")
    self.generate_fourth_group_of_tests("/subtask4")
#    self.generate_fifth_group_of_tests("/subtask5")


import os, shutil
if os.path.exists('../tests'):
  shutil.rmtree('../tests', ignore_errors=False, onerror=None)
if os.path.exists('../preliminary'):
  shutil.rmtree('../preliminary', ignore_errors=False, onerror=None)
try:
  os.makedirs('../tests')
  os.makedirs('../preliminary')
except OSError:
  pass

import time
start = time.time()
writer = TestGen()
writer.generate_all_tests()
finish = time.time()
print('All tests were generated. Elapsed time: ', finish - start)
