P177PROA - ROUND 7A - Một cái đinh rỉ !

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

• Problem:

Lúa rất thích Lều, nhưng Lều không muốn xao nhãng việc học. Biết Lúa rất dốt toán, nhất là hình học nên Lều ra cho Lúa một bài toán và nếu Lúa không giải được thì sẽ cho Lúa một cơ hội.  
Lều cho Lúa một hình tròn có bán kính r, tâm của nó được đặt ở tọa độ x0, y0, và một chiếc đinh rỉ. 
Và yêu cầu phải đưa tâm hình tròn đến tọa độ x1,y1.  Biết rằng : Lúa chỉ được di chuyển hình tròn bằng cách cắm chiếc đinh vào mép của hình tròn và xoay hình tròn, và Lúa phải thực hiện với số lần cắm đinh ít nhất.  
Đương nhiên làm sai là chuyện đơn giản, “nhưng hôm nay là cá tháng Tư nên chắc Lều đang nói ngược thôi -_- “ . Hãy giúp Lúa giải bài toán này nhé.

Input

Một dòng duy nhất 5 số nguyên r,x0,y0,x1,y1. (1 ≤ r ≤ 105,  - 105 ≤ x, y, x', y' ≤ 105)

Output

In ra một số nguyên là số lần cắm đinh ít nhất để hoàn thành yêu cầu

Example:

Input

2 0 0 4 0

Output:

1

Input

4 1 2 1 2

Output:

0

Giải thích : Test 2 0 0 4 0
Như hình dưới : sẽ chỉ cần một lần cắm đinh và xoay.

Output:

• Solution:

Hix, cứ trâu thui bạn :(

• Code:

https://ideone.com/n7gR4i

C++:

#include <iostream>
#include <math.h>
using namespace std;
 
int main ()
{
    long long r, x0, y0, x1, y1;
    cin>>r>>x0>>y0>>x1>>y1;
    long long d = (x1-x0)*(x1-x0) + (y1-y0)*(y1-y0);
    double k=sqrt(d);
 
    if (x1==x0 && y1==y0)
    {
        cout<<"0";
    }
    else
    {
        if ((k/2)<=r)
            cout<<"1";
        else
        {
            long long dem=0;
            do
            {
                k=k-(double)(r*2);
                dem++;
           }
            while (k/2>r);    		
            
            cout<<dem+1;	
    	}	
    }
    return 0;
}

JAVA:

...

Python:

...

P164PROG - ROUND 4G - Kim tự tháp

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

• Problem:

LB có n khối hộp lập phương và anh ta quyết định xếp nó thành hình kim tự tháp. Kim tự tháp tầng trên cùng có 1 khối, tầng thứ 2 có 1 + 2 = 3 khối, tầng thứ 3 có 1 + 2 + 3 = 6 khối, cứ như vậy cho các đỉnh ở dưới. LB muốn xác định với n khối hộp, chiều cao tối đa của kim tự tháp là bao nhiêu?

Input

Một dòng chứa số n ( 1 <= n <= 10^4).

Output

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

Example:

Input

1

Output:

1

Input

25

Output:

4

• Solution:

Bài này while cộng dồn cho đến khi đủ là ok ^^

• Code:

C++:

https://ideone.com/ZkdEQx

#include <iostream>
using namespace std;
 
int main ()
{
    int n;
    cin>>n;
    int s=0;
    int t=0;
    int bs=0;
    while (s<n)
    {
        t++;
        bs=bs+t;
        s=s+bs;
    }
    if (s==n)
        cout<<t;
    else if (s>n)
        cout<<(t-1);
        
    return 0;
}

JAVA:

...

Python:

...

P176PROG - ROUND 6G - Số phần tử khác nhau

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

• Problem:

Cho 4 số tự nhiên n, x, y, z (y < z).
Dãy số a được tạo ra như sau:
a[1] = x % z;
for (int i = 2; i <= n; i++)
    a[i] = (a[i – 1] + y) % z;
Hãy đếm số phần tử khác nhau của dãy số a.

Input

gồm 1 dòng chứa 4 số tự nhiên n, x, y, z (1 <= x, y, z <= 109; 1 <= n <= 108).

Output

1 số tự nhiên duy nhất là số phần tử khác nhau của dãy số a

Example:

Input

5 1 3 5

Output:

5

• Solution:

Hack :v

• Code:

C++:

https://ideone.com/461bZq

#include <iostream>
using namespace std;
 
int main ()
{
    long long n, x, y, z;
    cin>>n>>x>>y>>z;
    
    long long tg=z;
    while(y!=z)
    {
        if(y>z)
            y=y-z;
        else
            z=z-y;
    }
    
    if (tg/y<n) cout<<(tg/y);
    else cout<<n;
    return 0;
}

JAVA:

...

Python:

...

P152PROA - ROUND 2A - Nguyên tố cùng nhau

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

• Problem:

Juggernaut được cô giáo Disruptor dạy toán, cô giáo định nghĩa một hàm f(x) như sau:  
Với  t là số lượng các số tự nhiên k (1 <= k <= x) thỏa mãn nguyên tố cùng nhau với x, nếu t là nguyên tố thì f(x) = 1, ngược lại f(x) = 0.  
Disruptor cho Juggernaut một số nguyên dương x, yêu cầu anh cho biết giá trị của hàm f(x), nếu trả lời sai thì Jug sẽ bị  cô trả về nhà, Jug không muốn về nhà, các bạn hãy giúp Jug giải bài toán này.

Input

Dòng đầu tiên chứa số bộ test T (T <= 10).  
Mỗi test gồm một dòng chứa số x (1 <= x <= 10^5).

Output

In ra kết quả mỗi test trên một dòng là giá trị của hàm f(x).

Example:

Input

2
2
3

Output:

0
1

• Solution:

- Không biết có cách làm toán cao cấp gì không nhưng mình làm theo đề bài với độ phức tạp O(NlogN) vẫn ok.
- Tìm số nguyên tố cùng nhau (là hai số có ước chung lớn nhất = 1) bằng phương pháp Euclid.
- Sau khi đếm số nguyên tố cùng nhau rồi thì ta tiến hành kiểm tra số nguyên tố và đưa ra kết quả f(x).

• Code:

C++:

https://ideone.com/n70HhO

#include <iostream>
#include <math.h>
using namespace std;

int ucln(int a, int b)
{
    while (b!=0)
    {
        int x = a%b;
        a = b;
        b = x;
    }
    return a;
}

int snt(int x)
{
    if (x<2)
        return 0;
    for (int i=2; i<=sqrt(x); i++)
        if (x%i==0)
            return 0;
    return 1;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int x;
        cin>>x;
        int d = 0;
        for (int i=1; i<=x; i++)
        {
            if (ucln(i, x)==1)
                d++;
        }
        if (snt(d)==1)
            cout<<"1"<<endl;
        else
            cout<<"0"<<endl;
    }
    return 0;
}

