Pembahasan Codeforces 304A

Pembahasan gw yang kedua. Kali ini mau ngebahas soal codeforces yang baru gw kerjain tadi. Berikut soalnya :

A. Pythagorean Theorem II

In mathematics, the Pythagorean theorem — is a relation in Euclidean geometry among the three sides of a right-angled triangle. In terms of areas, it states:

In any right-angled triangle, the area of the square whose side is the hypotenuse (the side opposite the right angle) is equal to the sum of the areas of the squares whose sides are the two legs (the two sides that meet at a right angle).

The theorem can be written as an equation relating the lengths of the sides a, b and c, often called the Pythagorean equation:

a2 + b2 = c2where c represents the length of the hypotenuse, and a and b represent the lengths of the other two sides.

Given n, your task is to count how many right-angled triangles with side-lengths a, b and c that satisfied an inequality 1 ≤ a ≤ b ≤ c ≤ n.

Input

The only line contains one integer n (1 ≤ n ≤ 104) as we mentioned above.

Output

Print a single integer — the answer to the problem.

Sample test(s)
Input
5
Output
1
Input
74
Output
35

Pembahasan

Satu hal yang gw pikirin, soal ini bisa diselesaikan dengan bruteforce dengan kompleksitas O(N^3). Maksudnya soal ini diselesaikan dengan perulangan sebanyak 3 kali untuk menghitung perbandingan a^2+b^2=c^2 selama n kali. Tapi ternyata solusi gw itu dapet TLE di test case 31.😦

Mulai kepikiran buat cari cara gimana biar bisa dapet O(N^2). Setelah didiskusiin di grup fb, dapet solusi sebagai berikut.

Lakukan perulangan sebanyak 2 kali. For pertama untuk menghitung perulangan dari a ke n-1. Lalu perulangan kedua dari b ke n*n. Setelah itu buat nilai c yang bernilai a*a+b*b, dan nilai temp yang bernilai akar dari c. Lalu dipakein if untuk membuat perbandingan antara temp*temp=c. Dapet deh O(N^2).

Kode :

#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
int count=0;
for (int a=1;a<n;a++) {
for (int b=a;a*a+b*b<=n*n;b++) {
int c=a*a+b*b;
int temp=(int)sqrt(c);
if (temp*temp==c) count++;
}
}
cout << count;
}

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s