fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std ;
  5.  
  6. int T,N,P,A[51],ans,AP[10][1001];
  7.  
  8. bool check(int x){
  9.  
  10. 	int total = 0;
  11. 	for(int i=1;i<=N;i++){
  12. 		total += (upper_bound(AP[A[i]]+1,AP[A[i]]+1+1000,x)-(AP[A[i]]+1));
  13. 	}
  14. 	return (total>=P) ;
  15. }
  16.  
  17. int main(){
  18. 	scanf("%d",&T) ;
  19. 	memset(AP,0,sizeof AP) ;
  20. 	for(int i=1;i<=8;i++){
  21. 		for(int j=1;j<=1000;j++){
  22. 			AP[i][j] = i*j ;
  23. 			AP[i][j] += AP[i][j-1] ;
  24. 		}
  25. 	}	
  26. 	while(T--){
  27. 		scanf("%d",&P) ;
  28. 		scanf("%d",&N) ;
  29. 		for(int i=1;i<=N;i++){
  30. 			scanf("%d",&A[i]) ;
  31. 		}
  32. 		if(P==0)
  33. 			ans = 0;
  34. 		else{	
  35. 			int low,high,mid ;
  36. 			low = 1;
  37. 			high = 100000000 ;
  38. 			while(low<=high){
  39.  
  40. 				mid = (low+high)/2 ;
  41. 				if(check(mid) && (mid == 1 || !check(mid-1)))
  42. 					break ;
  43. 				else if(check(mid))
  44. 					high = mid-1;
  45. 				else
  46. 					low = mid+1;
  47. 			}
  48. 			ans = mid ;
  49. 		}  
  50. 		printf("%d\n",ans) ;
  51. 	}
  52. 	return 0;
  53. }
Success #stdin #stdout 0s 3336KB
comments ()
stdin
copy 
3
10
4 1 2 3 4
8
1 1
8
8 1 1 1 1 1 1 1 1
stdout
copy 
12
36
1
https://ideone.com/rXQXxX
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!