NEERC-2013 Solutions

README.md

NEERC-2013 Solutions

Author: Ale110

Olympiad homepage

My solutions to NEERC-2013 problems.

aplusb.py

"""
--- A Plus B v1.0
--- Filename: aplusb.py
---
--- (c) Ale110, 2013
"""

infile = open("aplusb.in", "rt");
outfile = open("aplusb.out", "wt");

c = int(infile.readline());
clen = len(str(c));

def isBeautiful(num):
  numstr = str(num);
  for i in range(0, len(numstr)-1):
    if (numstr[i] == numstr[i+1]):
      return False;
  return True;

count = 0;

for i in range(0, int(c/2)+1):
  j = c - i;
  if (isBeautiful(i)) and (isBeautiful(j)) and (len(str(i)) == clen) and (len(str(j)) == clen):
    count+=2;

outfile.write(str(count));

birch.py

"""
--- Birch v2.0
--- Filename: birch.py
---
--- (c) Ale110, 2013

Changelog:

v1.1 -> v2.0:
  + Now checks for trees on different sides
  
"""

import sys, math;

def listShift(lst):
  el = lst.pop()
  lst.reverse();
  lst.append(el);
  lst.reverse();
  return lst;

def pointsDist(a, b = [0, 0]):
  return math.sqrt((a[0]-b[0])*(a[0]-b[0])
                  +(a[1]-b[1])*(a[1]-b[1]));

def figureLen(fig):
  if len(fig) < 2:
    return 0;
  
  length = 0;
  for i in range(0, len(fig)-1):
    length += pointsDist(fig[i], fig[i+1]);

  length += pointsDist(fig[-1], fig[0]);

  return length;

def allTheCombinations(lst):
  if len(lst) == 1:
    return [lst]; # WTF?
  
  combos = [];
  
  for el in lst:
    nlst = lst+[]; # Forcing to create new object
    nlst.remove(el);
    for cmb in allTheCombinations(nlst):
      combos.append([el]+cmb);

  return combos;

def remDuplicate(lst):
  #for el in lst:
  #  if (lst.count(el) > 1):
  #    lst.remove(el)
  return lst;

def allTheRealCombinations(lst):
  # TODO: be faster
  combos = allTheCombinations(lst);
  ncombos = [];
  for i in range(0, len(lst)):
    for combo in combos:
      cmb = combo+[];
      for k in range(1, i):
        del cmb[-1];
      ncombos.append(cmb);
  return remDuplicate(ncombos);

def noTreesOnOneOfSides(trees):
  left = False;
  right = False;
  for tree in trees:
    if (tree[1] == 0):
      left = True;
    else:
      right = True;
  return not (left and right);

infile = open("birch.in", "rt");
outfile = open("birch.out", "wt");

### parsing ###

line = infile.readline().split();
length = int(line[0]);
width = int(line[1]);

trees = [];

leftcount = int(infile.readline());
line = infile.readline().split(" ");
for pos in line:
  trees.append([int(pos), 0]);
  
rightcount = int(infile.readline());
line = infile.readline().split(" ");
for pos in line:
  trees.append([int(pos), width]);

### /parsing ###

maxlen = 0;
for combo in allTheRealCombinations(trees):
  if (figureLen(combo) <= length):
    if (len(combo) > maxlen):
      if (noTreesOnOneOfSides(combo)):
        pass
      else:
        maxlen = len(combo);

outfile.write(str(maxlen));

casting.py

"""
--- Casting v1.2
--- Filename: casting.py
---
--- (c) Ale110, 2013
"""

infile = open("casting.in", "rt");
outfile = open("casting.out", "wt");

testtype = int(infile.readline());
abc = infile.readline().split(" ");
n = int(abc[0]);
a = int(abc[1]);
b = int(abc[2]);
c = int(abc[3]);

if testtype == 2:
  outfile.write(str(min([a, b, c])));
else:
  ### How do  I shot web
  # ((a) - (n-b)) - (n-c) = a+b+c-2n
  outfile.write(str(a+b+c-(2*n)));

cities.py

"""
--- Cities v1.1
--- Filename: cities.py
---
--- (c) Ale110, 2013
"""

infile = open("cities.in", "rt");
outfile = open("cities.out", "wt");

cities = [];

### Parsing input
size = int(infile.readline());

x = -1;
for line in infile:
  x += 1;
  for y in range(0, len(line)): # \n counts
                                # But won't be counted
    if line[y] == 'C':
      cities.append([x, y]);

# We need to find len/2 cites and routes between them
# Let's try to find a rectangle and assign it to 2nd country

for xmin in range(0, size):
  for ymin in range(0, size):
    for xmax in range(xmin, size):
      for ymax in range(ymin, size):
        print("Checking x:"+str(xmin)+"->"+str(xmax)+", y:"+str(ymin)+"->"+str(ymax));
        cities1 = [];
        cities2 = [];
        for city in cities:
          if (city[0] >= xmin) and (city[0] <= xmax) and (city[1] >= ymin) and (city[1] <= ymax):
            print (str(city)+" belongs to 2");
            cities2.append(city);
          else:
            print (str(city)+" belongs to 1");
            cities1.append(city);
        if (len(cities1) == len(cities2)):
          print("That's ok");

          # Printing answer
          for i in range(0, size):
            str = "";
            if (i < xmin) or (i > xmax):
              for j in range(0, size):
                str += "1";
            else:
              for j in range(0, size):
                if (j<ymin) or (j>ymax):
                  str += "1";
                else:
                  str += "2";
            outfile.write(str+"\n");
          exit(0);
        else:
          print("No good in it");