PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Mohammad Lutfar Rahman RIFAT
Tester: Satyam, Utkarsh Gupta
Editorialist: Devendra Singh
DIFFICULTY:
To be calculated
PREREQUISITES:
None
PROBLEM:
You are climbing an infinity staircase, which (as its name suggests) has an infinite number of stairs. You are currently standing at the $1$st stair, and you would like to reach the N-th stair. When standing at the i-th stair, you can make one of the following three moves:
- Move to stair {i+1}
- Move to stair {i+2}
- Move to stair {i+3}
However, you can’t make the same move twice in a row.
For example, suppose you reach the $7$th stair from the $4$th stair using the third move. Then, from the $7$th stair, you can move to either the $8$th or the $9$th stair (using the $1$st or $2$nd move) — but you can’t move to the $10$th stair (because you would use the third move twice in a row). Now suppose you choose the $1$st move and move to the $8$th stair. On your next move, you cannot move to the $9$th stair, but you can move to either the $10$th or the $11$th stair.
Under these conditions, find the minimum number of moves you need to reach the N-th stair.
EXPLANATION:
Total difference in stairs that needs to be covered is N-1. Given the type of moves and the constraint that you can’t make the same move twice in a row makes it impossible to climb more than 5 stairs in 2 consecutive steps (32323....). This means the answer is at least 2\cdot floor(\frac{(N-1)}{5}) in any case.
- If N-1 is a multiple of 5, the answer is exactly 2\cdot floor(\frac{(N-1)}{5}).
- If the remainder when N-1 is divided by 5 is 1,2 or 3, it can always be covered in 1 more move, the answer is 2\cdot floor((\frac{(N-1)}{5})+1.The answer cannot be less than this because maximum stairs that can be climbed in 2\cdot floor((\frac{(N-1)}{5}) moves, in this case ,is only N-1-(N-1)%5.
- If the remainder is 4, exactly two more moves (1 stair then 3 stairs) are needed to cover the remaining stairs, the answer is 2\cdot floor(\frac{(N-1)}{5})+2.The answer cannot be less than this because maximum stairs that can be climbed in 2\cdot floor((\frac{(N-1)}{5}) moves, in this case is only (N-1)-4 and in one more move you can only cover at most 3 stairs.
Therefore ,
ans = ((N-1) / 5) * 2
(N-1) %\:= 5
if (N-1) ans += (N-1) <= 3 ? 1 : 2
print(ans)
TIME COMPLEXITY:
O(1) or for each test case.
SOLUTION:
Setter's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--)
{
int n; cin >> n;
n--;
int ans = (n / 5) * 2;
n %= 5;
if (n) ans += n <= 3 ? 1 : 2;
cout << ans << '\n';
}
return 0;
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n;
cin >> n;
int ans = (2 * ((n - 1) / 5));
int rem = (n - 1) % 5;
if (rem == 4)
ans += 2;
if (rem >= 1 && rem <= 3)
ans++;
cout << ans << '\n';
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}