ALGOPRO8 - Đếm giày

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

• Problem:

Một ngày Gấu muốn đếm lại xem hiện tại mình đang có bao nhiêu đôi giày. Sau khi kiểm tra, Gấu có n chiếc giày màu đỏ và m chiếc giày màu xanh.  
Hiện tại Gấu đang theo mốt là mỗi ngày, gấu đeo một chiếc giày màu đỏ sang bên chân trái, chân phải thì đeo chiếc giày màu xanh. Gấu ngại giặt giày nên sau mỗi ngày, Gấu không đeo lại giày mà hôm đó đã dùng. Các bạn giúp Gấu xem là Gấu theo mốt này được bao nhiêu lâu. Sau đó, khi không thực hiện mốt này được nữa thì Gấu sẽ đeo 2 đôi giày cùng màu thì Gấu sẽ có giày đeo được bao nhiêu ngày tiếp theo.

Input

Một dòng duy nhất chứa 2 số nguyên n, m (1 <= n, m <= 100) là số lượng giày màu đỏ và số lượng giày màu xanh.

Output

Gồm 2 số nguyên lần lượt là số ngày Gấu đi mỗi bên một màu và số ngày tiếp theo Gấu đi 2 bên màu giống nhau.

Example:

Input

3 1

Output:

1 1

Input

2 3

Output:

2 0

Input

7 3

Output:

3 2

• Solution:

Bài này chắc không có gì khó khăn.
- Số đôi đi cọc cạch = min(n, m)
- Số đôi đi đi là một đôi = (max(n, m) - min(n, m))/2

• Code:

C++:

https://ideone.com/c3z6Be

#include <iostream>
using namespace std;

int main()
{
    int n, m;
    cin>>n>>m;
    int model = min(n, m);
    cout<<model<<" "<<(max(n, m) - model)/2;
    return 0;
}

JAVA:

...

Python:

...

ALGOPRO7 - Số bé thứ k

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

• Problem:

Cho một dãy số nguyên. Bạn hãy tìm số có giá trị thứ k sau khi đã sắp xếp dãy tăng dần.

Input

Dòng đàu chứa 2 số n và k là số phần tử và vị trí cần tìm ( 1 <= n <= 10^5, 0 <= k < n).  Dòng sau chứa n số nguyên là các phần tử của dãy số.

Output

In ra duy nhất 1 số là đáp án của bài toán.

Example:

Input

5 3
5 3 4 8 6

Output:

6

• Solution:

Chỉ cần dùng sort trong thư viện là ok rồi :v
*Lưu ý: k bắt tính từ 0.

• Code:

C++:

https://ideone.com/XO6Yw0

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int arr[100005];
    int n, k;
    cin>>n>>k;
    for (int i=0; i<n; i++)
    {
        cin>>arr[i];
    }
    
    sort(arr, arr+n);
    
    cout<<arr[k];
    
    return 0;
}

JAVA:

...

Python:

...

P163SUMH - ROUND 3H - Xúc xắc

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

• Problem:

Tí và Tèo đang chơi xúc xắc, mỗi người chọn ra một con số từ 1 đến 6 và sẽ tung xúc xắc để xem giá trị của con xúc xắc gần với con số của người nào hơn. Giá trị x gọi là gấn số a hơn số b nếu |x – a| < |x – b|  
Giờ đây bạn biết 2 con số mà Tí và Tèo đã chọn, hãy tính xem có bao nhiêu giá trị của xúc xắc mà gần số của Tí hơn, bao nhiêu giá trị mà khoảng cách tới 2 con số đã chọn như nhau và bao nhiêu giá trị mà nó gần với số của Tèo hơn và in ra kết quả lần lượt theo thứ tự như trên.

Input

Một dòng duy nhất gồm 2 số nguyên a, b (1 <= a, b <= 6)

Output

Kết quả bài toán.

Example:

Input

2 5

Output:

3 0 3

• Solution:

Bài này chỉ việc đếm thôi, chạy hết tất cả các trường hợp có thể có của xúc xắc (1->6) và đếm những trường hợp nào gần a hơn, trường hợp nào gần b hơn và bằng nhau.

• Code:

C:

https://ideone.com/I2191f

#include <stdio.h>
#include <math.h>

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    int ganA=0, ganB=0, bang=0;
    for (int i=1; i<=6; i++)
    {
        if (abs(a-i)<abs(b-i)) ganA++;
        else if (abs(a-i)>abs(b-i)) ganB++;
        else bang++;
    }
    printf("%d %d %d", ganA, bang, ganB);
    return 0;
}

C++:

...

JAVA:

...

Python:

...

P151SUMB - ROUND 1B - Đong gạo

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

• Problem:

