B. Hamster Farm

Codeforces

IDCF939B

Time2000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Dima has a hamsters farm. Soon _N_ hamsters will grow up on it and Dima will sell them in a city nearby. Hamsters should be transported in boxes. If some box is not completely full, the hamsters in it are bored, that's why each box should be completely full with hamsters. Dima can buy boxes at a factory. The factory produces boxes of _K_ kinds, boxes of the _i_\-th kind can contain in themselves _a__i_ hamsters. Dima can buy any amount of boxes, but he should buy boxes of only one kind to get a wholesale discount. Of course, Dima would buy boxes in such a way that each box can be completely filled with hamsters and transported to the city. If there is no place for some hamsters, Dima will leave them on the farm. Find out how many boxes and of which type should Dima buy to transport maximum number of hamsters. ## Input The first line contains two integers _N_ and _K_ (0 ≤ _N_ ≤ 1018, 1 ≤ _K_ ≤ 105) — the number of hamsters that will grow up on Dima's farm and the number of types of boxes that the factory produces. The second line contains _K_ integers _a_1, _a_2, ..., _a__K_ (1 ≤ _a__i_ ≤ 1018 for all _i_) — the capacities of boxes. ## Output Output two integers: the type of boxes that Dima should buy and the number of boxes of that type Dima should buy. Types of boxes are numbered from 1 to _K_ in the order they are given in input. If there are many correct answers, output any of them. [samples]

Dima 有一个仓鼠农场。不久后，将有 $N$ 只仓鼠在农场长大，Dima 将把它们运到附近的城市场销售。仓鼠必须装在箱子里运输。如果某个箱子没有装满，里面的仓鼠会感到无聊，因此每个箱子都必须完全装满仓鼠。 Dima 可以从工厂购买箱子。工厂生产 $K$ 种类型的箱子，第 $i$ 种类型的箱子可以容纳 $a_i$ 只仓鼠。Dima 可以购买任意数量的箱子，但他只能选择购买一种类型的箱子以获得批发折扣。当然，Dima 会以这样的方式购买箱子：每个箱子都能被完全装满并运送到城市。如果有些仓鼠没有足够的箱子容纳，Dima 将把它们留在农场。请找出 Dima 应该购买哪种类型的箱子以及购买多少个，以便运输尽可能多的仓鼠。第一行包含两个整数 $N$ 和 $K$（$0 ≤ N ≤ 10^{18}$，$1 ≤ K ≤ 10^5$）——将在 Dima 农场长大的仓鼠数量和工厂生产的箱子类型数量。第二行包含 $K$ 个整数 $a_1, a_2, \dots, a_K$（对所有 $i$，满足 $1 ≤ a_i ≤ 10^{18}$）——每种箱子的容量。请输出两个整数：Dima 应该购买的箱子类型编号，以及该类型箱子的数量。箱子类型从 $1$ 到 $K$ 编号，编号顺序与输入顺序一致。如果有多个正确答案，输出任意一个即可。 ## Input 第一行包含两个整数 $N$ 和 $K$（$0 ≤ N ≤ 10^{18}$，$1 ≤ K ≤ 10^5$）——将在 Dima 农场长大的仓鼠数量和工厂生产的箱子类型数量。第二行包含 $K$ 个整数 $a_1, a_2, \dots, a_K$（对所有 $i$，满足 $1 ≤ a_i ≤ 10^{18}$）——每种箱子的容量。 ## Output 请输出两个整数：Dima 应该购买的箱子类型编号，以及该类型箱子的数量。箱子类型从 $1$ 到 $K$ 编号，编号顺序与输入顺序一致。如果有多个正确答案，输出任意一个即可。 [samples]

**Definitions** Let $ N \in \mathbb{Z}_{\geq 0} $ be the number of hamsters. Let $ K \in \mathbb{Z}^+ $ be the number of box types. Let $ A = (a_1, a_2, \dots, a_K) $ be a sequence of positive integers, where $ a_i \in \mathbb{Z}^+ $ is the capacity of box type $ i $. **Constraints** 1. $ 0 \leq N \leq 10^{18} $ 2. $ 1 \leq K \leq 10^5 $ 3. $ 1 \leq a_i \leq 10^{18} $ for all $ i \in \{1, \dots, K\} $ **Objective** Find $ i^* \in \{1, \dots, K\} $ and $ x^* \in \mathbb{Z}_{\geq 0} $ such that: $$ x^* \cdot a_{i^*} = \max_{i \in \{1, \dots, K\}} \left( \left\lfloor \frac{N}{a_i} \right\rfloor \cdot a_i \right) $$ and output $ (i^*, x^*) = \left(i^*, \left\lfloor \frac{N}{a_{i^*}} \right\rfloor \right) $. If multiple $ i^* $ achieve the maximum, output any.

Samples

Input #1

19 3
5 4 10

Output #1

2 4

Input #2

28 3
5 6 30

Output #2

1 5

API Response (JSON)

{
  "problem": {
    "name": "B. Hamster Farm",
    "description": {
      "content": "Dima has a hamsters farm. Soon _N_ hamsters will grow up on it and Dima will sell them in a city nearby. Hamsters should be transported in boxes. If some box is not completely full, the hamsters in i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF939B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Dima has a hamsters farm. Soon _N_ hamsters will grow up on it and Dima will sell them in a city nearby.\n\nHamsters should be transported in boxes. If some box is not completely full, the hamsters in i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Dima 有一个仓鼠农场。不久后，将有 $N$ 只仓鼠在农场长大，Dima 将把它们运到附近的城市场销售。\n\n仓鼠必须装在箱子里运输。如果某个箱子没有装满，里面的仓鼠会感到无聊，因此每个箱子都必须完全装满仓鼠。\n\nDima 可以从工厂购买箱子。工厂生产 $K$ 种类型的箱子，第 $i$ 种类型的箱子可以容纳 $a_i$ 只仓鼠。Dima 可以购买任意数量的箱子，但他只能选择购买一种类型的箱子以获得...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}_{\\geq 0} $ be the number of hamsters.  \nLet $ K \\in \\mathbb{Z}^+ $ be the number of box types.  \nLet $ A = (a_1, a_2, \\dots, a_K) $ be a sequence of positive i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments