USACO Training Section 3.2 Feed Ratios

 
英文原题  中文题译

大意：给出整数a[i][j]和b[i]，i,j=1,2,3，有X={x[i]|i=1,2,3,s.t 存在y,对j=1,2,3 x[1]*a[1][j]+ x[3]*a[2][j]+ x[3]*a[3][j]=y*b[j]}，找出X中使x[i]最小的和。举例说明，三组整数为(1:2:3),(3:7:1),( 2:1:2)，目标为(3:4:5)，则8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5)。没有比8+1+5更小的了。

数据限制条件：a[i][j],b[i],x[i]均为小于100的整数。

可能是搜索做习惯了，一看到就往搜索上想了，发现，若无小于100的限制条件，难点在于如何记录和判定状态，如何判定无法满足。想了很久没想到合适的办法。此题要求解，必须看英文原题，题译不准确。OK，加了小于100的限制，那么无法满足就是如果100以内都搞不定，就NONE。全部枚举，也就100^3，变得没任何难度了。

再仔细想想，这其实是个线性方程组，x*(1:2:3) + y*(3:7:1) + z*(2:1:2) -k*(3:4:5)=0，常数时间搞定。这么一想，之前100的限制条件其实是给我这种笨蛋留的后门，呵呵。

/*
ID: blackco3
TASK: ratios
LANG: C++
*/
#include <iostream>
using namespace std;

int main() {
	freopen("ratios.in", "r", stdin);
	freopen("ratios.out", "w", stdout);	
	int feeds[3][3], num[3];
	cin >> num[0] >> num[1] >> num[2] ;
	for( int i=0; i<3; i++)
		cin >> feeds[i][0] >> feeds[i][1] >> feeds[i][2] ;
	for( int total=1; total<=297; total++) {		
		for( int i=0; i<=total && i<100; i++) {
			register int n0=i ;			
			for( int j=0; j<=total-i && j<100 /*&& total-i-j<100*/ ; j++) {
				register int n1=j, n2=total-i-j ;
				if( n2>=100 )
					continue ;
				register int s0 = n0*feeds[0][0] + n1*feeds[1][0] + n2*feeds[2][0] ;
				if( s0%num[0] )
					continue ;
				register int d=s0/num[0] ;
				register int s1 = n0*feeds[0][1] + n1*feeds[1][1] + n2*feeds[2][1] ;
				if( s1!=num[1]*d )
					continue ;
				register int s2 = n0*feeds[0][2] + n1*feeds[1][2] + n2*feeds[2][2] ;
				if( s2!=num[2]*d )
					continue ;
				cout << n0 << " " << n1 << " " << n2 << " " << d << endl ;
				return 0 ;
			}
		}
	}
	cout << "NONE" << endl ;
	return 0;
}