Limak has found a large field with some piles of stones.
Limak likes perfection. It would make him happy if every pile had the same number of stones. He is now going to move some stones between the piles to make them all equal.
However, there is a catch. Limak's perfectionism does not allow him to carry just one stone at a time. As he has two hands, he must always carry exactly two stones: one in each hand. Thus, he can only make one type of an action: pick up two stones from one of the piles and carry both of them to some other pile. He is not allowed to remove a pile completely. Therefore, he cannot pick up stones from a pile that currently contains fewer than 3 stones.
You are given a int stones. Each element of stones is the initial number of stones in one of the piles. Compute and return the smallest number of actions Limak has to perform in order to make all piles equal. If it is impossible to make all piles equal using the allowed type of actions, return -1 instead.
# -*- coding: utf-8 -*- import math,string,itertools,fractions,heapq,collections,re,array,bisect class GameOfStones: def count(self, stones): if len(stones) <= 1: return 0 sum_stones = sum(stones) if sum_stones % len(stones) != 0: return -1 avg = sum_stones / len(stones) sum_gt_avg = 0 for i in stones: if i > avg: diff = i - avg if (i-avg) % 2 != 0: return -1 sum_gt_avg += diff if sum_gt_avg % 2 != 0: return -1 return sum_gt_avg / 2
class GameOfStones: def count(self, stones): if len(stones) <= 1: return 0 sum_stones = sum(stones) if sum_stones % len(stones) != 0: return -1 avg = sum_stones / len(stones) result = 0 for i in stones: if (i-avg) % 2 != 0: return -1 if i > avg: result += (i-avg)/2 return result