Editorial for Odds and Ends


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Editorialist: PHPeasant

The intended solution is a constant time method to find the appropriate element in the sequence. This is based on finding which 'half' of the sequence you are inspecting and then generating the final element. Another point to remember is that the input can exceed the range of 32-bit integers.

A verbose example solution in C++14 is given below

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    unsigned long long k,n;
    cin >> n >> k;

    if(n==1){
        cout << 1;
    } else if(n%2==1){
        if(k == n/2+1){
            cout << n;
        }
        else if(k <= n/2){
            cout << 2*k;
        } else if(k > n/2+1){
            k-=(n/2+1);
            cout << n - (2*k);
        }
    } else {
        if(k==n){
            cout << 1;
        } else if(k <= n/2){
            cout << 2*k;
        } else{
            k-=n/2;
            cout << n-(2*k)+1;
        }
    }
}

Comments

There are no comments at the moment.