1057 . [入門]難度5.過河拆橋

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Y(OwO)Y
真実より 優しい嘘をプリーズ

User's AC Ratio

89.7% (140/156)

Submission's AC Ratio

30.4% (174/573)

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 1

8 50 10
2 6 14 22 30 38 46 47 48 49

Sample Output 1

6

Sample Input 2

10 8 1
5

Sample Output 2

0

Sample Input 3

1 100 1
50

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

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
Submit
Back to Top