Lại là Thang Máy

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 1000M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Một tòa nhà cao n tầng được đánh số từ tầng 1 đến tầng n có lắp 1 thang máy. Hiện nay thang máy bị trục trặc do đó mỗi lần có thể di chuyển k khả năng a1,a2...ak tầng với ai>0 là đi lên và ai<0 là đi xuống nếu nó đủ không gian di chuyển tức là xuống không quá tầng 1 và lên không quá tầng n. Thang máy đang ở tầng s một người ở đó muốn di chuyển đến tầng f hỏi số bước di chuyển ít nhất để đến được tầng f, trường hợp không di chuyển được xuất ra -1.

Input

Dòng đầu chứa n là số tầng của tòa nhà (1≤n≤104) và số nguyên dương k là số các khả năng di chuyển 1≤k≤100

Dòng thứ 2 chứa k số nguyên có giá trị tuyệt đối không vượt quá 103 nếu âm thì thang máy đi xuống, nếu dương là thang máy đi lên

Dòng thứ 3 chứa s và f (1<=s,f<=n) là vị trí tầng xuất phát và đích đến

Output

Số bước ít nhất di chuyển thang máy, nếu không đến được đích xuất ra -1

Example 1

Input

Copy
12 2
5 -7
1 8

Output

Copy
11

Giải thích: xuất phát từ tầng 1 mỗi lần lên đúng 5 tầng hoặc xuống đúng 7 tầng nếu có đủ không gian để lên hoặc xuống do đó cần 11 bước chuyển thang qua các tầng 1->6->11->4->9->2->7->12->5->10->3->8

Example 2

Input

Copy
120 2
-42 18
18 113

Output

Copy
-1
tichpx

Comments


  • 2
    CThành_CNTT6_K61  commented on May 29, 2021, 9:18 a.m. ← edited

    Em thấy vd 2 +19 14 lần và -43 4 lần có vẻ hợp lý mà thầy ơi


    • 2
      TICHPX  commented on May 29, 2021, 10:20 a.m. ← edited

      Cảm ơn em thầy đổi ví dụ rồi