TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (30/30)

Submission's AC Ratio

89.7% (35/39)

Description

生物學家發現,與特定功能相關的一群基因在基因序列上的位置通常十分靠近,因此在不同的基因序列中如果都看見相同基因構成的連續片段 (順序不重要),這些基因構成的集合就被認為是有意義的,稱為基因群 (gene cluster)。例如: 如果在一條基因序列上看到一個片段內容為 $(a, b, c, d)$,同時在另外一條基因序列上看到一個片段內容為 $(d, b, a, c)$,那麼 $\{ a, b,c, d \}$ 就構成一組基因群。
找出基因群並不是一件容易的工作,有一個計算生物學家想到一個聰明的方法來簡化這個問題。經過他的簡化後,基因群辨識的主要工作會被轉換成: 輸入一個由相異正整數組成的序列 S,然後判斷 S 的內容是否構成連續的一串整數。例如: $S = (2, 5, 3, 4)$ 的內容構成連續的一串整數 $2, 3, 4, 5$;但是 $S = (2, 6, 3, 4)$ 的內容並不構成連續的一串整數 (缺了 $5$)。
給定一個數字所構成的序列,請撰寫一個程式來判斷這個序列中的數字是否構成連續的一串整數。

Input Format

測試資料是由一行的數字所構成 (數字間以一個以上的空白隔開),第一個數字 $n$ 表示所給定數字序列的長度,$1 < n \leq100$,接下來會有 $n$ 個相異的正整數 $m_i$,$1\leq i \leq n$ 且 $1 \leq m_i \leq 1000$,表示數字序列的內容。

Output Format

輸出一行,如果此序列中的數字構成連續的一串整數,請輸出: a b yes;不行則輸出: a b no,其中 $a$ 和 $b$ 分別代表序列中所有數字的最小值與最大值。$a$ 和 $b$ 之間以及 $b$ 和 yes/no之間,請以剛好一個空白隔開。(yes/no 請用小寫)

Sample Input

Sample Input #1
2 6 5

Sample Input #2
2 5 7

Sample Input #3
3 9 8 7

Sample Input #4
3 10 9 7

Sample Input #5
5 2 3 4 5 6

Sample Input #6
5 2 3 4 5 7

Sample Output

Sample Output #1
5 6 yes

Sample Output #2
5 7 no

Sample Output #3
7 9 yes

Sample Output #4
7 10 no

Sample Output #5
2 6 yes

Sample Output #6
2 7 no

Hints

本題共有三個子題,每一子題可有多筆測試資料:
第一子題,$n = 2$,解出可以獲得 21 分;
第二子題,$2 \leq n \leq 3$,解出可以獲得 33 分;
第三子題,$2 \leq n \leq 100$,解出可以獲得 46 分。

Problem Source

106學年度高級中學資訊學科能力競賽決賽 程式設計試題第一題

Subtasks

For Testdata: 0 ~ 9, Score: 21
For Testdata: 10 ~ 19, Score: 33
For Testdata: 20 ~ 29, Score: 46
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 500 524288 65536
1 500 524288 65536
2 500 524288 65536
3 500 524288 65536
4 500 524288 65536
5 500 524288 65536
6 500 524288 65536
7 500 524288 65536
8 500 524288 65536
9 500 524288 65536
10 500 524288 65536
11 500 524288 65536
12 500 524288 65536
13 500 524288 65536
14 500 524288 65536
15 500 524288 65536
16 500 524288 65536
17 500 524288 65536
18 500 524288 65536
19 500 524288 65536
20 500 524288 65536
21 500 524288 65536
22 500 524288 65536
23 500 524288 65536
24 500 524288 65536
25 500 524288 65536
26 500 524288 65536
27 500 524288 65536
28 500 524288 65536
29 500 524288 65536