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

ARC-036-A ぐっすり

■■■問題■■■

高橋くんはこれからN日間の睡眠の予定を建てることにしました。
i日目にはti分だけ寝る予定です。

また、高橋くんは連続した3日間の睡眠時間の合計がK分を下回ると、
その連続した3日目に睡眠不足になります。
厳密に言うと、x >= 3のときx-2日目、x-1日目、x日目の睡眠時間の合計がKを下回ると、
x日目に睡眠不足になります。合計がちょうどKになった場合は睡眠不足になりません。

あらかじめ高橋くんの睡眠の予定を与えるので、
高橋くんが睡眠不足になるかどうかを求めてください。
もし睡眠不足になるならば、何日目に睡眠不足になるか求めてください。
答えが複数通り考えられるならば、最初に睡眠不足になる日を求めてください。

高橋くんは1日目と2日目には睡眠不足にならないものとします。
また、高橋くんは昼寝しかしないので、睡眠により日をまたぐことは考えなくて良いです。

■■■入力■■■

N K
t1
t2
・
・
・
tN

●1行目には高橋くんが予定を建てた日数 N(3 <= N <= 10万) と
  睡眠不足の基準を表す整数 K(0 <= K <= 4320) が空白区切りで与えられる。
●2行目からのN行のうち
  i行目にはi日目に予定している睡眠時間を表す整数 ti(0 <= ti <= 1440) が与えられる。

■■■出力■■■

もし高橋くんがN日の間に睡眠不足にならないならば-1を1行に出力せよ。
もしなるならば、最初になる日を1行に出力せよ。


C#のソース

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

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("5 1080");
            WillReturn.Add("300");
            WillReturn.Add("420");
            WillReturn.Add("420");
            WillReturn.Add("180");
            WillReturn.Add("360");
            //4
            //2,3,4日目の睡眠時間の合計は1020分となっておりKを下回っています。
            //この日以前に睡眠不足になっている日はありません。
            //よって高橋くんは4日目に初めて睡眠不足になります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 180");
            WillReturn.Add("60");
            WillReturn.Add("60");
            WillReturn.Add("60");
            WillReturn.Add("60");
            WillReturn.Add("60");
            //-1
            //3日間の睡眠時間の合計がちょうどKの場合は
            //睡眠不足にならないことに注意してください。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 4230");
            WillReturn.Add("360");
            WillReturn.Add("360");
            WillReturn.Add("360");
            WillReturn.Add("360");
            WillReturn.Add("360");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int K = wkArr[1];
        int[] TArr = InputList.Skip(1).Select(X => int.Parse(X)).ToArray();

        int wkSum = 0;
        for (int I = 0; I <= TArr.GetUpperBound(0); I++) {
            wkSum += TArr[I];

            //和を調整
            if (I >= 3) wkSum -= TArr[I - 3];

            if (I >= 2 && wkSum < K) {
                Console.WriteLine(I + 1);
                return;
            }
        }
        Console.WriteLine(-1);
    }
}


解説

ナイーブにループさせて解いてます。