INS14B - TRISQRS
After coming back from the ACM World Finals '13, Digo decided to celebrate his performance by watching a lot of action movies. Sitting in front of his laptop for days watching his favourite stars battle it out, Digo suddenly got inspired to join the CIA. Digo is a serious man, and vowed that he'd be inducted in the CIA force by the end of the year. And mind you, he takes his vows very seriously!
After sweating it out in the field for months, it's finally time for his interview. The interviewer believes that mental agility is as important as physical fitness and decides to test our hero with a mathematical puzzle.
The interviewer hands Digo a square of side N and asks him to partition the square into a number of right angled triangles, each having an equal integral area. Two sides of the triangle should be parallel to the two sides of the square. Being an ACM World Finalist, Digo solves the question in a split second. Impressed, the interviewer decided to test him with a harder question. He asks Digo to tell him the number of such partitions possible. All partitions having the same number of right triangles are considered the same.
First line will contain T, the number of test cases. Next T lines will contain a single integer each N, denoting the size of the square.
Output one line for each test case. Each line contains one integer which is the desired solution
Nice problem, read the description carefully - I've spent 1.5 hours figuring algorithms to compute sequences that, thankfully, this problem doesn't ask for.Last edit: 2019-03-17 05:45:06
This is an excellent question . Easy to code but a bit difficult to reach the solution by intuition.
/* Nitin Jaiman */:
Vamsi Krishna Avula:
@Rishav : Yes
is it possible one side is 0.5 and other side is 4. ??