Số thứ k

Dạng bài

Điểm: 10 (p) Thời gian: 1.0s Bộ nhớ: 128M Input: bàn phím Output: màn hình

Cô giáo có \(n\) số nguyên từ \(1\) tới \(n\). Cô sắp xếp dãy số này lại theo một cách khá đặc biệt. Cô xếp tất cả các số lẻ theo thứ tự từ bé đến lớn trước, hết các số lẻ thì cô mới xếp đến các số chẵn, cũng theo thứ tự từ bé đến lớn. Bé Bi thấy dãy số này và tự hỏi số thứ \(k\) của dãy sẽ là số nào. Hãy giúp bé nhé!

Input

\(2\) số nguyên dương \(n, k\) (\(k \le n \le 10^{12}\)).

Output

Hãy in ra số thứ \(k\) trong dãy.

Example

Test 1

Input

5 2

Output

Bình luận

em troll thôi :)) biết cách tính r
ở đây chúng ta không nên dùng mảng vì khá là tốn thời gian và ram

vậy chúng ta cần lập ra một cách khác, ở đây em nghĩ ra được cách khá ngắn nhưng em thấy cũng khá hay, các anh chị có thể tham khảo nha

C++

/*
Giải nghĩa:

- Biến:
+ odds: tính xem có bao nhiêu số lẻ từ 1 đến n
+ evenK: (nên đọc trình bày ở dưới trước khi đọc cái này)
  + ở đây even nghĩa là số chẵn
  ta thấy trong mảng (ở dưới), số chẵn được viết sau mà theo công thức cấp số cộng, ta cần tính số thứ tự để tìm được số ta cần tìm,
  nhưng nếu để nguyên cái số thứ tự như vậy thì số thứ tự của số lẻ sẽ cộng với lại số thứ tự của số chẵn (ở đây em cũng không biết giải thích như nào, cho mn cái phép tính này ai hiểu được thì hiểu: k = odds + evens; evens = k - odds)
  => ta cần phải trừ đi số thứ tự của số lẻ để ra số thứ tự của số chẵn


- Code:
giả sử ta có một mảng: [1, 3, 5, 2, 4] (n = 5)
ta thấy số lẻ và số chẵn là dãy số tăng theo cấp số cộng
vậy ta có thể áp dụng công thức ở dưới

phần tính bằng công thức chia làm 2 phần:

- nếu k bé hơn hoặc bằng odds *mà số lẻ là số được viết trước*:
  => k thuộc số lẻ => số thứ k là số lẻ
  vậy ta có thể tính theo công thức
- nếu k lớn hơn odds:
  => k thuộc số chẵn => số thứ k là số chẵn
  mà ở đây số chẵn được viết sau => ta cần tính evenK
  sau đó tính theo công thức
*/

#include <iostream>
#include <iomanip>

using namespace std;

int main() {
    long long n, k;

    cin >> n >> k;

    /*
    công thức tính số số hạng:

    - số số hạng = (b - a) / d + 1

    ở đây ta muốn tính có bao nhiêu số lẻ trong dãy số từ 1 đến n
    */
    long long odds = (n - 1) / 2 + 1;

    /*
    Công thức cấp số cộng: An = A + (n - 1) * d
    Với: 

    - An = số hạng thứ n
    - A = số đầu
    - d = khoảng cách
    - n = số thứ tự
    */
    if(k <= odds) {
        cout << 1 + (k - 1) * 2;
    } else {
        long long evenK = k - odds;
        cout << fixed << setprecison(0) << (1 + (evenK - 1) * 2) + 1;
    }

    return 0;
}

1 bình luận nữa