[UVa-10090] Marbles (jewel box)

Problem

I have some (say, n) marbles (small glass balls) and I am going to buy some boxes to store them. The boxes are of two types: T ype 1: each box costs c1 Taka and can hold exactly n1 marbles T ype 2: each box costs c2 Taka and can hold exactly n2 marbles I want each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them. Since I find it difficult for me to figure out how to distribute my marbles among the boxes, I seek your help. I want your program to be efficient also.

 

Input

The input file may contain multiple test cases. Each test case begins with a line containing the integer n (1 ≤ n ≤ 2, 000, 000, 000). The second line contains c1 and n1, and the third line contains c2 and n2. Here, c1, c2, n1 and n2 are all positive integers having values smaller than 2,000,000,000. A test case containing a zero for n in the first line terminates the input.

 

Output

For each test case in the input print a line containing the minimum cost solution (two nonnegative integers m1 and m2, where mi = number of T ypei boxes required) if one exists, print ‘failed’ otherwise. If a solution exists, you may assume that it is unique.

 

//Input_1.txt
43
1 3
2 4
40
5 9
5 12
0

//Output.txt
13 1
failed

 

//Input_2.txt
27
2 4
3 2
40
3 13
4 7
71
5 11
3 6
0

//Output_2.txt
failed
2 2
1 10

//Input_3.txt
36
5 2
3 4
400
3 12
2 6
0

//Output_3.txt
0 9
failed

 

//Input_4.txt
374
5 11
2 4
60
2 4
4 8
0

//Output_4.txt
34 0
1 7

 

//Input_5.txt
731
0 11
20 17
88
4 6
3 14
50
3 3
3 4
0

//Output_5.txt
51 10
3 5
2 11

Solution

확장된 유클리드 알고리즘 디오판토스 방정식 사용

#define _CRT_SECURE_NO_WARNINGS
#define NUMBER_OF_FILES 10
#include <stdio.h>
#include <stdlib.h>

int q_arr[10], x_arr[10], y_arr[10], res_arr[10];
int num, count = 0;

int Gcd(int a, int b) {
	int r = a % b;
	int q = a / b;
	res_arr[num] = a;
	q_arr[num] = q;
	num++;
	if (r != 0) {
		count++;
		b > r ? Gcd(b, r) : Gcd(r, b);
	}
	else {
		res_arr[num] = b;
		q_arr[num] = b;
		num = 0;
		return b;
	}
}

void Eea(int n1, int n2, int* u, int* v, int gcd_result) {
	if (n1 > n2) {
		x_arr[0] = 1;
		y_arr[0] = 0;
		x_arr[1] = 0;
		y_arr[1] = 1;
	}
	else {
		x_arr[0] = 0;
		y_arr[0] = 1;
		x_arr[1] = 1;
		y_arr[1] = 0;
	}
	if (count == 0) {
		*u = x_arr[1];
		*v = y_arr[1];
	}
	else {
		int i = 2;
		while (1) {
			x_arr[i] = x_arr[i - 1] * (-1) * q_arr[i - 2] + x_arr[i - 2];
			y_arr[i] = y_arr[i - 1] * (-1) * q_arr[i - 2] + y_arr[i - 2];
			//printf("No. %d : %d %d %d \n", i, x_arr[i], y_arr[i], q_arr[i]);
			if (res_arr[i] == gcd_result) {
				*u = x_arr[i];
				*v = y_arr[i];
				break;
			}
			i++;
		}
	}
}

int Algorithm(int set_num, int file_num, int c, int c1, int c2, int n1, int n2) {
	char Output[NUMBER_OF_FILES][15] = {
		"Output_1.txt", "Output_2.txt", "Output_3.txt", "Output_4.txt", "Output_5.txt", "Output_6.txt", "Output_7.txt", "Output_8.txt", "Output_9.txt", "Output_10.txt"
	};
	FILE* output;
	output = fopen(Output[file_num], "a");

	int gcd_result, eea_result, x1_result = 0, y1_result = 0;
	int u, v, x0, x1, y0, y1, k, cost;
	int min = 10000;

	if (output != NULL) {
		num = 0;
		if (n1 == 0 && n2 == 0) {
			printf("failed\n\n");
			fprintf(output, "failed\n");
			return 0;
		}
		else if (n1 == 0) {
			if (c % n2 != 0) {
				printf("failed\n\n");
				fprintf(output, "failed\n");
				return 0;
			}
			else
				y1_result = c / n2;
		}
		else if (n2 == 0) {
			if (c % n1 != 0) {
				printf("failed\n\n");
				fprintf(output, "failed\n");
				return 0;
			}
			else
				y1_result = c / n1;
		}

		if (n1 > n2)
			gcd_result = Gcd(n1, n2);
		else
			gcd_result = Gcd(n2, n1);
		if (c % gcd_result != 0) {
			printf("failed\n\n");
			fprintf(output, "failed\n");
			return 0;
		}
		Eea(n1, n2, &u, &v, gcd_result);
		x0 = c * u / gcd_result;
		y0 = c * v / gcd_result;
		k = -500;
		while (1) {
			x1 = x0 + n2 * k / gcd_result;
			y1 = y0 - n1 * k / gcd_result;
			if (k == 500)
				break;
			if (x1 < 0 || y1 < 0) {
				k++;
				continue;
			}
			else {
				cost = c1 * x1 + c2 * y1;
				if (cost < min) {
					x1_result = x1;
					y1_result = y1;
					min = cost;
				}
				k++;
			}
		}
		count = 0;
		printf("\n\nresult : %d %d\n\n", x1_result, y1_result);
		fprintf(output, "%d %d\n", x1_result, y1_result);
		return 0;
	}
	else {
		printf("Error.");
		exit(1);
	}
	fclose(output);
}

void File_input(int i) {
	char Input[NUMBER_OF_FILES][15] = {
		"Input_1.txt", "Input_2.txt", "Input_3.txt", "Input_4.txt", "Input_5.txt", "Input_6.txt", "Input_7.txt", "Input_8.txt", "Input_9.txt", "Input_10.txt"
	};
	FILE* input;
	input = fopen(Input[i], "r");

	printf("\nInput_%d.txt\n\n", i + 1);

	int p, c1, c2, n1, n2;
	int set_num = 0;

	if (input != NULL) {
		while (1) {
			int a = fscanf(input, "%d", &p);
			if (p == 0) break;
			a = fscanf(input, "%d %d ", &c1, &n1);
			a = fscanf(input, "%d %d", &c2, &n2);
			Algorithm(set_num, i, p, c1, c2, n1, n2);
			set_num++;
		}
	}
	else {
		printf("Error.");
		exit(1);
	}
	
	fclose(input);
}

int main(void) {
	for (int i = 0; i < NUMBER_OF_FILES; i++) {
		File_input(i);
	}
}