codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

939B.md (1758B)


      1 Source: https://codeforces.com/problemset/problem/939/B
      2 
      3 B. Hamster Farm
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Dima has a hamsters farm. Soon *N* hamsters will grow up on it and Dima will sell them in a city nearby.
     22 
     23 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.
     24 
     25 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.
     26 
     27 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.
     28 
     29 Find out how many boxes and of which type should Dima buy to transport maximum number of hamsters.
     30 
     31 Input
     32 
     33 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.
     34 
     35 The second line contains *K* integers *a*1, *a*2, ..., *a**K* (1 ≤ *a**i* ≤ 1018 for all *i*) — the capacities of boxes.
     36 
     37 Output
     38 
     39 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.
     40 
     41 If there are many correct answers, output any of them.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 19 3  
     49 5 4 10
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 2 4
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 28 3  
     62 5 6 30
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 1 5
     69 ```