以下是来自日本的官方日本新闻原版PDF,已完整保存并按原样染色。


可复制的 PDF 提取文本
Building: ビルの飾りつけ
input ファイル“building.in”
output 標準出力
ソースファイルbuilding.c/building.cpp/Building.java
時間制限1 秒/ データ
国際情報オリンピックが日本で開かれることとなり,世界の選手達を歓迎するため,空港か
ら宿泊施設までの道沿いにある高層ビルを飾りつけることにした.ある著名なデザイナーにデ
ザインを依頼したところ,飾りつけに利用するビルは,空港から宿泊施設に向けて高くなって
いく必要があると言った.つまり,飾りつけに利用するビルの高さを,空港に近いものから順
にh1, h2, h3, · · · とおくと,h1 < h2 < h3 < · · · となっていなければならない.
できるだけ飾りつけを華やかにするため,飾りつけに利用するビルの数をできるだけ多くし
たい.入力として全てのビルの高さが与えられたとき,利用することのできるビルの数の最大
値を計算するプログラムを作れ.
Input. 入力ファイルbuilding.in の1 行目には,1 つの整数n (1 ≦n ≦1000) が書かれてい
る.これは,空港から宿泊施設までの道のりにあるビルの数がn であることを表す.
次のn 行には,それぞれのビルの高さが書かれてる.i + 1 行目(1 ≦i ≦n) には1 つの整数
ai(1 ≦ai ≦10000) が書かれている.これは,空港からi 個目のビルの高さがai であることを
表す.
Output. 出力は,標準出力に行うこと.飾りつけに利用することのできるビルの数の最大値
を表す整数を出力せよ.
例
building.in 標準出力
9 5
3
7
5
9
8
10
10
11
9
ビルの飾りつけ–1/2
ビルの総数が9 であり、高さが空港に近いものから順に3, 7, 5, 9, 8, 10, 10, 11, 9 である場合
を示したのが下図である。色をつけて示したビルを選ぶことにより、飾り付けに利用するビル
の数を最大にすることができる。このときの最大値は5 である。
空港 宿泊施設
ビルの飾りつけ–2/2