TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

100.0% (134/134)

Submission's AC Ratio

84.6% (170/201)

Tags

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 1

2 6 5

Sample Output 1

5 6 yes

Sample Input 2

2 5 7

Sample Output 2

5 7 no

Sample Input 3

3 9 8 7

Sample Output 3

7 9 yes

Sample Input 4

3 10 9 7

Sample Output 4

7 10 no

Sample Input 5

5 2 3 4 5 6

Sample Output 5

2 6 yes

Sample Input 6

5 2 3 4 5 7

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

No. Testdata Range Score
1 0~9 21
2 10~19 33
3 20~29 46

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 500 524288 262144 1
1 500 524288 262144 1
2 500 524288 262144 1
3 500 524288 262144 1
4 500 524288 262144 1
5 500 524288 262144 1
6 500 524288 262144 1
7 500 524288 262144 1
8 500 524288 262144 1
9 500 524288 262144 1
10 500 524288 262144 2
11 500 524288 262144 2
12 500 524288 262144 2
13 500 524288 262144 2
14 500 524288 262144 2
15 500 524288 262144 2
16 500 524288 262144 2
17 500 524288 262144 2
18 500 524288 262144 2
19 500 524288 262144 2
20 500 524288 262144 3
21 500 524288 262144 3
22 500 524288 262144 3
23 500 524288 262144 3
24 500 524288 262144 3
25 500 524288 262144 3
26 500 524288 262144 3
27 500 524288 262144 3
28 500 524288 262144 3
29 500 524288 262144 3