ABC057

[ABC057C] Digits in Multiplication

题面翻译

对于两个正整数A和B，将F ( A，B )定义为以下两者中较大的一个: max（A的位数，B的位数）例如，F ( 3，11 ) = 2，因为3有一位，11有两位。

给你一个整数n 求F ( A，B )的最小值为使得 N = A×B

输入 n

输出 min f(a,b)

感谢@chengni 提供的翻译

题目描述

整数 $ N $ が与えられます。
ここで、$ 2 $ つの正の整数 $ A,B $ に対して、$ F(A,B) $ を「$ 10 $ 進表記における、$ A $ の桁数と $ B $ の桁数のうち大きい方」と定義します。
例えば、$ F(3,11) $ の値は、$ 3 $ は $ 1 $ 桁、$ 11 $ は $ 2 $ 桁であるため、$ F(3,11)=2 $ となります。
$ 2 $ つの正の整数の組 $ (A,B) $ が $ N=A×B $ を満たすように動くとき、$ F(A,B) $ の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $

输出格式

$ 2 $ つの正の整数の組 $ (A,B) $ が $ N=A×B $ を満たすように動くときの $ F(A,B) $ の最小値を出力せよ。

样例 #1

样例输入 #1
10000
样例输出 #1
3
样例 #2

样例输入 #2
1000003
样例输出 #2
7
样例 #3

样例输入 #3
9876543210
样例输出 #3
6
提示

制約

$ 1≦N≦10^{10} $

$ N $ は整数である。

Sample Explanation 1

$ (A,B)=(100,100) $ のときに $ F(A,B) $ は最小値をとるため、$ F(100,100)=3 $ を出力します。

Sample Explanation 2

条件を満たす $ (A,B) $ の組は $ (1,1000003) $ と $ (1000003,1) $ の $ 2 $ 通りで、$ F(1,1000003)=F(1000003,1)=7 $ です。

思路

不难想到，最小值与平方根有关，所以我们可以求出平方根，然后选出较大的数。分解位数并统计即可

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
const int mod=1e9+7;
const int INF=1e9;
int main(){
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    ll d=(ll)sqrt(n)+1;
    ll num=0;
    //选出较大的数
    for(int i=1;i<=d;i++){
        if(n%i==0){
            num=n/i;
        }
    }
    ll cnt=0;
    //分解数位并统计
    while(num){
        num/=10;
        cnt++;
    }
    cout<<cnt;
    return 0;
}

[ABC057D] Maximum Average Sets

题面翻译

有n个数，可以选取最少A个最多B个，使得所选的数的平均值最大。求可能的最大平均值和在平均值最大的情况下的方案数

题目描述

$ N $ 個の品物が与えられます。
$ i $ 番目の品物の価値は $ v_i (1≦i≦N) $ です。
これらの品物から、$ A $ 個以上、$ B $ 個以下を選ばなければなりません。
この制約下において、選んだ品物の価値の平均の最大値を求めてください。
また、選んだ品物の平均が最大となるような品物の選び方が何通りあるかを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ A $ $ B $ $ v_1 $ $ v_2 $ $ ... $ $ v_N $

输出格式

解答を $ 2 $ 行に出力せよ。
$ 1 $ 行目には、選んだ品物の価値の平均の最大値を出力せよ。絶対誤差または相対誤差が $ 10^{−6} $ 以下ならば正解となる。
$ 2 $ 行目には、選んだ品物の平均が最大となるような品物の選び方の数を出力せよ。

样例 #1

样例输入 #1
5 2 2
1 2 3 4 5
样例输出 #1
4.500000
1
样例 #2

样例输入 #2
4 2 3
10 20 10 10
样例输出 #2
15.000000
3
样例 #3

样例输入 #3
5 1 5
1000000000000000 999999999999999 999999999999998 999999999999997 999999999999996
样例输出 #3
1000000000000000.000000
1
样例 #4

样例输入 #4
50 1 50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
样例输出 #4
1.000000
1125899906842623
提示

制約

$ 1≦N≦50 $

$ 1≦A≦B≦N $

$ 1≦v_i≦10^{15} $

$ v_i $ は全て整数である。

Sample Explanation 1

$ 4 $ 番目の品物と $ 5 $ 番目の品物を選ぶと価値の平均が最大となるため、出力の $ 1 $ 行目は $ 4.5 $ です。また、それ以外の品物の選び方で価値の平均が $ 4.5 $ になるものはないため、出力の $ 2 $ 行目は $ 1 $ です。

Sample Explanation 2

価値の平均が最大となる品物の選び方は複数存在することがあります。

思路

显然，选取最大的A个数，再往下选均值只会越来越小。

方案数只与临界值有关，其他更大的肯定被选了。

注意考虑临界情况，可能在最大的A个数后面还存在若干个数与临界值相等，所以利用排列组合计算方案。

但是还有一种特殊情况，就是最大值与临界值相等，所以不一定只选A个，还可能选A+1、A+2个等等。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+10;
const ll mod=998244353;
const ll INF=1e11;
ll n,a,b,num;
ll v[MAXN];
ll C[55][55];
bool cmp(ll a,ll b){
    return a>b;
}
ll ans;
//组合数预处理
void init(){
    C[0][0]=1;
    for(int i=1;i<=50;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++){
            C[i][j]=C[i-1][j-1]+C[i-1][j];
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    init();
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    
    //选出最大的A个数
    sort(v+1,v+1+n,cmp);
    for(int i=1;i<=a;i++){
        ans+=v[i];
    }
    cout<<fixed<<setprecision(6)<<(double)ans/a<<"\n";
    
    
    ll cnt1=0,cnt2=0;
    
    //统计n个数中有多少个临界值
    for(int i=1;i<=n;i++){
        if(v[i]==v[a])cnt1++;
    }
    
    //统计a个数中有多少个临界值
    for(int i=1;i<=a;i++){
        if(v[i]==v[a])cnt2++;
    }
    
    //如果最大值与临界值相等，那么最多可以选择b个
    if(v[1]==v[a]){
        for(ll i=a;i<=b;i++){
            num+=C[cnt1][i];
        }
    }
    
    //一般情况
    else{
        num=C[cnt1][cnt2];
    }
    cout<<num;
    return 0;
}