#include #include #include #define MAX 51 //no need to sort //O(n) int main(){ int k,K; int s,t; int si,ti,i; int sum[MAX]; int maxValue,maxIndex; int isSuspect; FILE *in = fopen ("money.in", "r"); fscanf (in, "%d\n", &K); for (k = 1; k <= K; k ++){ memset(sum,0,sizeof(sum)); fscanf(in,"%d %d",&s,&t); for (i = 0; i < t; i++){ fscanf(in,"%d %d",&si,&ti); sum[si]+=ti;//index starts at 1 not 0 } maxValue=0; maxIndex=0; for (i = 1; i <= s; i++){ if(sum[i]>maxValue){ maxValue=sum[i]; maxIndex=i; } } //check if purchases add up to more than twice of any other person isSuspect=1; for (i = 1; ((i <= s)&&(isSuspect)); i++){ if((sum[maxIndex]<= 2*sum[i])&&(maxIndex!=i)){ isSuspect=0; } } printf ("Data Set %d:\n", k); if(isSuspect) printf ("%d\n", maxIndex); else printf ("No suspect.\n"); printf ("\n"); } fclose (in); return 0; }