Tuyenlv7 bị mẹ giao cho nhiệm vụ đó là đong gạo để mang lên nhà trọ. Anh được mẹ đưa cho 2 loại bịch, là loại 5 kg và 3 kg. Tuyenlv7 sẽ phải đong đủ số gạo mà mẹ cho vào 2 loại bịch trên.  
Ví dụ mẹ cho 18 kg thì Tuyenlv7 có thể đong bằng 3 bịch 5kg + 1 bịch 3kg hoặc 6 bịch 3 kg.  
Hãy giúp anh ấy đong với số lượng bịch ít nhất có thể, nếu không thể đong được, in ra -1.

Input

Dòng duy nhất chứ số N là số gạo mẹ Tuyenlv7 cho ( 0 < N < 5000).

Output

In ra đáp án của bài toán.

Example:

Input

18

Output:

4

• Solution:

Vì các bao chứa gạo đều là số nguyên tố, vậy nên với m(kg) gạo nếu chia được ta luôn có:
m = i*3 + j*5
->CT1: j = (m-i*3)/5 (hoặc CT2: i = (m-j*5)/3) (trong đó i là số bao 3kg, j là số bao 5 kg)
Với công thức trên ta chỉ cần for() với từng trường hợp của  i (hoặc j) và xét thêm điều kiện j nguyên (hoặc i nguyên) đối với CT1 (hoặc CT2) là đã xét được đầy đủ các trường hợp có thể chia ra các Bao
Việc còn lại là chỉ cần xác định trường hợp nào là ít bao nhất bằng phép tính: số bao gạo = i+j

• Code:

C:

https://ideone.com/Cpxb9T

#include <stdio.h>

int main()
{
    int N;
    scanf("%d", &N);
    
    int minB = 5000;
    for (int i=0; i<=(N/3); i++)
    {
        int kg = i*3;
        int kgRe = N - (kg);
        if (kgRe%5==0)
        {
            int B = i+kgRe/5;
            if (B<minB)
            {
                minB = B;
            }
        }
    }
    if (minB==5000)
        printf("-1");
    else
        printf("%d", minB);
    return 0;
}

C++:

...

JAVA:

...

Python:

...

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:

...

P146PROC - ROUND 6C - Bút màu

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

• Problem:

Tí nhờ mẹ đi mua bút màu để chuẩn bị cho giờ vẽ tranh trên lớp. Tí dặn mẹ mua 4 bút màu khác nhau, nhưng mẹ Tí lại quên mất, chỉ nhớ là mua 4 cái bút màu cho Tí.  
Về đến nhà, Tí bắt đền mẹ vì đã không mua đủ 4 màu cho Tí. Tí đòi mẹ ra hiệu sách mua thêm, để có đủ 4 màu vẽ cho ngày mai.  
Các bạn hãy tính xem mẹ Tí cần mua thêm ít nhất bao nhiêu chiếc bút màu?

Input

Một dòng duy nhất gồm 4 số nguyên s1, s2, s3, s4 (1<= s1, s2, s3, s4 <= 10^9) thể hiện màu của 4 chiếc bút mà mẹ vừa mới mua cho Tí.

Output

In ra số lượng bút màu ít nhất cần mua thêm cho Tí.

Example:

Input

1 7 3 3

Output:

1

Input

7 7 7 7

Output:

3

• Solution:

Bài này thực chất là bạn đếm số các số khác nhau và kết quả = 4-số đó.

• Code:

C:

https://ideone.com/FkgO2U

#include <stdio.h>

int main ()
{
    int n = 0;
    int arr[5];
    int tmp;
    for (int i=1; i<=4; i++)
    {
        scanf("%d", &tmp);
        int kt = 0;
        for (int i=1; i<=n; i++)
        {
            if (tmp==arr[i])
            {
                kt = 1;
                break;
            }
        }
        if (kt==0)
        {
            n++;
            arr[n]=tmp;
        }
    }
    printf ("%d", 4-n);
    return 0;
}

C++:

...

JAVA:

...

Python:

...

P166SUMI - ROUND 6I - Rick Flag

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

• Problem:

Trong hành trình giải cứu Amanda Waller, Slipknot đã bỏ trốn và ngay lập tức hắn bị Rick Flag tiêu diệt bằng cách bấm nút kích hoạt bom ở ngay trên tay. Sau một thời gian chiến đấu, Rick Flag không biết màn hình kích hoạt bom của mình còn hoạt động đúng không. Các bạn hãy kiểm tra giúp Rick Flag nhé.  
Biết rằng, màn hình kích hoạt bom của Rick Flag có n nút đại diện cho n người, mỗi nút gồm 2 trạng thái 0 là đã ấn nút cho nổ bom, 1 là chưa ấn nút. Nếu màn hình còn hoạt động tốt thì trong n nút sẽ chỉ có duy nhất một nút ở trạng thái 0.

Input

Dòng đầu tiên là số nguyên n (2 <= n <= 1000)  
Dòng tiếp chứa n số nguyên, mỗi số nguyên có giá trị 0 hoặc 1.

