[Codeforces Round #835 (Div. 4)] F. Quests

 

 

---

https://codeforces.com/blog/entry/109348

Codeforces Round #835 (Div. 4) Editorial - Codeforces

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n, d;
	long long c;
	cin >> n >> c >> d;
	long long a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n, greater<long long>());
	int l = 0, r = d + 2;
	while (l < r) {
		int m = l + (r - l + 1) / 2;
		long long tot = 0;
		int curr = 0;
		for (int i = 0; i < d; i++) {
			if (i % m < n) {tot += a[i % m];}
		}
		if (tot >= c) {
			l = m;
		}
		else {
			r = m - 1;
		}
	}
	if (l == d + 2) {cout << "Infinity\n"; return;}
	if (l == 0) {cout << "Impossible\n"; return;}
	cout << l - 1 << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

 

※. d를 넘어가지 않으면서 c이상의 코인을 얻을 수 있는가

 

※. k는 i퀘스트를 했을 때 k일 이후에 i퀘스트를 다시할 수 있다.

(퀘스트 배열을 내림차순한 다음 가장 큰 보상을 주는 퀘스트를 할 수 있을 때 마다 한다,)

([10,9,8,7] -> k = 2 -> (1d 10퀘스트) -> (2d 9퀘스트) -> (3d 8퀘스트) -> (4d 10퀘스트) = i % (k+1) )

 

※. k가 d를 넘어간다면 하루만에 퀘스트를 클리어 "Infinity"

※. k가 0이라면 d를 다 써도 퀘스트 클리어 불가능 "Impossible"

 

※. k를 이분탐색으로 구한다.

(k를 정했을 때 d일 까지의 보상합 (tot)를 구하고 tot >= c 라면 k를 증가시킨다 -> l = k+1)

(tot < c 라면 k를 감소시킨다 ->r = k)

(이분탐색이 끝날 때 k의 값은 l - 1 이다.)

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			long c = Long.parseLong(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			Long[] a = new Long[n];
			st = new StringTokenizer(br.readLine(), " ");
			for(int i = 0; i < n; i++) {
				a[i] = Long.parseLong(st.nextToken());
			}
			Arrays.sort(a,Collections.reverseOrder());
			int l = 0, r = d+2;
			while(l < r) {
				int m = l + (r - l + 1) / 2;
				long tot = 0;
				int curr = 0;
				for(int i = 0; i < d; i++) {
					if(i % m < n) {tot += a[i % m];} //day % k < n
				}
				if(tot >= c) { //sum >= coin k+
					l = m;
				}
				else { //sum < coin k-
					r = m-1;
				}
			}
			if(l == d + 2) sb.append("Infinity").append('\n');
			else if(l == 0) sb.append("Impossible").append('\n');
			else sb.append(l-1).append('\n');
		}
		System.out.println(sb);
	}
}

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			long c = Long.parseLong(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			Integer[] arr = new Integer[n];
			st = new StringTokenizer(br.readLine(), " ");
			for(int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			Arrays.sort(arr, Collections.reverseOrder());
			int l = 0;
			int r = d+1;
			while(l < r) {
				int k = (l + r) / 2;
				long tot = 0;
				int m = k+1;
				for(int i = 0; i < d; i++) {
					if(i % m < n) {
						tot += arr[i % m];
					}
				}
				if(tot >= c) {
					l = k+1;
				}
				else {
					r = k;
				}
			}
			if(l == d+1) sb.append("Infinity").append('\n');
			else if(l == 0) sb.append("Impossible").append('\n');
			else sb.append(l-1).append('\n');
		}
		System.out.println(sb);
	}
}