Pongeponge

Codingame『The Gift』クリア

IMGP7062IMGP7062 / 丹波写眞 Tamba photo


 ギフトがどうとか、予算がどうとか、寄付金の最大金額が小さくなるようにとか。
それって簡単に言えば年貢でしょ?
www.codingame.com

年貢を徴収するぞ!

 説明を読んでもいまいち要領を得ないので*1
「年貢の話かな?」と頭の中で置き換えたらできた。
要は全村に均等に負担させつつ徴収目標を達成する、ってことですよね。

Source code
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Solution
{
    static void Main(string[] args)
    {
        //村の数
        int N = int.Parse(Console.ReadLine());
        //徴収する年貢の総量
        int C = int.Parse(Console.ReadLine());

        //村の収穫量リスト作成
        int[] v = new int[N];
        for (int i = 0; i < N; i++)
        {
            v[i] = int.Parse(Console.ReadLine());
        }

        //収穫量の昇順ソート
        Array.Sort(v);

        //年貢の平均負担量        
        int Ave = C / N;
        //余り
        int q = C % Ave;

        //村々をまわる
        for (int i = 0; i < N - 1; i++)
        {
            //収穫分から年貢を徴収する
            int remain = v[i] - Ave;
            if (remain >= 0)         //年貢を払えるなら
            {
                //総徴収量から負担分を引いて更新する
                C -= Ave;
                //Output用に書き換える
                v[i] = Ave;
            }
            else {                  //払えないのなら
                //あるだけ根こそぎ奪う
                C -= v[i];
            }

            //再び残りから平均負担量と余りを求める(足りない分は別から村から取る)
            Ave = C / (N - (i + 1));
            if (Ave > 0)
            {
                q = C % Ave;
            }
            else {
                q = 0;
            }
        }

        if (Ave + q > v[v.Length - 1])  //最後の村の年貢が足りなければ
        {     
            Console.WriteLine("IMPOSSIBLE");
        }
        else {                          //年貢が足りるなら
            v[v.Length - 1] = Ave + q;
            foreach (int n in v)
            {
                Console.WriteLine(n);
            }
        }

    }
}


*1:英語だから