Concept behind this?

Being a nonconformist, Volodya is displeased with the current state of things, particularly with the order of natural numbers (natural number is positive integer number). He is determined to rearrange them. But there are too many natural numbers, so Volodya decided to start with the first n. He writes down the following sequence of numbers: firstly all odd integers from 1 to n (in ascending order), then all even integers from 1 to n (also in ascending order). Help our hero to find out which number will stand at the position number k.

Input
The only line of input contains integers n and k (1 ≤ k ≤ n ≤ 1012).

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output
Print the number that will stand at the position number k after Volodya's manipulations.

Examples
input
10 3
output
5
input
7 7
output
6
Note
In the first sample Volodya's sequence will look like this: {1, 3, 5, 7, 9, 2, 4, 6, 8, 10}. The third place in the sequence is therefore occupied by the number 5.


And here is the optimal code for the solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>

#define fl(n) for(int i = 0; i < n; i++)


#define ll long long
#define nl endl
#define init -9999
#define INF 1e9
#define u unsigned


using namespace std;

int main()
{

    long long n, k;
    cin >> n >> k;
    if (k <= (n + 1) / 2)
    {
        cout << k * 2 - 1 << endl;
    }
    else
    {
        cout << (k - (n + 1) / 2) * 2 << endl;
    }

    return 0;
}


But I honestly don't know why were these equations used, I mean.. I traced them I get the values they output are correct but Idk the CONCEPT behind the equations...
Last edited on
In the sequence, odd numbers precede the even numbers; there are n numbers in total.

If n is odd, there are EXACTLY (n+1)/2 odd numbers, irrespective of division or integer division.
If n is even, there are EXACTLY n/2 odd numbers, but (n+1)/2 will give the same answer if done by integer division.

So, regardless of whether n is even or odd,
X = (n+1)/2 (with integer division)
will given the number of odd numbers which precede the even ones.

Then, if k is less than or equal to X you require the kth odd number, which is 2k-1.
Otherwise you want the (k-X)th even number, which is (k-X)*2.

Here's some shorter code.
1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
int main()
{
   int k, n;
   cout << "Input n k: ";   cin >> n >> k;
   int odds = ( n + 1 ) / 2;
   cout << ( k <= odds ? 2 * k - 1 : 2 * ( k - odds ) );
}
Last edited on
Topic archived. No new replies allowed.