Candy Tribulation

Problem: https://atcoder.jp/contests/abc432/tasks/abc432_c

C - Candy Tribulation

 

문제 요약

작은 사탕과, 큰 사탕 두 종류의 사탕이 있다.

작은 사탕의 한 개 무게는 X, 큰 사탕의 한 개 무게는 Y일 때,

N명에게 동일한 무게의 사탕을 분배하려고 한다.

 

N명이 받은 큰 사탕은 몇 개인가?

단, 각각 받을 수 있는 최대 사탕 갯수는 모두 다르다.

 

예시1)

입력	설명(의미)
3 6 8	3명, X = 6, Y = 8
11 10 13	각각 받을 수 있는 최대 사탕 개수

 

정답: 18

세 사람이 동일하게 받을 수 있는 최대 무게: 80

첫 번째 사람: 6 x 4 + 8 x 7 = 80

두 번째 사람: 6 x 0 + 8 x 10 = 80

세 번째 사람: 6 x 12 + 8 x 1 = 80

세 명이 받은 큰 사탕의 수: 7 + 10 + 1 = 18개

 

예시2)

입력	설명(의미)
2 3 4	2명, X = 3, Y = 4
3 5	각각 받을 수 있는 최대 사탕 개수

 

정답: -1

동일한 무게로 분배할 방법이 없음

 

예시2)

입력	설명(의미)
8 4 32	8명, X = 4, Y = 32
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

 

정답: 8000000000

정답이 32-bit integer를 초과할 수 있음

 

문제 풀이

수식으로 문제를 정리해보자.

--------------------------------------

L = 큰 사탕의 수

S = 작은 사탕의 수

T = 각 사람이 받을 수 있는 총 사탕의 수 \( (T = L + S) \)

X = 작은 사탕의 무게

Y = 큰 사탕의 무게

W = 각 사람이 가져가는 총 무게 (모두 동일)

--------------------------------------

 

① 사탕 개수 정리

\( T_{i}  = L_{i} + S_{i} \)

\( \therefore S_{i} = T_{i} - L_{i} \)

 

② 사탕 무게 정리

\( W_{i} = (L_{i} * Y) + (S_{i} * X) \)

\( W_{i} = (L_{i} * Y) + {(T_{i} - L_{i}) * X} \)

\( W_{i} = L_{i}Y + T_{i}X - L_{i}X \)

\( W_{i} = L_{i}(Y - X) + (T_{i}X) \)

모든 사람은 동일한 무게 W를 가져야 하므로, \( W_{i} = W \)

 

③ 큰 사탕 개수 정리

\( W = L_{i}(Y - X) + (T_{i}X) \)

\( W - (T_{i}X) = L_{i}(Y - X) \)

\( \frac{W - T_{i}X}{(Y - X)}  = L_{i} \)

\( L_{i} \)는 정수여야 하므로,  \( (W - T_{i}X) \text{ mod } (Y - X)  = 0 \)

\( L_{j} \)도 마찬가지다.  \( (W - T_{j}X) \text{ mod } (Y - X)  = 0 \)

(A) \( W - T_{i}X \equiv 0 \pmod {Y - X} \)

(B) \( W - T_{j}X \equiv 0 \pmod {Y - X} \)

두 식을 빼면, \( (W - T_{i}X) - (W - T_{j}X) = T_{j}X - T_{i}X = (T_{j} - T_{i})X \)

\( \therefore (T_{j} - T_{i})X \text{ mod } (Y - X) = 0 \) 를 만족하지 않으면, 사탕 분배는 불가능하다.

 

④ 각 사람이 가져가는 총 무게(W) 정리

\( \frac{W - T_{i}X}{(Y - X)}  = L_{i} \) 를 보면, \( L_{i} \) 는 W에 대해 증가하는 선형함수이다.

즉, W가 증가하면 모든 \( L_{i} \)는 증가한다.

따라서 문제에서 요구하는 "큰 사탕의 총 개수를 최대화" 하려면, 가능한 W 중 가장 큰 W를 선택해야 한다.

단, 이 W가 실제로 존재하려면 모든 사람이 동일한 W를 가져갈 수 있는 범위 안에 있어야 한다.

 

정리

1. \( (T_{j} - T_{i})X \)가 \( (Y - X) \)의 배수라면, 사탕 분배 가능하다.

    → 따라서 모든 \( T_{j} \)가 \( (T_{j} - T_{0})X \equiv 0 \pmod{Y - X} \)를 만족하지 않으면, -1

2. 만족한다면, W가 올바른 범위에 있는지 확인해야 한다.

    → \( \text{max}(T_{i}X) <= W <= \text{min}(T_{i}Y) \)

 

풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	long long n, x, y;
	cin >> n >> x >> y;

	vector<int> total_candies(n, 0);
	for (int i = 0; i < n; i++) cin >> total_candies[i];

	// 사탕 분배가 가능한지 확인
	// {(T[i] - T[0]) * x} 는 (y - x)의 배수이어야 한다.
	sort(total_candies.begin(), total_candies.end());
	for (int i = 1; i < total_candies.size(); i++)
	{
		long long impossible = (total_candies[i] - total_candies[0]) * x % (y - x);
		if (impossible != 0)
		{
			cout << -1;
			return 0;
		}
	}

	// 공통 무게(W) 범위 계산
	// T[i] * X <= W <= T[i] * Y
	long long min_weight = 0;
	long long max_weight = numeric_limits<long long>::max();
	for (int i = 0; i < total_candies.size(); i++)
	{
		min_weight = max(min_weight, total_candies[i] * x);
		max_weight = min(max_weight, total_candies[i] * y);
	}

	if (min_weight > max_weight)
	{
		cout << -1;
		return 0;
	}
 
	// 최대 W 구하기
	long long remainder = (max_weight - total_candies[0] * x) % (y - x);
	max_weight = max_weight - remainder;

	// large candy 개수 합 구하기
	long long answer = 0;
	for (int i = 0; i < n; i++)
	{
		answer += (max_weight - total_candies[i] * x) / (y - x);
	}

	cout << answer;
	return 0;
}