B. Running Student

Codeforces

IDCF9B

Time1000ms

Memory64MB

Difficulty—

brute forcegeometryimplementation

English · Original

Chinese · Translation

Formal · Original

And again a misfortune fell on Poor Student. He is being late for an exam. Having rushed to a bus stop that is in point (0, 0), he got on a minibus and they drove along a straight line, parallel to axis _OX_, in the direction of increasing _x_. Poor Student knows the following: * during one run the minibus makes _n_ stops, the _i_\-th stop is in point (_x__i_, 0) * coordinates of all the stops are different * the minibus drives at a constant speed, equal to _v__b_ * it can be assumed the passengers get on and off the minibus at a bus stop momentarily * Student can get off the minibus only at a bus stop * Student will have to get off the minibus at a terminal stop, if he does not get off earlier * the University, where the exam will be held, is in point (_x__u_, _y__u_) * Student can run from a bus stop to the University at a constant speed _v__s_ as long as needed * a distance between two points can be calculated according to the following formula: * Student is already on the minibus, so, he cannot get off at the first bus stop Poor Student wants to get to the University as soon as possible. Help him to choose the bus stop, where he should get off. If such bus stops are multiple, choose the bus stop closest to the University. ## Input The first line contains three integer numbers: 2 ≤ _n_ ≤ 100, 1 ≤ _v__b_, _v__s_ ≤ 1000. The second line contains _n_ non-negative integers in ascending order: coordinates _x__i_ of the bus stop with index _i_. It is guaranteed that _x_1 equals to zero, and _x__n_ ≤ 105. The third line contains the coordinates of the University, integers _x__u_ and _y__u_, not exceeding 105 in absolute value. ## Output In the only line output the answer to the problem — index of the optimum bus stop. [samples] ## Note As you know, students are a special sort of people, and minibuses usually do not hurry. That's why you should not be surprised, if Student's speed is higher than the speed of the minibus.

又一次不幸降临在可怜的学生身上。他考试要迟到了。他冲到位于点 #cf_span[(0, 0)] 的公交站，上了一辆小巴，小巴沿着一条与 #cf_span[OX] 轴平行的直线，朝 #cf_span[x] 增加的方向行驶。可怜的学生知道以下信息：学生希望尽快到达大学。请帮他选择应在哪个公交站下车。如果有多个这样的公交站，请选择离大学最近的那个。第一行包含三个整数：#cf_span[2 ≤ n ≤ 100]，#cf_span[1 ≤ vb, vs ≤ 1000]。第二行包含 #cf_span[n] 个按升序排列的非负整数：索引为 #cf_span[i] 的公交站的坐标 #cf_span[xi]。保证 #cf_span[x1] 等于零，且 #cf_span[xn ≤ 105]。第三行包含大学的坐标，两个整数 #cf_span[xu] 和 #cf_span[yu]，其绝对值不超过 #cf_span[105]。仅在一行中输出问题的答案——最优公交站的索引。正如你所知，学生是一种特殊的人群，而小巴通常不会着急。因此，如果学生的速度比小巴还快，你也不必感到惊讶。 ## Input 第一行包含三个整数：#cf_span[2 ≤ n ≤ 100]，#cf_span[1 ≤ vb, vs ≤ 1000]。第二行包含 #cf_span[n] 个按升序排列的非负整数：索引为 #cf_span[i] 的公交站的坐标 #cf_span[xi]。保证 #cf_span[x1] 等于零，且 #cf_span[xn ≤ 105]。第三行包含大学的坐标，两个整数 #cf_span[xu] 和 #cf_span[yu]，其绝对值不超过 #cf_span[105]。 ## Output 仅在一行中输出问题的答案——最优公交站的索引。 [samples] ## Note 正如你所知，学生是一种特殊的人群，而小巴通常不会着急。因此，如果学生的速度比小巴还快，你也不必感到惊讶。

**Parameters** * $n \in \mathbb{Z}$ such that $2 \le n \le 100$. * $v_b, v_s \in \mathbb{Z}$ such that $1 \le v_b, v_s \le 1000$. * $X = \{x_1, x_2, \dots, x_n\} \subset \mathbb{Z}_{\ge 0}$ where $x_1 = 0$ and $x_i < x_{i+1}$ for $1 \le i < n$. * $(x_u, y_u) \in \mathbb{Z}^2$ where $|x_u|, |y_u| \le 10^5$. **Definitions** For each bus stop index $i \in \{1, \dots, n\}$: 1. **Euclidean distance** from stop $i$ to the University: $$D(i) = \sqrt{(x_i - x_u)^2 + y_u^2}$$ 2. **Total travel time**: $$T(i) = \frac{x_i}{v_b} + \frac{D(i)}{v_s}$$ **Objective** Find the index $k \in \{1, \dots, n\}$ that minimizes the tuple $(T(k), D(k))$ lexicographically: $$k = \arg\min_{i \in \{1, \dots, n\}} \left( T(i), D(i) \right)$$ **Output** Output the integer $k$.

Samples

Input #1

4 5 2
0 2 4 6
4 1

Output #1

Input #2

2 1 1
0 100000
100000 100000

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Running Student",
    "description": {
      "content": "And again a misfortune fell on Poor Student. He is being late for an exam. Having rushed to a bus stop that is in point (0, 0), he got on a minibus and they drove along a straight line, parallel to a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF9B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "And again a misfortune fell on Poor Student. He is being late for an exam.\n\nHaving rushed to a bus stop that is in point (0, 0), he got on a minibus and they drove along a straight line, parallel to a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "又一次不幸降临在可怜的学生身上。他考试要迟到了。\n\n他冲到位于点 #cf_span[(0, 0)] 的公交站，上了一辆小巴，小巴沿着一条与 #cf_span[OX] 轴平行的直线，朝 #cf_span[x] 增加的方向行驶。\n\n可怜的学生知道以下信息：\n\n学生希望尽快到达大学。请帮他选择应在哪个公交站下车。如果有多个这样的公交站，请选择离大学最近的那个。\n\n第一行包含三个整数：#cf_span[2...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Parameters**\n*   $n \\in \\mathbb{Z}$ such that $2 \\le n \\le 100$.\n*   $v_b, v_s \\in \\mathbb{Z}$ such that $1 \\le v_b, v_s \\le 1000$.\n*   $X = \\{x_1, x_2, \\dots, x_n\\} \\subset \\mathbb{Z}_{\\ge 0}$ wher...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments