CDOJ 1639 Fruit Ninja
Problem:http://www.acm.uestc.edu.cn/problem.php?pid=1639
一見面倒に見えるが、実際に考えなければならない特殊な状況は多くない.
まずINFの場合から始めるのが簡単で、mが10の倍数の場合、無限に加算することができ、例えば10000から始める.mが5ビットである場合、差は多くなくても無限に加算できるが、制限がある.例えば55555に追加すると、nを追加する必要があり、結果が5の倍数ではない可能性があります.しかし,nが5の倍数であれば,このような問題は起こらない.nが5の倍数でない場合,mについてそれぞれ議論できる.引っ掛かる可能性のある点は5555555555555555に現れます.
初期点数をa*5とすると、a*5+k*m=55555等のときに引っかかり、すなわちa+k*(m/5)=11111等となる.aを選択することで、点数が小さい数に引っかからないようにすることができます.
m=5の場合、必ず55555に引っかかりますが、結果は55555+m+nまでで、その時はmを付けずにそのまま間違いました.
m=15,m/5=3であり、11111等のデジタルモード3の場合を考慮すると、結果は2,0,1,2,0,1である.aは残りの2と0を避ける場合を合理的に選択することができ、この場合1に対応する1111111に引っかかるため、結果は555555555+m+nである.
m=25、m/5=511111等はいずれも型取りが1であるため、全ての数を避けることができ、結果はINFとなる..
特殊な状況を考慮した場合、最大はmax(9999+n+((9999+n)%5?0:m)、10000+m)である.
一見面倒に見えるが、実際に考えなければならない特殊な状況は多くない.
まずINFの場合から始めるのが簡単で、mが10の倍数の場合、無限に加算することができ、例えば10000から始める.mが5ビットである場合、差は多くなくても無限に加算できるが、制限がある.例えば55555に追加すると、nを追加する必要があり、結果が5の倍数ではない可能性があります.しかし,nが5の倍数であれば,このような問題は起こらない.nが5の倍数でない場合,mについてそれぞれ議論できる.引っ掛かる可能性のある点は5555555555555555に現れます.
初期点数をa*5とすると、a*5+k*m=55555等のときに引っかかり、すなわちa+k*(m/5)=11111等となる.aを選択することで、点数が小さい数に引っかからないようにすることができます.
m=5の場合、必ず55555に引っかかりますが、結果は55555+m+nまでで、その時はmを付けずにそのまま間違いました.
m=15,m/5=3であり、11111等のデジタルモード3の場合を考慮すると、結果は2,0,1,2,0,1である.aは残りの2と0を避ける場合を合理的に選択することができ、この場合1に対応する1111111に引っかかるため、結果は555555555+m+nである.
m=25、m/5=511111等はいずれも型取りが1であるため、全ての数を避けることができ、結果はINFとなる..
特殊な状況を考慮した場合、最大はmax(9999+n+((9999+n)%5?0:m)、10000+m)である.
#include <cstdio>
typedef long long ll;
int main()
{
int T, n, m;
scanf("%d", &T);
for(int ca=0; ca<T; ++ca)
{
scanf("%d%d", &m, &n);
if((m % 10) == 0)
printf("Case #%d: INF
", ca+1);
else if((m % 5) == 0)
{
if((n % 5) == 0)
printf("Case #%d: INF
", ca+1);
else
{
printf("Case #%d: ", ca+1);
switch(m)
{
case 5: printf("%lld", (ll)55555+(ll)(n+m)); break;
case 15: printf("%lld", (ll)5555555+(ll)(n+m)); break;
case 25: printf("INF"); break;
case 35: printf("INF"); break;
case 45: printf("%lld", (ll)5555555555555+(ll)(n+m)); break;
}
printf("
");
}
}
else
{
int max = 9999+n;
if(max % 5 == 0)
max += m;
if(10000+m > max)
max = 10000+m;
printf("Case #%d: %d
", ca+1, max);
}
}
return 0;
}