News Paper Puzzle

QUESTION

When things slow down in the kitchen, the Chef likes to do puzzles he finds in the newspaper until more orders arrive. Today, a new type of puzzle has been featured and the Chef needs help solving it.\n\nIn this puzzle, a series of groups of non-zero integers are given where each group has exactly three integers. Furthermore, for each positive integer k, the number of groups including k plus the number of groups including -k does not exceed 3. The goal is to assign, for each positive integer k, either the character ‘T’ or ‘F’ so that every group of three integers has\n\n at least one negative integer k such that |k| is assigned ‘F’, or\n at least one positive integer k such that k is assigned ‘T’\n\nFinally, you are guaranteed that the absolute values the three integers in any particular group are all distinct. Now, newspaper puzzles are only fun if they are solvable so you are guaranteed that there is a solution. Your task is to find such an assignment of ‘T’ or ‘F’ values to the positive integers meeting the above requirements.\n\nInput\n\nThe first line consists of a single integer denoting the number of test cases (at most 30). The first line for each test case consists of two integers C and V. Following this are C lines, one per group of integers in the puzzle. Each such line consisting of 3 non-zero integers between -V and V. Furthermore, the absolute values of these three integers are distinct.\n\nFinally, the input is such that for every integer k, the total number of groups containing either k or -k is at most 3.\n\nBounds: 1<=C<=1000 and 3<=V<=3000\n\nOutput\n\nThe output for each test case is a single line consisting of V characters ‘T’ or ‘F’. These characters should appear consecutively with no spaces between. The i’th such character is what positive integer i is assigned. This should be done so that each group of three integers has the property described above.\n\nIf an integer k between 1 and V does not have either k or -k appearing in a group of three integers then you should still assign it a character ‘T’ or ‘F’. Finally, if there are multiple solutions then any will do.

“TESTCASE_1”: “2\n3 3\n1 2 3\n1 -2 -3\n-1 2 -3\n2 7\n5 -2 1\n3 -1 2\n###—###SEPERATOR—###—\nFFT\nFFTTTTT”, “TESTCASE_2”: “3\n4 4 \n4 5 6\n1 -2 -3\n-1 2 -3\n2 7\n5 -2 1\n3 -1 2\n###—###SEPERATOR—###—\nTTFT\nT”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <stdio.h>
#include <string.h>
#define S(a) if(a)return
 
int w, q, a[1111][3], u[1111], b[3333], r[3333];
 
void A(int i)
{
int j, k, p, d;
if(i==-1)S(!!(q=1));
S(u[i]==w);
for(u[i]=w+!(j=-1); ++j<3; b[k]=p,r[k]=d)
	{
	p=b[k=abs(a[i][j])];
	b[k]=i;
	d=r[k];
	r[k]=a[i][j];
	A(p);
	S(q);
	}
}
 
main()
{
int fall, n, m, i, j;
for(scanf("%d",&fall); fall--; puts(""))
	{
	for(i=!!scanf("%d %d",&n,&m); i<=n; i++)
	for(j=0; j<3; scanf("%d",&a[i][j++]));
	for(memset(b,255,sizeof(b)),i=1; i<=n; q=(++w)*0,A(i++));
	for(i=1; i<=m; putchar((r[i++]<0)?'F':'T'));
	}
return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro