PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: archit
Editorialist: raysh07
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You are given N sticks of lengths 1, 2, …, N. Find the maximum perimeter of a non-degenerate triangle constructed using these or -1 if not possible.
EXPLANATION:
Since we want to maximize perimeter, it makes sense to consider using the largest sticks.
Let’s try to use the sticks N, N - 1 and N - 2. This is possible only if 2 \cdot N < 3 \cdot N - 3 i.e. 3 < N. So for N \ge 4, we can obtain the maximum perimeter of 3 \cdot N - 3 by using the 3 largest sticks.
For N = 3, there are no triangles possible, hence the answer is -1.
Simply check if N \ge 4 or not, and print 3 \cdot N - 3 or -1 accordingly.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's Code (C++)
#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while (t--){
int n; cin >> n;
if (n >= 4) cout << (3 * n - 3) << "\n";
else cout << -1 << "\n";
}
}