Problem Description
Clarke is a patient with multiple personality disorder. One day, Clarke turned into a junior student and took a chemistry exam. But he did not get full score in this exam. He checked his test paper and found a naive mistake, he was wrong with a simple chemical equation balancer. He was unhappy and wanted to make a program to solve problems like this. This chemical equation balancer follow the rules: Two valences A combined by |A| elements and B combined by |B| elements. We get a new valence C by a combination reaction and the stoichiometric coefficient of C is 1. Please calculate the stoichiometric coefficient a of A and b of B that aA+bB=C, a,b∈N∗.
Input
The first line contains an integer T(1≤T≤10), the number of test cases. For each test case, the first line contains three integers A,B,C(1≤A,B,C≤26), denotes |A|,|B|,|C| respectively. Then A+B+C lines follow, each line looks like X c, denotes the number of element X of A,B,C respectively is c. (X is one of 26 capital letters, guarantee X of one valence only appear one time, 1≤c≤100)
Output
For each test case, if we can balance the equation, print a and b. If there are multiple answers, print the smallest one, a is smallest then b is smallest. Otherwise print NO.
Sample Input
2
2 3 5
A 2
B 2
C 3
D 3
E 3
A 4
B 4
C 9
D 9
E 9
2 2 2
A 4
B 4
A 3
B 3
A 9
B 9
2 3 5
A 2
B 2
C 3
D 3
E 3
A 4
B 4
C 9
D 9
E 9
2 2 2
A 4
B 4
A 3
B 3
A 9
B 9
Sample Output
2 3
NO
NO
Hint:
The first test case, $a=2, b=3$ can make equation right.
The second test case, no any answer.
Source
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<stdlib.h>
using namespace std;
#define ll long long
#define eps 1e-10
#define MOD 1000000007
#define N 1000000
#define inf 1e12
int a,b,c;
int mp[][];
int mpp[][];
int vis[];
int main()
{
int t;
scanf("%d",&t);
while(t--){
memset(mpp,,sizeof(mpp)); scanf("%d%d%d",&a,&b,&c);
char s[];
int cnt;
for(int i=;i<a;i++){
scanf("%s%d",s,&cnt);
int index = s[]-'A';
mpp[][index]+=cnt;
//printf("1---%d\n",mp[0][index]);
}
for(int i=a;i<a+b;i++){
scanf("%s%d",s,&cnt);
int index = s[]-'A';
mpp[][index]+=cnt;
//printf("2---%d\n",mp[1][index]);
}
for(int i=a+b;i<a+b+c;i++){
scanf("%s%d",s,&cnt);
int index = s[]-'A';
mpp[][index]+=cnt;
//printf("3---%d\n",mp[2][index]);
} int i,j;
int flag=;
for(i=;i<=;i++){
for(j=;j<=;j++){
for(int k=;k<;k++){
mp[][k]=mpp[][k];
mp[][k]=mpp[][k];
mp[][k]=mpp[][k];
}
memset(vis,,sizeof(vis));
for(int k=;k<;k++){
mp[][k]*=i;
mp[][k]*=j;
}
int w=;
for(int k=;k<;k++){
if(mp[][k]){
if(mp[][k]+mp[][k] == mp[][k]){
vis[k]=;
}else{
w=;
break;
}
}
} if(w==){
for(int k=;k<;k++){
if(vis[k]== && (mp[][k] || mp[][k] || mp[][k])){
w=;
break;
}
}
}
if(w==){
flag=;
break;
}
}
if(flag==) break;
}
if(flag==){
printf("%d %d\n",i,j);
}else{
printf("NO\n");
}
}
return ;
} //A 6 2 12
//B 6 3 18
//C 12 5 60