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.
InputVí 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.
Dòng duy nhất chứ số N là số gạo mẹ Tuyenlv7 cho ( 0 < N < 5000).
Output
Example:
In ra đáp án của bài toán.
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
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:
...