Đèn cầy

View as PDF

Submit solution

Points: 350 (partial)
Time limit: 0.1s
Memory limit: 128M
Input: stdin
Output: stdout

Author:
Problem types

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.

Dữ liệu vào:

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

Kết quả:

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

Example Input

1

Example Output

2

Example Input 2

6

Example Output 2

8

Example Input 3

21

Example Output 3

26

Nguồn: VNOI


View comments (22)

Comments


  • 0
    PhamtUan123  commented on 9:10 a.m. 11 jul, 2022

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


  • 1
    tk21phucnguyenxuan  commented on 8:56 p.m. 20 mar, 2022

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


  • 1
    huyhau6a2  commented on 7:58 p.m. 21 jan, 2022 edited

    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  commented on 7:53 p.m. 21 jan, 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
      huyhau6a2  commented on 7:55 p.m. 21 jan, 2022

      bật mí cho 1 điều test cuối hình như 1000 chữ số hay sao ấy hehehehe<cười khốn lạn>


      • 2
        nguyenminhhai021009  commented on 7:59 p.m. 21 jan, 2022

        khi tôi ac kiểu: ahaha <cười 1000 chữ số dễ ồm>


  • 1
    huyhau6a2  commented on 5:06 p.m. 14 jan, 2022

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


  • 1
    tkluannguyendang  commented on 3:26 p.m. 14 jan, 2022

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


  • 1
    minhtuanitk20  commented on 8:05 p.m. 11 dec, 2021

    test cuối chịu r


    • -3
      VoBaThongL921  commented on 8:14 p.m. 11 dec, 2021

      bạn có thể lên google và tìm hiểu về cấu trúc if-else trong c++ =))


      • 1
        nguyendanghau2006  commented on 8:15 p.m. 11 dec, 2021

        :)), chơi zậy hả


        • -2
          VoBaThongL921  commented on 8:15 p.m. 11 dec, 2021

          ơ tui biết gì đâu :)?


          • 3
            nguyendanghau2006  commented on 8:17 p.m. 11 dec, 2021

            ai lại chơi if test :((, chơi switch case đi :))


  • 3
    LeQuangMinh0903  commented on 8:23 a.m. 1 dec, 2021

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


  • 2
    huyhau6a2  commented on 10:11 a.m. 30 nov, 2021 edited

    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á!


    • 3
      stack_queue_4977  commented on 10:15 a.m. 30 nov, 2021

      test cuối chính xác là có 474 chữ số nhé.


      • -2
        huyhau6a2  commented on 10:17 a.m. 30 nov, 2021 edit 2
        • !!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        • Thảo nào dùng py dùng float ra inf
        • Thành ra phải if else
        • Cái này dùng c++ đúng là dùng bẫy tính nhanh thật

        • 2
          tkluannguyendang  commented on 10:23 a.m. 30 nov, 2021

          Hình như test cuối bạn if test đúng không vậy?


          • -4
            huyhau6a2  commented on 10:24 a.m. 30 nov, 2021 edit 2

            mình dùng py nên phải if test chứ không bị IR. Lát nữa mình thử c++ xem có ok không. Mình mong cái này dưới 300 chữ số thì dùng py được


      • 2
        tkluannguyendang  commented on 10:17 a.m. 30 nov, 2021

        :>


  • 3
    stack_queue_4977  commented on 9:59 a.m. 30 nov, 2021

    Đã update test và rejudge.


  • 4
    tkluannguyendang  commented on 9:43 p.m. 29 nov, 2021 edited

    P/s: Nếu ai muốn có ý kiến gì về bài tập này hãy nhắn vào trong phần "Báo cáo một vấn đề" giúp mình nhé. :>