Bịt mắt bắt dê

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Hôm nay trong giờ ra chơi sau khi học 3 tiết cấu trúc dữ liệu và giải thuật căng thẳng. Toto rủ các bạn chơi trò chơi bịt mắt bắt dê các bạn đều hào hứng tham gia nhưng không ai chịu bịt mắt trước. Toto mới học về cấu trúc danh sách liên kết vòng và bài toán của Josephus, thế là Toto đề nghị các bạn xếp vào thành vòng tròn bắt đầu từ Toto và đếm từ 1 lần lượt đến người thứ 5 thì được ra khỏi vòng tròn, người sau đó lại được bắt đầu đếm từ 1 và loại người thứ 5 ra khỏi vòng tròn. Cứ như vậy ai còn lại cuối cùng sẽ phải vào bịt mắt lần đầu tiên.

Bịt mắt bắt dê

Bài toán đặt ra là có n người được đánh số từ 1 đến n và bắt đầu từ người số 1 cứ đếm đến người thứ k thì loại ra khỏi vòng tròn và lại bắt đầu chơi tiếp từ người thứ k+1 được đếm từ 1 cứ tiếp tục như vậy vì đứng thành vòng tròn nên lần lượt sẽ loại hết chỉ còn người cuối cùng. Hãy cho biết chỉ số của người cuối cùng là bao nhiêu?

Input

Dòng đầu có hai số nguyên dương n và k \(1<k<n<=1000\)

Output

Một số nguyên dương duy nhất là chỉ số của người cuối cùng

Ví dụ 1:

Input

13 3

Output

13

Giải thích : lần lượt các số sau bị loại 3, 6, 9, 12, 2, 7, 11, 4, 10, 5, 1, 8

Ví dụ 2:

Input

13 4

Output

5

Giải thích : lần lượt các số sau bị loại 4, 8, 12, 3, 9, 1, 7, 2, 11, 10, 13, 6

Ví dụ 3:

Input

200 10

Output

163
tichpx

Comments


  • 4
    TrinhThanhNam_CNTT1_K62  commented on Nov. 14, 2022, 11:43 a.m.

    Khó hiểu +1 :]] (1 sol mình nghĩ ra sau khi nghiên cứu Josephus problem)

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

int w(int a, int b)
{
    if (a == 0) return 0;
    else return (w(a - 1, b) + b) % a;
}

int main()
{
    int n, k;
    cin >> n >> k;

    cout << w(n, k) + 1;
}

  • 1
    TranVanLong_DTVT2_K62  commented on Oct. 14, 2022, 9:30 a.m. ← edited 
    using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    queue<int> Q;
    for(int i=1;i<=n;i++) Q.push(i);
    while(Q.size()>1)
    {
        for(int i=1;i<=k;i++) {Q.push(Q.front());Q.pop();}
        Q.pop();
    }
    cout<<Q.front();
}