ikemonn's blog

技術ネタをちょこちょこと

SRM 636 Div2 250 GameOfStones

問題文

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
広告を非表示にする