P145PROC - ROUND 5C - Modulo

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

• Problem:

Cho 2 số nguyên A và B, A modulo B là phần dư của A khi chia cho B. Ví dụ, 7, 14, 27 và 38 lần lượt là 1, 2 , 0 và 2 theo modulo 3.  
Cho trước một dãy số có 10 phần tử. Bạn hãy viết chương trình tính số lượng số giá trị khác nhau trong dãy sau khi lấy modulo 42.

Input

Gồm 10 số nguyên không âm <= 1000.

Output

Ghi ra một số nguyên duy nhất là số lượng giá trị có trong dãy số sau khi lấy MOD 42.

Example:

Input

1
2
3
4
5
6
7
8
9
10

Output:

10

Input

42
84
252
420
840
126
42
84
420
126

Output:

1

Input

39
40
41
42
43
44
82
83
84
85

Output:

6

• Solution:

Cách đơn giản nhất để làm bài này đó là sử dụng mảng đánh dấu.
Nhận thấy rằng khi chia lấy dư cho 42 các giá trị chỉ nhận nguyên ở trong đoạn [0, 41]. Vậy nên ta tạo mảng dd[42]={0} (có ít nhất 42 phần tử đều bằng 0), mỗi lần tính toán ta đánh dấu dd[A%42]=1. Sau đó ta chỉ việc đếm xem trong mảng dd [0, 41] có bao nhiêu số đã được đánh dấu.
VD đối với 5 số:
1
1
3
3
42
-> dd[0]=1, dd[1]=1, dd[2]=0, dd[3]=1, dd[4]=0, dd[5] =0,...

• Code:

C:

https://ideone.com/LUbcJe

#include <stdio.h>

int main ()
{
    int dd[43]={0};
    int A;
    for (int i=1; i<=10; i++)
    {
        scanf("%d", &A);
        dd[A%42]=1;
    }
    int dem = 0;
    for (int i=0; i<42; i++)
    {
        if (dd[i]==1)
            dem++;
    }
    printf ("%d", dem);
    return 0;
}

C++:

...

JAVA:

...

Python:

...

Author : DL

Share this

Related Posts