Phần code của em:
int Count_bits(ll n)
{
int cnt = 0;
while (n != 0)
{
if (n % 2 == 1) cnt++;
n /= 2;
}
return cnt;
}
ll Decode(int n)
{
int i = 0;
ll sum = 0, factorial = 1;
while (n != 0)
{
if (n % 2 == 1) sum += factorial;
n /= 2;
i++;
factorial *= i;
}
return sum;
}
int main()
{
int num;
ll n;
cin >> num;
for (int i = 0; i < num; i++)
{
int Min = numeric_limits<int>::max();
cin >> n;
for (int j = 0; j < 32768; j++)
{
ll fac_sum = Decode(j);
if (fac_sum > n) break;
int bits = Count_bits(n - fac_sum);
Min = min(bits + Count_bits(j), Min);
}
cout << Min << endl;
}
return 0;
}
Ý tưởng phần code trên là: n = (a1! + a2! + … + (a_k)!) + (2^(b1) + … + 2^(b_t)). Trong đó, a trong khoảng từ 0 -> 14. Như vậy số hạng tử cần để tạo ra n = số hạng tử giai thừa + số hạng mũ 2 = k + t. Ta có tổng cộng 2^15 - 1 trường hợp(tương đương dùng hoặc không dùng 0!, 1!, …, 14!). Em xét hết các trường hợp i: 0 -> 2^15 -1 rồi:
Tính k dựa trên số bit của i
Tính t dựa trên số bit của (n - (a1! + a2! + … + (a_k)!))
Không hiểu sai gì nhưng hệ thống vẫn cho TLE. Trong khi bài cho 3 giây và em thấy code chỉ chạy trong khoảng O(10^8). : D. Em cảm ơn trước ạ.