Codeforces Round #464 (Div. 2) B. Hamster Farm

62 阅读 0 评论 41 点赞

我是靠谱客的博主俊逸鸭子，最近开发中收集的这篇文章主要介绍Codeforces Round #464 (Div. 2) B. Hamster Farm，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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 ai 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 a1, a2, ..., aK (1 ≤ ai ≤ 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.

   Examples 
 
     input 
    
      Copy 
    
19 3
5 4 10

     output 
   
2 4

     input 
    
      Copy 
    
28 3
5 6 30

     output 
   
1 5

题意：有n只仓鼠，k种箱子，只能买一种，可以任意多，每个箱子必须装满仓鼠，否则不能运输。问你买哪一种箱子可以带走最多的仓鼠，同时输出需要的箱子个数。

思路：三种情况：箱子容量小于n，此时取余比较即可。箱子容量等于n，此时是最优解。箱子容量大于n，此时可以买任何一个编号的箱子，只不过买的个数是0。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100010],n,k,p,ans,pend;
int main()
{
    while(~scanf("%lld%lld",&n,&k))
    {
        for(ll i=1;i<=k;i++)scanf("%lld",&a[i]);
        pend=1e18;
        p=1;ans=0;
        for(ll i=1;i<=k;i++)
        {
            if(a[i]<n)
            {
                if(n%a[i]<pend)
                {
                    ans=n/a[i];
                    pend=n%a[i];
                    p=i;
                }
            }
            else if(a[i]==n)
            {
                ans=1;
                pend=0;
                p=i;
            }
        }
        printf("%lld %lldn",p,ans);
    }
    return 0;
}