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:

...

ALGOPRO5 - Lucky number

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

• Problem:

Một số được cho là may mắn nếu nó chỉ gồm các chữ số 6 và 9.  
Cho số tự nhiên n ( 1 <= n <= 55), hãy tính xem có bao nhiêu số may mắn có tối đa n chữ số?

Input

Số n.

Output

Đáp án của bài toán.

Example:

Input

2

Output:

6

Input

1

Output:

2

• Solution:

Bài này thực chất là có bao nhiêu số có độ dài không quá n chỉ có 6 và 9 :D

• Code:

C:

https://ideone.com/VNOQQE

#include <stdio.h>

main () {
    int n;
    scanf ("%d",&n);
    long long ssmm, tsmm=0;
    for (int i=1; i<=n; i++) {
        ssmm=1;
        for (int j=1; j<=i; j++) {
            ssmm=ssmm*2;
        }
        tsmm=tsmm+ssmm;
    }
    printf ("%lld",tsmm);
}

C++:

...

JAVA:

...

Python:

...

P143PROJ - ROUND 3J - Quảng trường

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

• Problem:

Quảng trường nhà hát thủ đô của Berland hình chữ nhật có kích thước n × m (m2). Nhân ngày lễ kỉ niệm thành phố, người ta quyết định lát quảng trường bằng các phiến đá grannite. Mỗi phiến đá có kích thước a × a (m2). Các cạch của phiến đá được lát song song với cạnh của quảng trường.

Cần ít nhất bao nhiêu phiến đá để lát kín quảng trường? Phần đá lát có thể lớn hơn diện tích quảng trường nhưng quảng trường phải được bao phu hết, và không được phép cắt các phiến đá ra.

Input
Dòng đầu tiên chứa 3 số nguyên n,  m và a (1 ≤  n, m, a ≤ 109).

Output
In ra số lượng phiến đá cần dùng.

Example:

Input

6 6 4

Output:

4

• Solution:

- Bài này nếu lát vừa khít thì sẽ chia lấy số lượng đá lát thồi. 
- Nhưng nếu lát không vừa thì lấy phần nguyên và + 1 (Có nghĩa là lát tối đa số đá và lát thêm 1 hàng đá nữa cho vừa kín).

• Code:

C:

JAVA:

P144PROI - ROUND 4I - Đoạn thẳng lớn nhất

Link Sub: http://www.spoj.com/PTIT/problems/P144PROI/
Người Gửi: Loo?

• Problem:

Bạn được cho n đoạn thẳng trên tia Ox. Đoạn thứ i được bắt đầu từ điểm L[i] và kết thúc tại R[i]. Nhiệm vụ của bạn là tìm trong tập đoạn đã cho đoạn thẳng lớn nhất, bao trùm tất cả các tập đoạn còn lại.  
Hãy in ra chỉ số của đoạn thẳng đó, nếu không tồn tại thì in ra -1.
Đoạn [a,b] được gọi là bao trùm đoạn [c, d]  nếu a <= c <= d <= b.
Input
Dòng đầu tiên là số nguyên n(1 <= n <= 100).  
n dòng tiếp theo, mỗi dòng gồm 2 số nguyên L[i], R[i] (1<= L[i] <= R[i] <= 10^9) biểu diễn đoạn thứ i.  
Các đoạn được đánh số bắt đầu 1.

Output
In ra một số nguyên duy nhất là đáp án của bài toán. Input đảm bảo không có 2 đoạn thẳng nào trùng nhau.

Example:

Input

3
1 1
2 2
3 3

Output:

-1

Input

6
1 5
2 3
1 10
7 10
7 7
10 10

Output:

3

• Solution:

Bao trùm tất cả có nghĩa là: Có một cặp left - right sao cho: left là nhỏ nhất và right là lớn nhất. Vậy thì chỉ cần tìm left min và right max là được. VD1: 1 1 2 3 left min = 1, right max = 3. Có nghĩa là phải có đoạn [1, 3] mới có thể bao trùm được tất cả. Nhưng không! Trên dãy kia không có đoạn [1, 3] nên in ra -1; VD2: 2 3 1 9 left min = 1, right max = 9. Có nghĩa là phải có đoạn [1, 9] mới có thể bao trùm được tất cả. Vâng! Trên dãy kia có đoạn [1, 9] nên ta sẽ in ra vị trí của [1 9];

• Code:

C:

JAVA:

PTIT013A - Bài A - Số may mắn

Link Sub: http://www.spoj.com/PTIT/problems/PTIT013A/
Người Gửi: Hikaru

• Problem:

John rất thích con số 86 vì theo John đó là con số may mắn. Khi bắt gặp một số nguyên X John muốn kiểm tra xem trong dạng biểu diễn của nó kết thúc là số 86 hay không? Ví dụ số 111539786 kết thúc là  số 86, còn số 123456789 thì không. 
Nhiệm vụ của bạn là viết một chương trình đọc số nguyên X và kiểm tra xem trong dạng biểu diễn của nó kết thúc là số 86 hay không?

Input
Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một  số nguyên dương không lớn hơn 20 là số l ượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Output
Với mỗi bộ dữ liệu, ghi ra trên một dòng câu trả lời, ghi số 1 nếu trong dạng biểu diễn của nó kết thúc là số 86, ghi số 0 trong trường hợp ngược lại.

Example:

Input

3
111539786
123456789
8686

Output:

1
0
1

• Solution:

Bài này khá đơn giản khi các bạn chỉ cần lấy dư cho 100 và so sánh với 68.
Nếu không có thể nhập vào string và xử lí như trong code C++;

• Code:

C:

https://pastebin.com/LZEG9j2w

#include <stdio.h>
 
int main () {
    int t;
    scanf ("%d", &t);
    for (int i=1; i<=t; i++) {
        long long n;
        scanf ("%lld", &n);
        if (n%100==86) printf ("1\n");
        else printf ("0\n");
    }
    return 0;
}

C++:

https://pastebin.com/Gw2LUJPw

#include <iostream>
#include <string>
using namespace std;
 
int main () {
    string s;
   
    int t;
    cin>>t;
    for (int i=1; i<=t; i++) {
        cin>>s;
        int len = s.length();
        if (s[len-1]=='6' && s[len-2]=='8') {
            cout<<"1"<<endl;
        } else cout<<"0"<<endl;
    }
    return 0;
}

JAVA: