37. UVa-11236 Grocery Store //complex multi loop searching

문제

<그림1: 문제 설명>

문제는 간단하다. Input은 따로 주어지지 않고, 0<a,b,c,d<=20인 네 실수에 대해(a,b,c,d는 소숫점 두자리까지만 가질 수 있다.)  a+b+c+d=a*b*c*d를 만족하는 모든 (a,b,c,d)쌍을 출력하는 것. (단 중복 쌍은 없어야한다.)

 

만약 그냥 가능한 a,b,c,d를 보려면 이는 (2000)⁴인데 말도 안되는 연산 수이다. 따라서 search space를 줄일 방법을 생각해봐야 한다. 우선, 실수 연산은 매우 느리므로 그냥 a,b,c,d를 0.01~20.00으로 두는 대신 1~2000으로 두면 다음과 같은 식을 생각해볼 수 있다.

<그림2: 문제에서 만족해야 하는 식>

 

또한, 중복제거를 위해 대칭성을 고려해야하므로 a<=b<=c<=d로 순서를 잡아보면, a는 제일 lower bound가 되므로 4*a<=2000이어야 한다. 따라서 a<=500

또한 a가 결정되었을 때 a+3b<=2000,... a와b가 결정되었을 때 a+b+2c<=2000인것도 차례대로 생각해볼 수 있다.

이렇게 a+b+c+d의 bound로 많은 search space를 자를 수 있지만, a*b*c*d의 upper bound로도 많은 search space를 줄여볼 수 있다.

위의 식에서 p₁p₂p₃p_{4/10⁸은 20이하여야 하므로 다음과 같이 bound를 고려한 loop를 최종적으로 완성할 수 있다.}

<그림3: 최종 loop>

루프를 세 개만 사용한 이유는 어차피 d는 abc로 결정되기 때문이다. <그림2>의 식을 바꿔서 p4에 대한 식으로 써보면 다음과 같다.

 

<그림4: p4(d)를 결정하는 식>

그러면 이제 이 p4에 대해 다음 사항을 모두 통과한 것을 a,b,c,d sequence로 출력하면 된다.

 

(1) 결정된 d가 c보다 크거나 같은가?

(2) p1p2p3-10^6은 0이 아닌가? (0이면 그림4에서 분모에 0이 생기게 됨)

(3) a+b+c+d가 2000이하인가?

(4) a*b*c*d가 2*10^9이하인가?

(5) <그림4>의 분자%분모==0인가? -->0이어야 소숫점 둘째자리까지만 사용해도 표현될 수 있는 수

이 코드를 써보면 다음과 같다. p1,p2,p3,p4와 a,b,c,d는 조금 혼용해서 설명했다.

 

 

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main() {
	int upperbound = 2 * pow(10, 9);
	int ten_six = 1000000;
	int sum;
	int product;
	int d;
	for (int a = 1; a <= 500; a++) {	
    if (a * a * a * a >upperbound) break;
		for (int b = a; a + 3 * b <= 2000; b++) {	
        if (a * b * b * b > upperbound) break;
			for (int c = b; a + b + 2 * c <= 2000; c++) {
			if (a * b * c * c > upperbound) break;
			
            sum = (ten_six * (a+b+c));
			product = a * b * c-ten_six;
			
            if (product == 0) continue;
			if (sum % product != 0) continue;
			d = sum / product;
			if (c > d) continue;
			if (a + b + c + d > 2000) continue;
			if (a * b * c * d > upperbound) continue;
			printf("%.2f %.2f %.2f %.2f\n",a/100.0,b/100.0,c/100.0,d/100.0);
			}
		}
	}
	return 0;
}