トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

ABC-033-B 町の合併

■■■問題■■■

N個の町が合併し、1つの新しい市になることになりました。
合併前の i(1 <= i <= N) 番目の町は名称がSiで、人口がPi人です。 
新しい市の名称を、以下のように決めようとしています。

●N個の町の人口の合計の過半数以上の人口を有する町が存在するならば、
  新しい市の名称はその町の名称を引き継ぐことにする。
●そのような町が存在しないならば、新しい市の名称はatcoderとする。

それぞれの町の名称と人口が与えられるので、合併後の新しい市の名称を出力してください。

■■■入力■■■

N
S1 P1
S2 P2
・
・
・
SN PN

●1行目には、整数 N(2 <= N <= 1000) が与えられる。
●2行目からN行では、それぞれの町の情報が与えられる。
  このうちi行目には、英小文字のみからなる長さ1以上20以下の文字列Siと
                     整数Pi(1 <= Pi <= 10万) が空白区切りで与えられる。
●S1, S2, ・・・ , SN は全て異なる。

■■■出力■■■

合併後の新しい市の名称を1行に出力せよ。
出力の末尾にも改行を入れること。


C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("4");
            WillReturn.Add("unagi 20");
            WillReturn.Add("usagi 13");
            WillReturn.Add("snuke 42");
            WillReturn.Add("smeke 7");
            //snuke
            //4つの町の合計人口は 20+13+42+7=82人です。
            //3番目の町はこの過半数以上の人口を有しています。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("a 10");
            WillReturn.Add("b 20");
            WillReturn.Add("c 30");
            WillReturn.Add("d 40");
            WillReturn.Add("e 100");
            //atcoder
            //5つの町の合計人口は 10+20+30+40+100=200 人ですが、
            //この過半数以上の人口を有する町は存在しないので、atcoderという市名になります。
            //なお、5番目の町は合計人口のちょうど半数の人口を有していますが、
            //過半数ではないことに注意してください。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("14");
            WillReturn.Add("yasuzuka 3340");
            WillReturn.Add("uragawara 4032");
            WillReturn.Add("oshima 2249");
            WillReturn.Add("maki 2614");
            WillReturn.Add("kakizaki 11484");
            WillReturn.Add("ogata 10401");
            WillReturn.Add("kubiki 9746");
            WillReturn.Add("yoshikawa 5142");
            WillReturn.Add("joetsu 100000");
            WillReturn.Add("nakago 4733");
            WillReturn.Add("itakura 7517");
            WillReturn.Add("kiyosato 3152");
            WillReturn.Add("sanwa 6190");
            WillReturn.Add("nadachi 3169");
            //joetsu
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct TownInfoDef
    {
        internal string S;
        internal int P;
    }

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

        var TownInfoList = new List<TownInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            string[] wkStrArr = EachStr.Split(' ');
            TownInfoDef WillAdd;
            WillAdd.S = wkStrArr[0];
            WillAdd.P = int.Parse(wkStrArr[1]);
            TownInfoList.Add(WillAdd);
        }
        int SumP = TownInfoList.Sum(X => X.P);
        int wkInd = TownInfoList.FindIndex(X => X.P * 2 > SumP);
        if (wkInd == -1) {
            Console.WriteLine("atcoder");
        }
        else Console.WriteLine(TownInfoList[wkInd].S);
    }
}


解説

人口の2倍 > 総人口 かを判定してます。