JAVA:

...

Python:

...

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:

...

BCPOW - Lũy thừa

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

• Problem:

Cho hai số n, m nguyên dương (n,m<=200). Hỏi trong biểu diễn thập phân của tổng  S=2n+3m chữ số  Cho hai số n, m nguyên dương (n,m<=200). Hỏi trong biểu diễn thập phân của tổng  S=2^n+3^m chữ số đầu tiên là chữ số nào? 
Ví dụ : 
với n=4 , m=2 thì S=25 có chữ số đầu tiên là 2. 
Với n=8, m=4 thì s=337 có chữ số đầu là 3. 

Input

Dữ liệu vào gồm một dòng duy nhất ghi 2 số n, m cách nhau bởi dấu cách.

Output

Một số duy nhất là đáp số của bài toán.

Example:

Input

4 2

Output:

2

Input

8 4

Output:

3

• Solution:

- n, m <= 200 nên sẽ phải dùng số nguyên lớn để xử lý (cộng string)
- Code dưới đây chia làm 2 phần: Công số nguyên lớn và Lũy thừa số nguyên lớn.
+ Cong: Để cộng hai string như một số thì ta phải quy nó về cùng chiều dài số lơn nhất, sau đó áp dụng quy tắt cộng và nhớ số từ cuối lên đầu.
VD:
a = "123"
b = "4567"
->
a = "0123"
b = "4567"
<- "+", rs = "" , remember = 0
3 + 7 + 0 = 10 -> rs =    "0"  remember = 1
2 + 6 + 1 =  9 -> rs =   "90"  remember = 0
1 + 5 + 0 =  6 -> rs =  "690"  remember = 0
0 + 4 + 0 =  4 -> rs = "4690"  remember = 0
+ Luythua: đối với luy thừa thì thực chất ta cộng nhiều số lại với nhau thôi.
VD: 2^3 = 2*2*2
-> rs = "2"
rs = rs*2
-> rs = Cong(rs, rs) = 4
rs = rs*2
-> rs = Cong(rs, rs) = 8

• Code:

C++:

https://ideone.com/fYJSFb

#include <iostream>
#include <math.h>
using namespace std;

string Cong(string a, string b)
{
    int len = max(a.length(), b.length());
    while (a.length()<len)
        a="0"+a;
    while (b.length()<len)
        b="0"+b;
    /*
    a = 123
    b = 4567
    ->
    a = 0123
    b = 4567
    */
    string rs = "";
    int remember = 0;
    for (int i=len-1; i>=0; i--)
    {
        int n1 = a[i]-'0';
        int n2 = b[i]-'0';
        int s = n1+n2+remember;
        
        char rs_tmp = s%10 + '0';
        rs = rs_tmp + rs;
        remember = s/10;
    }
    if (remember!=0)
        return char(remember+'0')+rs;
    return rs;
}

string luythua(string x, int n, int d)
{
    if (n==0) return "1";
    else if (n==1) return x;
    string rs = x;
    for (int i=2; i<=n; i++)
    {
        string rs_tmp = rs;
        for (int j=2; j<=d; j++)
        {
            rs = Cong(rs, rs_tmp);  //2^3 = ((2)*2)*2 = ((2)+(2))+((2)+(2))
        }
    }
    return rs;
}

int main()
{
    int n, m;
    cin>>n>>m;
    string lt2 = luythua("2", n, 2);
    string lt3 = luythua("3", m, 3);
    
    string S = Cong(lt2, lt3);
    
    cout<<S[0];
    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:

...