質問- リヴィウ動物園の子象はラッキーナンバーが大好きです。ラッキー ナンバーは正の整数であり、その 10 進表現にはラッキー ディジット 4 と 7 のみが含まれていることは誰もが知っています。たとえば、47、744、4 はラッキー ナンバーであり、5、17、467 はラッキー ナンバーではありません。
F4(X) を X の 10 進数表現の桁数 4、F7(X) を X の 10 進数表現の桁数 7 とします。たとえば、F4(456) = 1、F4(444) です。 = 3, F7(1) = 0, F7(747) = 2. 子象は最大の積 F4(X) ∙ F7(X) (L ≤ X ≤ R) を知りたがっています。値 max{F4(X) ∙ F7(X) : L ≤ X ≤ R}。
1 <= L <= R <= 10 18
例: 1) 範囲の場合、1 100 の回答は 1 {47,74} になります。
2) 4199 6000 の答えは 4 {4747, 4477} になります
私のコードは正しいと思いますが、送信すると、間違った回答という評決が下されます。何が問題なのかを正確に知るのを手伝ってくれる人はいますか?
私のアルゴリズムが間違っているはずはありません (非常に単純です)。実装を再確認しました (考えられるすべてのケースを処理します)。一部の入力が間違っているとは信じがたいです。
C++ コードは次のとおりです。
#include <cstdio>
#include <cstring>
using namespace std;
char buf1[20],buf2[20];
int *L, *R, *ans, len, ansn;
bool flagL, flagR;
inline int count(int n)
{
int a=0,c=0;
for(;a<len;a++) if(ans[a] == n) c++;
return c;
}
inline int max(int a, int b) { return a>b ? a:b; }
inline int min(int a, int b) { return a<b ? a:b; }
inline void f(int i, int n)
{
int a=0,n4=0,n7=0,t;
for(;a<=i;a++) if(ans[a] == 4) n4++; else if(ans[a] == 7) n7++;
while(n)
{
if(n4 == n7)
{
n4 += n/2;
n7 += (n-n/2);
break;
}
else if(n4 > n7)
{
t = min(n,n4-n7);
n -= t;
n7 += t;
}
else if(n7 > n4)
{
t = min(n,n7-n4);
n -= t;
n4 += t;
}
}
ansn = max(ansn,n4*n7);
}
void solve(int i, bool flagL, bool flagR)
{
while(i<len)
{
if(flagL && !flagR)
{
if(4 > L[i])
{
f(i-1,len-i);
return;
}
if(4 == L[i])
{
ans[i] = 4;
solve(i+1, 1, 0);
ans[i] = 7;
f(i,len-i-1);
return;
}
if(7 > L[i])
{
ans[i] = 7;
f(i,len-i-1);
return;
}
if(7 == L[i])
{
ans[i] = 8;
f(i,len-i-1);
ans[i] = 7;
i++;
continue;
}
// else
ans[i] = 9;
if(ans[i] > L[i])
{
f(i,len-i-1);
return;
}
else
{
i++;
continue;
}
}
if(!flagL && flagR)
{
if(7 < R[i])
{
f(i-1,len-i);
return;
}
if(7 == R[i])
{
ans[i] = 4;
f(i,len-i-1);
ans[i] = 7;
i++;
continue;
}
if(4 < R[i])
{
ans[i] = 4;
f(i,len-i-1);
return;
}
if(4 == R[i])
{
ans[i] = 3;
f(i,len-i-1);
ans[i] = 4;
i++;
continue;
}
// else
ans[i] = 0;
if(ans[i] < R[i])
{
f(i,len-i-1);
return;
}
else
{
i++;
continue;
}
}
if(flagL && flagR)
{
if(R[i] - L[i] == 1)
{
ans[i] = L[i];
solve(i+1,1,0);
ans[i]++;
solve(i+1,0,1);
return;
}
bool four = 4 > L[i] && 4 < R[i];
bool sev = 7 > L[i] && 7 < R[i];
if (four && sev)
{
f(i-1,len-i);
return;
}
else if (four && !sev)
{
ans[i] = 4;
f(i,len-i-1);
}
else if (!four && sev)
{
ans[i] = 7;
f(i,len-i-1);
}
if (L[i] == 4 || L[i] == 7 || R[i] == 4 || R[i] == 7)
{
if(L[i] == R[i]) { ans[i] = L[i]; i++; continue; }
if(L[i] == 4 && R[i] == 7)
{
ans[i] = 4;
solve(i+1,1,0);
ans[i] = 7;
solve(i+1,0,1);
ans[i] = 5;
f(i,len-i-1);
return;
}
if(R[i] - L[i] >= 2)
{
ans[i] = L[i]+1;
f(i,len-i-1);
if(L[i] == 4 || L[i] == 7)
{
ans[i] = L[i];
solve(i+1,1,0);
}
if(R[i] == 4 || R[i] == 7)
{
ans[i] = R[i];
solve(i+1,0,1);
}
return;
}
}
else
{
if (R[i] - L[i] >= 2)
{
ans[i] = L[i]+1;
f(i,len-i-1);
return;
}
ans[i] = L[i];
}
}
i++;
} // end of while
ansn = max(ansn, count(4)*count(7));
}
int main()
{
int a,t; scanf("%d\n",&t);
while(t--) // test cases
{
scanf("%s %s",&buf1,&buf2);
len = strlen(buf2);
L = new int[len];
R = new int[len];
ans = new int[len];
for(a=0;a<len;a++) R[a] = buf2[a]-48;
for(a=0;a<len-strlen(buf1);a++) L[a] = 0;
int b=a;
for(;a<len;a++) L[a] = buf1[a-b]-48;
flagL = flagR = 1; ansn = 0;
solve(0,1,1);
printf("%d\n",ansn);
}
return 0;
}
アルゴリズム:
まず、長さ = no の配列 L[]、R[] に L、R の数字を入れます。そして、答えの整数 (F4(ans)*F7(ans) が最大になる整数) を追跡するための配列 ans[] を初期化します。
L の左側を 0 で埋めて、長さが R と等しくなるようにします。(したがって、1,100 は 001,100 になります) これは、solve() を呼び出す前に、main() 自体で行われます。
実際のロジック: for i in range(0,len(R)) ループを実行します。各 i について、L[i] と R[i] を比較します。
変数flagLとflagRは、L と R をそれぞれチェックする必要があるかどうかを示します。
L[]、R[] が最初は 238 967 であると仮定すると、最初に 0 番目のインデックスから開始して両方をチェックする必要があります (したがって、 solve(0,1,1) または solve(0,true,true) )。
現在、4 と 7 は両方ともL[0] と R[0]の間にあります。そのため、 ans[] が[L,R]の範囲外になることなく、 {4,7} の任意の順列を 3 桁に入れることができます。したがって、答えは 2 になります。
範囲が 238 ～ 545 の場合
2 と 5の間に入るのは 4 だけなので、4 を ans[0] に入れ、{4,7} の任意の順列を残りの場所に入れることができます。ですから、答えはまた 2 です。
範囲が 238 と 410 の場合
4 も 7 も L[0] と R[0] の間にありません。ただし、R[0] は 4 であることに注意してください。
したがって、4 と L[0]+1 の 2 つの選択肢があります (ここで再帰の出番です)。
L[0]+1 の理由 L[0]+1 を ans[0] に入れると、ans[0] は L[0] と R[0] の間に収まるため (この R[0] - L[0] >= 2 の場合)、残りの桁に何を入れても、ans[] が範囲外になることはありません。しかし、ans[0] が 4 であることも確認する必要があります。最後の例では役に立ちませんが、R が >= 477 であれば役に立ちます。
したがって、答えは 1 になります (R が >= 477 の場合は 2)。
別の例について説明しましょう。
範囲: 4500 5700
R[0] と L[0] の違いは 1 だけなので、両方をチェックする必要があります。1 回は ans[i] = L[i]、次に ans[i] = R[i] (または ans[i] ]++ )
ここで ans[i] = 4 を確認すると、ans[0] < R[0] であるため、ans[i] と R[i] を比較する必要がなくなります。したがって、ansは常に < Rになります。したがって、次のように solve() を再帰的に呼び出します: solve(i+1, true, false)
次回、ans[0] = R[0] の場合、ans と L を比較する必要はありません (ans > L であるため、残りの 2 か所に何を入れても)。次に、次のように solve() を呼び出します: solve(i+1, false, true)。
それがどのように機能しているかがわかります。また、私のコードを見ると、可能なテスト ケースが除外されていません。なぜWAを取得するのかわかりません。
PS: Andrew が間違いを指摘しました。条件の順序が間違っていました。if ブロック4 == L[i]は if ブロックの前に来る必要があります7 > L[i]。これで、コードは正しく機能します。