INFINITY-Editorial

editorial
, ,
1

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();
}
1 Like