Problem K. Skills in Pills
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 256 megabytes
An unnamed protagonist of this task received amazing e-mail offers for wondrous pills that will enhance
their cognitive and all other sorts of abilities. After carefully analyzing all offers and side effects, he has
decided that he will order 2 types of pills, let’s call them A and B. He needs to take pill A every k days
and pill B every j days. He will follow this meticulously over the next n days.
More formally, in the next n days, there should be no k consecutive days where he does not take pill A and
no j consecutive days where pill B is not taken. However, there is a twist – the two pills are highly potent
and must not be taken on the same day, least horrible side effects should happen. Given this constraint,
what is the smallest number of pills that he needs to take to meet these requirements?
input
You are given three space-separated integers, k, j, and n.
Constraints
? 2 ≤ n ≤ 106
? 2 ≤ k, j ≤ n
output
Print one number – the minimum number of pills that need to be taken. It is easy to prove that a solution
always exists for the given constraints.
Examples
standard input standard output
2 3 8 6
2 3 11 9
3 7 100 48
note
In the first case, we can take pill A on days 2, 4, 5, and 7, and pill B on days 3 and 6, giving the sequence
.ABAABA. In the second case, the best approach is to take pills in sequence .ABAABAABA. which
requires taking 9 pills.
Question meaning: There are two kinds of medicines, you can take one medicine or not take it every day, you can’t take both kinds at the same time, A requires continuous
a
a
eat at least a day
1
1
1 capsule, drug B requires continuous
b
b
Eat at least b days
1
1
1 capsule, in succession
no
no
Take at least several pills in n days.
Greedy, for considering the first
i
i
For one day, the last time of medicine A and medicine B is delayed, and the results will not get worse.
consider only in
a
∣
i
a|i
eat on the day of a∣i
a
a
a medicine,
b
b
b medicine is the same.
then in
l
c
m
(
a
,
b
)
lcm(a,b)
lcm(a,b) will hit the sky.
because
a
,
b
>
=
2
a,b>=2
a, b>=2, so the day before the collision
a
,
b
a,b
Medicines a and b are not taken, and one of the medicines can be postponed for 1 day.
make
f
[
i
]
[
0
]
f[i][0]
f[i][0] means eating today
j
=
=
0
?
a
:
b
j==0?a:b
j==0?a:b medicine, take it tomorrow
j
=
=
0
?
b
:
a
j==0?b:a
j==0?b: A medicine, there are n days left, so how much medicine should be taken including today,
dp
#include <bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i ++ )
#define Fork(i,k,n) for(int i=k;i<=n;i ++ )
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define Rep(i,n) for(int i=0;i<n;i ++ )
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (o<<1)
#define Rson ((o<<1) + 1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,0x3f,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define MEMx(a,b) memset(a,b,sizeof(a));
#define INF (0x3f3f3f3f)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a). size())
#define Pr(kcase,ans) printf("Case #%d: %lld\
",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) {<!-- --> \
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
#define gmax(a,b) a=max(a,b);
#define gmin(a,b) a=min(a,b);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){<!-- -->return (a*b)%F;}
ll add(ll a,ll b){<!-- -->return (a + b)%F;}
ll sub(ll a,ll b){<!-- -->return ((a-b)%F + F)%F;}
void upd(ll & amp;a,ll b){<!-- -->a=(a%F + b%F)%F;}
inline int read()
{<!-- -->
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {<!-- -->if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {<!-- --> x=x*10 + ch-'0'; ch=getchar();}
return x*f;
}
#define MAXN (1000000 + 10)
ll f[MAXN][2]; //f[i][0]=ab(remain i days) f[i][1]=ba(remain i days)
int main()
{<!-- -->
int a=read(),b=read(),n=read();
//ab
int dab=2,dba=2;
while(dab<=n & amp; & amp; (dab%a!=0 ||(dab-1)%b!=0)) {<!-- -->
+ + dab;
}
while(dba<=n & amp; & amp; (dba%b!=0 ||(dba-1)%a!=0)) {<!-- -->
+ + dba;
}
f[0][0]=f[0][1]=2;
For(i,n) {<!-- -->
f[i][0]=f[i-1][0] + ((i + 1)%a==0) + (i%b==0);
f[i][1]=f[i-1][1] + ((i + 1)%b==0) + (i%a==0);
if(i-1>=dab) f[i][0]=f[dab-3][0] + min(f[i-(dab-3)-2][0],f[i-( dab-3)-2][1]);
if(i-1>=dba) f[i][1]=f[dba-3][1] + min(f[i-(dba-3)-2][0],f[i-( dba-3)-2][1]);
\t\t
}
ll ans=0;
For(i,n) {<!-- -->
if(i%a==0 & amp; & amp; i%b==0) {<!-- -->
ans + =min(f[n-i][0],f[n-i][1]);
break;
}
ans + =(i%a==0) + (i%b==0);
}
cout<<ans;
return 0;
}