No.178 美しいWhitespace (1)

■■■問題■■■

太郎君は難解プログラミング言語である
Whitespaceでプログラムを作ることに熱中しています。
Whitespaceでは、スペース・タブ・改行のみを構文に使用し、その他は無視します。

太郎君はソースコードの美しさにこだわりがあり、
ソースコードについて、すべての行の幅が等しい時に「完璧」と呼びます。

太郎君は自分の書いたWhitespaceのソースコードに全角スペースを挿入することで
「完璧」にしようとしています。

太郎君がソースコードを「完璧」にするために必要な
最小の全角スペースの数を求めるプログラムを作ってください。

ただし、ある行のスペースの数をa、タブの数をb、全角スペースの数をcとしたとき、
その行の幅は(a+4b+2c)とします。

普通のエディタとは異なり、タブの位置などは幅に影響しません。

■■■入力■■■

N
a1 b1
・・・
aN bN

1行目に太郎君が完璧にしたいソースコードの行数Nが与えられます。
続くN行は、ソースコードの行ごとの情報です。i行目にはスペースがai個、タブがbi個あることを表します。

2 <= N <= 1000
0 <= ai,bi <= 1000万
太郎君のソースコードにはスペース・タブ・改行以外の文字は含まれません。
太郎君のソースコードがWhitespaceの文法的に正しいとは限りません。

■■■出力■■■

太郎君がWhitespaceのソースコードを「完璧」にできる時、必要な最小の全角スペースの数を出力してください。
「完璧」にすることが出来ない時、-1を出力してください。
最後に改行してください。 

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input4";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            WillReturn.Add("1 1");
            WillReturn.Add("3 0");
            //1
            //1行目はスペースが1個、タブが1個なので幅は1+1×4=5です。
            //2行目はスペースが3個、タブは0個なので幅は3+0×4=3です。
            //このままでは「完璧」でないですが、
            //2行目に全角スペースを1個足せば全ての行の幅が5となり「完璧」になるので、1を出力します。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("0 0");
            WillReturn.Add("0 0");
            WillReturn.Add("0 0");
            WillReturn.Add("0 0");
            //0
            //全ての行の幅ははじめから0で、すでに「完璧」です。
            //全角スペースを足す必要はないので、0を出力します。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2");
            WillReturn.Add("0 0");
            WillReturn.Add("1 0");
            //-1
            //1行目の幅は0で、2行目の幅は1です。
            //どのように全角スペースを足しても「完璧」にできないので、-1を出力します。
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4");
            WillReturn.Add("30 0");
            WillReturn.Add("20 10");
            WillReturn.Add("10 20");
            WillReturn.Add("0 30");
            //90
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        var ResultSet = new List<int>();
        foreach (string EachStr in InputList.Skip(1)) {
            int[] wkArr = EachStr.Split(' ').Select(X => int.Parse(X)).ToArray();
            ResultSet.Add(wkArr[0] + 4 * wkArr[1]);
        }

        //2を法として余りが0の集合
        List<int> Mod0List = ResultSet.FindAll(X => X % 2 == 0);

        //2を法として余りが1の集合
        List<int> Mod1List = ResultSet.FindAll(X => X % 2 == 1);

        //両方とも空集合でない場合
        if (Mod0List.Count > 0 && Mod1List.Count > 0) {
            Console.WriteLine(-1);
            return;
        }

        List<int> WkList = (Mod0List.Count == 0 ? Mod1List : Mod0List);
        int wkMax = WkList.Max();
        long Answer = 0;
        WkList.ForEach(X => Answer += (wkMax - X) / 2);
        Console.WriteLine(Answer);
    }
}

解説

2を法とした余りで分類した集合で考えてます。