Output

In ra “YES” nếu màn hình còn hoạt động đúng và “NO” trong trường hợp còn lại.

Example:

Input

3
1 0 1

Output:

YES

• Solution:

Bài này khá là giản đơn thôi. Bạn chỉ việc đếm số lượng số 0, nếu số lượng số 0 bằng 1 thì là YES, không thì sẽ là NO.

• Code:

C++:

https://ideone.com/bEBHJ5

#include <iostream>
using namespace std;

int main ()
{
    int n;
    cin>>n;
    int dem_0 = 0;
    int dem_1 = 0;
    int tmp;
    for (int i=1; i<=n; i++)
    {
        cin>>tmp;
        if (tmp==0)
            dem_0++;
        else
            dem_1++;
    }
    if (dem_0==1)
        cout<<"YES";
    else
        cout<<"NO";
    return 0;
}

JAVA:

...

Python:

...

BCTOHOP - Sinh tổ hợp (Cơ bản)

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

• Problem:

Một tổ hợp chập k của n là một tập con k phần tử của tập n phần tử.

Chẳng hạn tập {1, 2, 3, 4} có các tổ hợp chập 2 là:

{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}

Vì trong tập hợp các phần thử không phân biệt thứ tự nên tập {1, 2} cũng là tập {2, 1}, do đó ta coi chúng chỉ là một tổ hợp.

Bạn hãy sinh hết tổ hợp chập của n phần tử, n phần tử gồm các số nguyên từ 1 đến n.

Các tập con in ra theo thứ tự từ điển. Ví dụ: {1, 2, 3, 4} < {1, 3, 2 4}.

Input
Một dòng duy nhất gồm 2 số nguyên n, k (1 <= k <= n <= 10)

Output
Mỗi một tổ hợp chập k in ra trên một dòng.

Example:

Input

4 2

Output:

1 2
1 3
1 4
2 3
2 4
3 4

• Solution:

Code C: Sinh hoán vị thông thường; 
- Khởi tạo cấu hình ban đầu: 1 2 3 ... k; 
- Tìm vị trí mà tại đó phần tử [i] chưa đạt cấu hình cuối (!=n-k+i). Nếu không tìm thấy thì đã đạt cấu hình cuối (stop). 
- Tăng [i]++; và các phần tử sau nó [i+1]= [i]+1, [i+2]=[i]+2, ...

• Code:

C:

C++:

JAVA:

BCQUEUE - Cấu trúc dữ liệu hàng đợi (queue) (Cơ bản)

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

• Problem:

Ban đầu cho một queue rỗng. Bạn cần thực hiện các truy vấn sau:

1. Trả về kích thước của queue
2. Kiểm tra xem queue có rỗng không, nếu có in ra “YES”, nếu không in ra “NO”.
3. Cho một số nguyên và đẩy số nguyên này vào cuối queue.
4. Loại bỏ phần tử ở đầu queue nếu queue không rỗng, nếu rỗng không cần thực hiện.
5. Trả về phần tử ở đầu queue, nếu queue rỗng in ra -1.
6. Trả về phần tử ở cuối queue, nếu queue rỗng in ra -1.

Input
Dòng đầu tiên chứa số nguyên n - lượng truy vấn (1 <= n <= 1000)  
N dòng tiếp theo, mỗi dòng sẽ ghi loại truy vấn như trên, với truy vấn loại 3 sẽ có thêm một số nguyên, không quá 10^6.

Output
In ra kết quả của các truy vấn.

Example:

Input

14
3 1
3 2
3 3
5
6
4
4
4
4
4
3 5
3 6
5
1

Output:

1
3
5
2

• Solution:

Đây là bài cấu trúc dữ liệu cơ bản. 
Sơ lược qua: 
- Một queue gổm mảng giá trị, front (phần tử đầu tiên) và back (phần tử cuối cùng). 
- Hoạt động theo cơ chế FIFO: Vào trước tiên ra đầu tiên

• Code:

C:

C++:

JAVA:

BCGCD - Ước chung lớn nhất, bội chung nhỏ nhất (Cơ bản)

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

• Problem:

Tìm UCLN và BCNN của 2 số.

Input
Gồm nhiều test, mỗi test trên 1 dòng chứa 2 số nguyên dương không quá 2^31  
Bộ test kết thúc bởi dòng chứa 2 số 0.

Output
Mỗi test xuất ra trên 1 dòng chứa 2 số cách nhau bởi dấu cách lần lượt là UCLN và BCNN.

Example:

Input

2 4
6 9
0 0

Output:

2 4
3 18

• Solution:

UCLN: Áp dụng phép chia lấy dư trong giải thuật Euclid. 
BCNN: Áp dụng công thức UCLN(a,b) = (a*b)/(BCNN(a,b)) trong giải thuật Euclid.

• Code:

C:

C++:

JAVA: