Đèn cầy

Xem PDF

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

Nến (còn gọi là đèn cầy) thường được thắp trong các buổi tiệc ngoài tời để tạo không khí huyền ảo, ấm cúng, lãng mạn. Hôm nay là sinh nhật Jasmine! Aladdin, Abu và thần đèn đã tổ chức một buổi tiệc thịnh soạn gồm cơ man nào là sơn hào hải vị. Trên bàn tiệc là một hàng \(N\) cây nến bằng đúng số tuổi của Jasmine. Điều đặc biệt là những cây nến này có phép (do của thần đèn).

  • Ban đầu \(N\) nến đều đang cháy.
  • Nếu thổi lần đầu thì cả \(N\) nến sẽ tắt.
  • Thổi lần hai thì các nến số chẵn cháy trở lại.
  • Thổi sang lần thứ \(3\) thì nến \(3, 6, 9, 12,…\). nếu đang cháy sẽ tắt, còn nếu đang tắt sẽ cháy.
  • Tương tự vậy với các lần \(4, 5, 6, …, N\).

Aladdin nhận thấy là sau khi thổi nến một số lần thì một số nến sẽ không bị tác động nữa, từ đó nghĩ ra một trò chơi. Aladdin đố Jasmine tìm ra cây nến còn sáng thứ \(K\) sau khi thổi hết cả \(N\) lần. Nếu Jasmine trả lời đúng sẽ nhận được một phần quà đặc biệt mà Aladdin bỏ ra cả mấy ngày để chuẩn bị :D.

Phải thối hết \(N\) lần thì mất công quá. Tuy nhiên Aladdin có một mẹo, không cần thổi mà cũng không cần biết có bao nhiêu nến tất cả vẫn tính được ngay số thứ tự của cây nến đang cháy thứ \(K\). Hãy giúp Jasmine giành được quà nào!

Yêu cầu:
Cho \(K\). Tìm số thứ tụ của cây nến đang cháy thứ \(K\) sau \(N\) lần thổi nến.

Input

  • Một số nguyên dương duy nhất \(K\) (\(K\) có giới hạn hơn \(10^{18}\)).

Output

  • Một số nguyên dương là số thứ tự của cây nến sáng thứ \(K\).

Example

Test 1

Input
1
Output
2

Test 2

Input
6
Output
8

Test 3

Input
21
Output
26

Nguồn: VNOI


Bình luận


  • 0
    PhamtUan123    9:10 a.m. 11 Tháng 7, 2022

    làm sao để ac đc test cuối v ạ?


    • 1
      xuanphuc165    8:56 p.m. 20 Tháng 3, 2022

      tăng thời gian cho scratch đi anh ơi, ko ac được bài nào


      • 1
        huyhau6a2    7:58 p.m. 21 Tháng 1, 2022 đã chỉnh sửa

        what time có 0,1 s sao tle rồi hmm(ac do số trời, tle cũng do số trời)


        • 2
          nguyenminhhai021009    7:53 p.m. 21 Tháng 1, 2022

          Ai mà ac bài này rồi thì qua bài xếp dãy bàn rồi thì qua làm bài xếp dãy bàn đi nó cũng tương tự như bài này thôi.

          1 phản hồi

          • 1
            huyhau6a2    5:06 p.m. 14 Tháng 1, 2022

            Bài này nên dùng chặt nhị phân tìm căn nha


            • 1
              tkluannguyendang    3:26 p.m. 14 Tháng 1, 2022

              Mình đã thêm test và rejudge lại bài của các bạn (credit: huyhau6a2)


              • 1
                minhtuanitk20    8:05 p.m. 11 Tháng 12, 2021

                test cuối chịu r

                1 phản hồi

                • 3
                  LeQuangMinh0903    8:23 a.m. 1 Tháng 12, 2021

                  Test cuối có vẻ khó AC !!


                  • 2
                    huyhau6a2    10:11 a.m. 30 Tháng 11, 2021 đã chỉnh sửa

                    Chắc test cuối 1000 chữ số quá, mãi không ac. Hoặc cớ khi if else tới hết quá!

                    1 phản hồi

                    • 3
                      stack_queue_4977    9:59 a.m. 30 Tháng 11, 2021

                      Đã update test và rejudge.

                      • 1 bình luận nữa