{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"問題文","value":{"format":"HTML","content":"\r\n\r\n\u003csection\u003e\r\n 高橋君はもう大人なので、親元を離れて一人暮らしをすることにしました。トラックから引越し先の部屋へと荷物のダンボールを運びたいのですが、部屋の床がダンボールで埋まってしまうと、今日高橋君が寝るための布団がひけません。\u003cbr\u003e\r\n そこで、\u003cvar\u003e\\(1\\)\u003c/var\u003e 箱ずつ広げて置くのではなく、ある程度ダンボールを積み重ねた山を作ることにしました。しかし、ダンボールには重さが決まっており、下にあるダンボールよりも重いダンボールを上に積み重ねると下のダンボールが潰れてしまいます。\u003cbr\u003e\r\n\u003cdiv class\u003d\"img-caption\"\u003e\r\n\t\u003cimg src\u003d\"CDN_BASE_URL/43933ae7f21f8881740ddef89bd24c5a?v\u003d1715259280\" width\u003d\"300\" height\u003d\"187\"\u003e\r\n\t\u003cdiv class\u003d\"caption\"\u003e図:下にあるダンボールは上にあるダンボール以上の重さでなければならない\u003c/div\u003e\r\n\u003c/div\u003e\r\n\r\n\u003cbr\u003e\r\n トラックから運ぶ順にダンボールの重さが与えられるので、ダンボールを潰さないような積み重ね方を考えなさい。そして、その積み重ねた山の個数が最小となる場合の山の個数を求めなさい。\r\n\u003c/section\u003e\r\n"}},{"title":"入力","value":{"format":"HTML","content":"\r\n\r\n\u003csection\u003e\r\n入力は以下の形式で標準入力から与えられる。\r\n\u003cpre\u003e\r\n\u003cvar\u003e\\(N\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(w_1\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(w_2\\)\u003c/var\u003e\r\n:\r\n:\r\n\u003cvar\u003e\\(w_N\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\u003cul\u003e\r\n\t\u003cli\u003e入力は \u003cvar\u003e\\(N+1\\)\u003c/var\u003e 行ある。\u003c/li\u003e\r\n\t\u003cli\u003e\u003cvar\u003e\\(1\\)\u003c/var\u003e 行目には、ダンボールの個数を表す整数 \u003cvar\u003e\\(N(1≦N≦50)\\)\u003c/var\u003e が与えられる。\u003c/li\u003e\r\n\t\u003cli\u003e\u003cvar\u003e\\(2\\)\u003c/var\u003e 行目からの \u003cvar\u003e\\(N\\)\u003c/var\u003e 行には、\u003cvar\u003e\\(i+1(1≦i≦N)\\)\u003c/var\u003e 行目に \u003cvar\u003e\\(i\\)\u003c/var\u003e 番目に運ぶダンボールの重さを表す整数 \u003cvar\u003e\\(w_i(1≦w_i≦100,000)\\)\u003c/var\u003e が与えられる。 \r\n\u003c/li\u003e\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"出力","value":{"format":"HTML","content":"\r\n\r\n\u003csection\u003e\r\nダンボールを順番に運び、上のダンボールが下のダンボールと同じ重さまたはそれよりも軽くなるように積み重ねたときに、できるダンボールの山の数の最小値を標準出力に \u003cvar\u003e\\(1\\)\u003c/var\u003e 行で出力せよ。\u003cbr\u003e\r\nなお、最後には改行を出力せよ。\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n5\r\n4\r\n3\r\n1\r\n2\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e下図の例の順に積み重ねると、\u003cvar\u003e\\(2\\)\u003c/var\u003e つのダンボールの山ができる。\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(3\\)\u003c/var\u003e 番目のダンボールの次に重さ \u003cvar\u003e\\(2\\)\u003c/var\u003e のダンボールをその上に重ねることはできないので \u003cvar\u003e\\(1\\)\u003c/var\u003e つの山にすることはできず、最小は \u003cvar\u003e\\(2\\)\u003c/var\u003e となる。\r\n\u003c/li\u003e\u003c/ul\u003e\r\n\u003cdiv class\u003d\"img-nocaption\"\u003e\r\n\t\u003cimg src\u003d\"CDN_BASE_URL/bba2f0bd3809b044e07f8228fecbdfd3?v\u003d1715259280\" width\u003d\"800\" height\u003d\"156\"\u003e\r\n\u003c/div\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n7\r\n93\r\n249\r\n150\r\n958\r\n442\r\n391\r\n25\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e下図の形に積み重ねると、山の数は \u003cvar\u003e\\(3\\)\u003c/var\u003e となる。\u003c/li\u003e\r\n\u003cdiv class\u003d\"todo\"\u003e訂正:下図の225のダンボールは25の誤りです。申し訳ありません。\u003c/div\u003e\r\n\u003c/ul\u003e\r\n\u003cdiv class\u003d\"img-nocaption\"\u003e\r\n\t\u003cimg src\u003d\"CDN_BASE_URL/4c2f398f99b599a6fdd1a101b066114d?v\u003d1715259280\" width\u003d\"300\" height\u003d\"259\"\u003e\r\n\u003c/div\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n4\r\n100\r\n100\r\n100\r\n100\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e同じ重さのダンボールは積み重ねられるので、\u003cvar\u003e\\(1\\)\u003c/var\u003e つの山にすることができる。\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 4","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n6\r\n5\r\n10\r\n15\r\n20\r\n25\r\n30\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003eどのダンボールも前に運んだダンボールの上に重ねられないので、\u003cvar\u003e\\(1\\)\u003c/var\u003e つも積み重ねることができない。\u003c/li\u003e\r\n\u003cli\u003eしたがって、\u003cvar\u003e\\(6\\)\u003c/var\u003e つの山が最小となる。\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 5","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n15\r\n3\r\n1\r\n4\r\n1\r\n5\r\n9\r\n2\r\n6\r\n5\r\n3\r\n5\r\n8\r\n9\r\n7\r\n9\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003csection\u003e\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e下図のように積み重ねると最小となる。\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cdiv class\u003d\"img-nocaption\"\u003e\r\n\t\u003cimg src\u003d\"CDN_BASE_URL/7138e19866f60cb9c857eeabd4a8d121?v\u003d1715259280\" width\u003d\"500\" height\u003d\"168\"\u003e\r\n\u003c/div\u003e\r\n\u003c/section\u003e\r\n"}}]}