101602024-03-28 19:50:39111Az óvodai lét elviselhetetlen könnyűsége #2cpp17Elfogadva 100/10048ms7576 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define MA (int)1e5

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int M,Q;
	cin>>M>>Q;
	vector<int>v(M);
	for(int i=0;i<M;i++){
		cin>>v[i];
	}
	sort(v.rbegin(),v.rend());
	int A=1e5;
	vector<int>dp(A);
	dp[0]=1;
	for(int i=1;i<A;i++){
		int h=0;
		for(int j=0;j<M&&v[j]>h;j++){
			h=max(h,dp[i-1]*(v[j]-1)%v[j]);
		}
		if(h==0||dp[i-1]>1e7){
			A=i;
		}
		dp[i]=dp[i-1]+h;
	}
	while(Q--){
		int N;
		cin>>N;
		int l=0,h=A;
		while(l<h){
			int m=(l+h)/2;
			if(dp[m]>N){
				h=m;
			}
			else{
				l=m+1;
			}
		}
		cout<<(h==A?0:h)<<'\n';
	}
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms3160 KiB
2Elfogadva25ms3508 KiB
subtask220/20
3Elfogadva4ms3728 KiB
4Elfogadva4ms3940 KiB
5Elfogadva4ms4140 KiB
6Elfogadva16ms4336 KiB
7Elfogadva9ms4568 KiB
8Elfogadva7ms4564 KiB
9Elfogadva8ms4764 KiB
10Elfogadva7ms4716 KiB
subtask310/10
11Elfogadva24ms4776 KiB
12Elfogadva24ms4788 KiB
13Elfogadva25ms4972 KiB
14Elfogadva24ms5184 KiB
15Elfogadva23ms5284 KiB
16Elfogadva25ms5472 KiB
17Elfogadva28ms7076 KiB
subtask415/15
18Elfogadva4ms5436 KiB
19Elfogadva3ms5428 KiB
20Elfogadva16ms7120 KiB
21Elfogadva4ms5640 KiB
22Elfogadva17ms7236 KiB
23Elfogadva3ms5904 KiB
24Elfogadva3ms5956 KiB
25Elfogadva3ms5864 KiB
26Elfogadva3ms5908 KiB
27Elfogadva13ms6876 KiB
subtask555/55
28Elfogadva37ms7440 KiB
29Elfogadva37ms7572 KiB
30Elfogadva27ms6064 KiB
31Elfogadva28ms6024 KiB
32Elfogadva27ms6340 KiB
33Elfogadva25ms6024 KiB
34Elfogadva32ms6124 KiB
35Elfogadva28ms6012 KiB
36Elfogadva32ms6348 KiB
37Elfogadva32ms6472 KiB
38Elfogadva41ms7104 KiB
39Elfogadva48ms7576 KiB