← 返回题目列表

AtCoder · joi2007ho_b

B. 最长的楼梯

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

最長の階段 - 原题 PDF 第 1 页
原题PDF第3页
最長の階段 - 原题 PDF 第 2 页
原始 PDF 第 4 部分
可复制的 PDF 提取文本
2                    最長の階段 


問題

  1 からn までの整数がそれぞれ1 つずつ書かれたn 枚のカードと,1 枚の白紙の
カードがある.これらn + 1 枚のカードの内,k 枚のカードが与えられる.ただし,
1 ≦k ≦n である.白紙のカードには1 からn までの整数を1 つ書くことができ
る.与えられたカードだけで,できるだけ長い連続した整数列を作りたい.
 与えられるカードが入力されたときに, 与えられたカードから作ることができる連
続した整数列の最大長を出力するプログラムを作成せよ.


例

例1

  n = 7, k = 5 とする.6, 2, 4, 7, 1 のカードが与えられたとき,このカードを使っ
て作れる連続した整数列のうち最長のものは1, 2 であり,その長さは2 である.


例2

  n = 7, k = 5 とする.6, 2, 4, 7 と白紙のカードが与えられたとき,このカードを
使って作れる連続した整数列のうち最長のものは,白紙のカードに5 を書くことに
よってできる4, 5, 6, 7 であり,その長さは4 である.


入力

 入力ファイルのファイル名はinput.txt である.
  1 行目には,2 つの整数n (1 ≦n ≦100000) とk (1 ≦k ≦n) がこの順で1 つの
空白を区切りとして書かれている.続くk 行には整数が1 つずつ書かれており,与
えられるk 枚のカードに書かれている整数を表している.白紙のカードは0 で表さ
れる.
 採点用データのうち, 配点の40% 分は1 ≦n ≦1000, 1 ≦k ≦500 を, 配点の
20% 分は1 ≦n ≦60000, 1 ≦k ≦50000 を. 配点の40% 分は1 ≦n ≦100000,
1 ≦k ≦100000 を満たす.




                        問題2-1

出力

 出力ファイルのファイル名はoutput.txt である.
  output.txt は1 行だけからなり,その1 行は出力する整数1 つだけを含む.


入出力の例

入出力の例1

 例1 に対応する入出力は以下の通りである.
input.txt

     7 5
     6
     2
     4
     7
     1

output.txt

     2


入出力の例2

 例2 に対応する入出力は以下の通りである.
input.txt

     7 5
     6
     2
     0
     4
     7

output.txt

     4





                        問題2-2