ポンゴのヒーローは数字を覆う
ポンゴのカバー数字の原題は以下の通りです.
整数区間[a,b]と整数区間[x,y]を与えて、あなたは任意の何回のa,bの間の整数を使って加算することができて、何個の[x,y]区間内の整数を集めることができますか?a,b,x,yと入力し、ここで1<=aこの問題は間違った問題の意味を理解し始め、最大同じ数が2回加算されると思っていたが、実際には同じ数を何度も加算することができる.
例えばa=8,b=10,x=3,y=30の場合は,24から30まで(8+8+8…10+10+10)に上書きできる.
では,上書きできない場合を考慮すると,上書きできない区間はr=[i*b+1,(i+1)*a−1],iが0からy/bまでである.
では,区間r>0の場合iの取値範囲はどれくらいであるか,すなわち(i+1)*a−1−(i*b+1)>0を求める.
当iを求める
次にi以下の被覆不能区間rと区間[x,y]の交差countを求める
累積交差count
最後にy-x-count+1を返します
コードは次のとおりです.
整数区間[a,b]と整数区間[x,y]を与えて、あなたは任意の何回のa,bの間の整数を使って加算することができて、何個の[x,y]区間内の整数を集めることができますか?a,b,x,yと入力し、ここで1<=aこの問題は間違った問題の意味を理解し始め、最大同じ数が2回加算されると思っていたが、実際には同じ数を何度も加算することができる.
例えばa=8,b=10,x=3,y=30の場合は,24から30まで(8+8+8…10+10+10)に上書きできる.
では,上書きできない場合を考慮すると,上書きできない区間はr=[i*b+1,(i+1)*a−1],iが0からy/bまでである.
では,区間r>0の場合iの取値範囲はどれくらいであるか,すなわち(i+1)*a−1−(i*b+1)>0を求める.
当iを求める
次にi以下の被覆不能区間rと区間[x,y]の交差countを求める
累積交差count
最後にy-x-count+1を返します
コードは次のとおりです.
public class Test
{
public static int howmany(int a,int b,int x,int y)
{
int j = (a - 2) / (b - a) > y / b ? y / b : (a - 2) / (b - a);
int count = 0;
int i = 0;
while (i <= j) {
int c = i * b + 1;
int d = (i + 1) * a - 1;
int max = c > x ? c : x;
int min = d > y ? y : d;
if (min - max + 1 > 0) {
count += (min - max + 1);
}
i++;
}
return y - x - count + 1;
}
//start : , 。
public static void main(String args[])
{
System.out.println(howmany(0,0,0,0));
}
//end // : , 。
}