TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

91.8% (45/49)

Submission's AC Ratio

37.0% (60/162)

Tags

Description

你有一塊長M公尺的輕便可攜式木橋,正準備渡過一條寬P公尺的河流。這條河流上總共有N個木樁,這些木樁的排列方式恰好形成一條垂直於河流流向的直線。你是否能夠利用這塊可攜式木橋達到過河的任務呢?如果可以過河,至少要拆幾次橋呢?

你可以假設木樁只是一個點,不具有任何長度或寬度。

Input Format

輸入包含兩列,第一列有三個正整數M,P,N (1<=M,P<=231-1, 1<=N<=100)
第二列包含N個嚴格遞增的正整數S1,S2,...,SN (1<=Si<P)。

你要從河岸標記為0公尺的位置渡到標記為P公尺的對岸。

Output Format

如果可以過河,請輸出拆橋的次數。否則請輸出"IMPOSSIBLE"。

Sample Input

Sample Input #1:
8 50 10
2 6 14 22 30 38 46 47 48 49

Sample Input #2:
10 8 1
5

Sample Input #3:
1 100 1
50

Sample Output

Sample Output #1:
6

Sample Output #2:
0

Sample Output #3:
IMPOSSIBLE

Hints

關於 Sample Output #1


其中打*號代表木樁或河的兩岸,等號代表架的木橋:
0 50
----*-------*-------*-------*-------*-------*****
=========
      1
      =========
              2
              =========
                      3
                      =========

                              4
                              =========

                                      5
                                      =========

                                              6
                                          =========

p.s.這題是挑戰題喔,多動動腦吧:p

Problem Source

原TIOJ1057 / C/C++程式設計入門。Problem Setter: Tmt

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536