PTIT123F - Người cai ngục say rượu

Link Sub: http://www.spoj.com/PTIT/problems/PTIT123F/
Người Gửi: Dương Lee

• Problem:

Một nhà tù nào đó có n ô kế tiếp nhau. Mỗi ô có một tù nhân ở trong nó và đều được khóa lúc ban đầu.  
Một đêm, cai ngục buồn chán và quyết định chơi một trò chơi. Vòng thứ nhất của trò chơi, ông uống một chai whisky và chạy đi mở khóa cho tất cả các ô 1,2,3,..n . Vòng thứ 2, ông cũng uống 1 chai whisky và chạy đi khóa tất cả các ô chia hết mà chỉ số ô cho 2. Vòng thứ 3, ông cũng uống như vậy @@ và lại chạy đi thăm các ô có chỉ số chia hết cho 3. Nếu ô đang khóa, thì ông mở khóa, nếu ô đang mở thì ông sẽ khóa lại. Ông lặp lại trong n vòng, sau đó đi ra ngoài. Một số tù nhân thấy ô của họ đã được mở khóa và không có cai ngục, lập tức họ thoát ra ngoài.  
Cho số lượng các ô ban đầu, xác định có bao nhiêu tù nhân thoát ra ngoài.

Input

-         Dòng 1 chứa số bộ test T  
-         Sau đó là T bộ test, mỗi bộ test trên 1 dòng chứa một số n (5<=n<=100) là số ô của nhà tù.

Output

Với mỗi bộ test, in ra trên một dòng số tù nhân trốn thoát.

Example:

Input

2
5
100

Output:

2
10

• Solution:

Bài này đề có nghĩa là: Có ông say rượu chạy n lượt (i:1->n) mỗi lượt sẽ mở khóa (or đóng lại) cho các phòng giam có chỉ số là bội của i nếu nó đang khóa (or đang mở).
Và đếm số của mở.
Bài này chỉ cần áp dụng thuật Buffalo thôi :v (vì n nhỏ)
p/s: Thấy trên kienthuc24 có công thức -> "(lấy nguyên) sqrt(n)" @@ và hiện tại vẫn chưa thể lĩnh hội được (trình độ hơi có hạn ^^)

• Code:

C++:

https://ideone.com/DSe7DL

#include <iostream>
using namespace std;

int drunk(int n)
{
    int arr[102];
    for (int i=1; i<=n; i++)
    {
        if (i==1)
        {
            for (int j=1; j<=n; j++)
                arr[j] = 0;
        }
        else
        {
            for (int j=1; j<=n/i; j++)
            {
                if (arr[i*j]==0) arr[i*j] = 1;
                else arr[i*j] = 0;
            }
        }
    }
    int count = 0;
    for (int i=1; i<=n; i++)
        if (arr[i]==0) count++;
    return count;
}

int main ()
{
    int T;
    cin>>T;
    int n;
    for (int i=1; i<=T; i++)
    {
        cin>>n;
        cout<<drunk(n)<<endl;
    }
    return 0;
}

JAVA:

...

Python:

...

Author : DL

Share this

Related Posts