Editorials of PERHILL-UVCE NCode October-2103

general
, ,
1

PROBLEM LINK:

Practice

Contest

Author: Bharathkumar Hegde

Tester: Amogh Aithal

Editorialist: Bharathkumar Hegde

DIFFICULTY:

Simple

PREREQUISITES:

Elementary School Maths.

PROBLEM:

Given the slant height of the hill, which is in the form of isosceles triangle. find out whether the height of the hill can be integer and base width can be even integer or not.

QUICK EXPLANATION:

Generate all the possible numbers, which can be hypotenuse of a right triangle, whose all sides are integers. and check whether the given number is one among them or not.

EXPLANATION:

Perfect Hill

The problem can reduced to find out whether the given number can be hypotenuse of the any right angled triangle, whose all sides can be integers or not. Simplest way to solve the problem is to pre-calculate all possible values of hypotenuse so that the right triangle formed by it can have integral sides.

You can refer to Pythagorean triple

for beautiful explanation on generating pythagorian triplets.

the following algorithm would generate all possible hypotenuse of integral triangle, and solve the problem in given time

initialize hypotenuse[1000001] to 0's

triplet_gen():
	for (1 to 1001):
		for (i+1 to 1001):
			hypotenuse[i*i+j*j]=1;			
for each input :
	start:
	accept input
	for ( 2 to sqrt(input) ):
		if ( input%i == 0 and ( hypotenuse[i] or hypotenuse[n/i])):
			print "PERFECT"
			goto start
	print "IMPERFECT"

The problem can be solved faster. All numbers can be expressed as multiples of prime numbers. and a Pythagorean Prime is a number which is in the form of 4n+1 and it is a sum of squares of two integers. Now check all prime factors of input, if any prime factor of input is a Pythagorean Prime, then input forms a PERFECT hill else answer is IMPERFECT.

2 Likes