Author: Yash Chaudhari
Tester: Ritik Mittal
Editorialist: Yash Chaudhari
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
None
PROBLEM:
Given an equilateral triangle of side length n, that forms a pattern as given in the following image, your task is to find the number of regular hexagons ( of any side length greater than 0 ) in the triangle, such that it has its side overlapping with any of line in the pattern.
EXPLANATION:
We can just count the centers of hexagons of all sides that can be formed. By observation we can see that there can be atmax floor(n / 3) types of hexagons. And the number of hexagons of ith type are f(n - 3 * i + 1), where f(x) = x * (x + 1) / 2. So, we can just loop through 1 to n / 3 and count the total number of hexagons.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define FOR(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define FORL(i, a, n) for (int(i) = (a); (i) <= (n); (i)++)
#define FORR(i, a, n) for (int(i) = (a); (i) >= (n); (i)--)
#define FORSQ(i, a, n) for (int(i) = (a); (i) * (i) <= (n); ++(i))
#define FOREACH(a, b) for (auto &(a) : (b))
#define all(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))
#define log(args...) \
{ \
string _s = #args; \
replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); \
istream_iterator<string> _it(_ss); \
err(_it, args); \
}
#define logcontainer(container) \
for (auto &(e) : (container)) \
cout << (e) << " "; \
cout << endl;
void err(istream_iterator<string> it)
{
}
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
cout << *it << " = " << a << endl;
err(++it, args...);
}
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vll;
typedef vector<bool> vb;
typedef priority_queue<ll> maxheap;
typedef priority_queue<ll, vl, greater<ll>> minheap;
typedef map<ll, ll> mapll;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll maxn = 1e6 + 5;
ll Mod(ll a, ll b)
{
return (b + a % b) % b;
}
ll f(ll n)
{
return n * (n + 1) / 2;
}
void yash56244()
{
ll n;
cin >> n;
ll ans = 0;
for (int i = 1; i <= n / 3; i++)
{
ans += f(n - 3 * i + 1);
}
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
cin >> t;
while (t--)
{
yash56244();
}
return 0;
}