/
Update
2 min
补题 | ARC224D
题目 There are N cards, numbered 1 through N. Initially, nothing is written on any of the cards. You can write zero or more positive integers on each ca
题目#
There are cards, numbered through . Initially, nothing is written on any of the cards.
You can write zero or more positive integers on each card.
The cost of writing a positive integer once is equal to the number of digits in the decimal representation of .
Determine whether it is possible to satisfy the following condition. If it is possible, output the minimum total cost required; if it is not possible, output .
- For every pair of positive integers satisfying , there exists a card containing exactly one of and .
test cases are given; solve each of them.
做法#
将题目条件进行翻译,记记录了数字 的卡片编号集合为 ,要满足题意,即要求不存在 使得 ,即不存在两个相同的集合。对于大小为 的集合,显然有 种。
再看题目要求的条件,即最小化:
其中 , 是 十进制的位数。
贪心地把 较大的数分配给较小的权重即可。
代码#
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int T;
cin>>T;
while(T--){
int n,k;
cin>>n>>k;
ll cnt=1;
for(int i=1;i<=n&&cnt<k;i++){
cnt=min((ll)k,cnt*2);
}
if(cnt<k){
cout<<-1<<"\n";
continue;
}
vector<ll> digit(20);
for(ll l=1,len=1;l<=k;l*=10,len++){
ll r=min((ll)k,l*10-1);
digit[len]=r-l+1;
}
vector<ll> C(n+1);
C[0]=1;
for(int i=0;i<n;i++){
__int128 nxt=(__int128)C[i]*(n-i)/(i+1);
C[i+1]=min<__int128>(nxt,k);
}
ll ans=0;
int cur=8;
while(cur>=0&&digit[cur]==0) cur--;
for(int i=0;i<=n;i++){
ll rem=C[i];
while(rem>0&&cur>=1){
ll use=min(rem,digit[cur]);
ans+=i*cur*use;
rem-=use;
digit[cur]-=use;
if(digit[cur]==0) cur--;
}
}
cout<<ans<<endl;
}
return 0;
}cpp