結果
| 問題 |
No.2039 Copy and Avoid
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:21 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 69 ms / 2,000 ms |
| コード長 | 9,538 bytes |
| コンパイル時間 | 1,398 ms |
| コンパイル使用メモリ | 115,556 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:12 |
| 合計ジャッジ時間 | 2,939 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 31 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath> // Include cmath for sqrt
using namespace std;
// Define long long type for large integers
typedef long long ll;
// Use a sufficiently large value for infinity.
// Maximum possible cost could be around N*A, which can be up to 10^9 * 10^9 = 10^18.
// std::numeric_limits<ll>::max() is about 9e18. 4e18 should be safe enough as infinity marker.
const ll INF = 4e18;
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll N; // Target value for x
int M; // Number of forbidden integers
ll A, B; // Costs for operation a and operation b
cin >> N >> M >> A >> B;
set<ll> forbidden_set; // Use set for efficient lookup if needed, though not primarily used in the final DP approach
vector<ll> C_input(M); // Store input forbidden integers
for (int i = 0; i < M; ++i) {
cin >> C_input[i];
forbidden_set.insert(C_input[i]);
}
// Sort the forbidden integers. This helps in efficiently finding the first forbidden multiple later.
sort(C_input.begin(), C_input.end());
// Base case: If N=1, we are already at the target state (1, 1). Cost is 0.
if (N == 1) {
cout << 0 << endl;
return 0;
}
// Problem constraints state C_i >= 2 and C_i <= N-1.
// This implies that the initial state x=1 is never forbidden, and the target state x=N is never forbidden.
// Find all divisors of N. This is needed because the DP state relies on divisors.
vector<ll> divs;
ll sqrtN = sqrt(N); // Compute square root once for efficiency
for (ll i = 1; i <= sqrtN; ++i) {
if (N % i == 0) {
divs.push_back(i);
// Add the corresponding larger divisor if it's different from i
if (N / i != i) {
divs.push_back(N / i);
}
}
}
sort(divs.begin(), divs.end()); // Sort the divisors
int tauN = divs.size(); // Number of divisors of N
map<ll, int> div_idx; // Map divisor value to its index in the sorted vector `divs`
for (int i = 0; i < tauN; ++i) {
div_idx[divs[i]] = i;
}
// Precompute the minimum forbidden multiple for each divisor d'.
// This optimization speeds up validity checks during DP transitions.
// `min_forbidden_multiple[i]` stores the minimum forbidden value C_p such that C_p > divs[i] and divs[i] divides C_p.
// If no such forbidden multiple exists, it stores INF.
vector<ll> min_forbidden_multiple(tauN, INF);
for (int i = 0; i < tauN; ++i) {
ll d_prime = divs[i];
// Iterate through the sorted list of forbidden values
for (ll forbidden_val : C_input) {
// Check conditions: must be greater than d' and divisible by d'
if (forbidden_val > d_prime && forbidden_val % d_prime == 0) {
min_forbidden_multiple[i] = forbidden_val; // First one found is the minimum because C_input is sorted
break; // Found the minimum, no need to check further forbidden values for this d'
}
}
}
// DP table: dp[i] stores the minimum cost to reach the state (divs[i], divs[i])
vector<ll> dp(tauN, INF);
// Initialize DP: The initial state is (1, 1) with cost 0. divs[0] is always 1.
dp[0] = 0;
// Dynamic Programming calculation
// Iterate through all divisors d' = divs[i]
for (int i = 0; i < tauN; ++i) {
ll d_prime = divs[i];
// If state (d', d') is unreachable (cost is INF), skip transitions from it
if (dp[i] == INF) continue;
// Iterate through all larger divisors d = divs[j]
for (int j = i + 1; j < tauN; ++j) {
ll d = divs[j];
// Check if d is reachable from d' via a block operation: d = (1+k) * d'
if (d % d_prime == 0) {
// Calculate k: the number of 'a' operations in the block
ll k = d / d_prime - 1;
// Since j > i, d > d', so d/d' >= 2 (integer division if d' divides d). Thus k >= 1.
// Check validity: The sequence of x values generated by 'a' operations is (1+1)d', (1+2)d', ..., (1+k)d' = d.
// None of these intermediate values should be forbidden.
// We only need to check the minimum forbidden multiple of d' that is > d'.
bool valid = true;
// Use the precomputed minimum forbidden multiple for d' (`divs[i]`)
if (min_forbidden_multiple[i] <= d) {
// If the minimum forbidden multiple is less than or equal to d, it means it's encountered during the 'a' operations sequence.
valid = false;
}
if (valid) {
// If the path segment is valid, update the DP state for d
// Calculate cost for 'a' operations: k*A. Check for potential overflow.
ll cost_A = 0;
if (A > 0 && k > 0) {
// Use long double for intermediate check to prevent overflow with standard `ll` multiplication if k and A are large
// Check if k*A potentially exceeds INF. If so, treat cost as INF.
if (k > INF / A) { // More robust check against overflow
cost_A = INF;
} else {
cost_A = k * A;
}
}
// Check for overflow before adding costs: dp[i] + cost_A + B
if (cost_A == INF || dp[i] == INF || cost_A > INF - B || dp[i] > INF - B - cost_A) {
// If calculation results in INF or would overflow, skip update (or assign INF explicitly)
// Here we just continue, effectively skipping updates that would lead to costs >= INF
} else {
// Update dp[j] with the minimum cost found so far
dp[j] = min(dp[j], dp[i] + cost_A + B);
}
}
}
}
}
// Calculate the final minimum cost to reach x = N
ll min_total_cost = INF;
// Consider the special path using only 'a' operations: (1, 1) -> (2, 1) -> ... -> (N, 1)
// This path consists of N-1 'a' operations. Cost is (N-1)*A.
bool special_path_valid = true;
// This path is valid if and only if no forbidden number C_p exists in the range [2, N].
if (!C_input.empty()) {
ll min_C = C_input[0]; // C_input is sorted, so C_input[0] is the minimum forbidden value.
if (min_C <= N) { // If the smallest forbidden number is <= N, it blocks this path.
special_path_valid = false;
}
}
if (special_path_valid) {
if (N > 1) { // Avoid calculation if N=1 (handled at start)
ll cost_A = 0;
if (A > 0 && N - 1 > 0) {
if (N - 1 > INF / A) { // Check for overflow
cost_A = INF;
} else {
cost_A = (N - 1) * A;
}
}
min_total_cost = min(min_total_cost, cost_A);
} else {
min_total_cost = 0; // Should have been handled, but safe check.
}
}
// Consider paths ending with a sequence of 'a' operations starting from a state (d, d)
for (int i = 0; i < tauN; ++i) {
ll d = divs[i]; // Current divisor representing state (d, d)
// If state (d, d) is unreachable, skip
if (dp[i] == INF) continue;
// Check if N is reachable from d by multiplication factor (N = (1+k)d)
if (N % d == 0) {
// Calculate k: number of 'a' operations in the final sequence
ll k = N / d - 1;
// If k<0, this means d > N, impossible. N=d case is k=0.
// Check validity: intermediate x values (1+p)d for 1 <= p <= k must not be forbidden
bool valid = true;
// Use the precomputed minimum forbidden multiple of d (`divs[i]`) that is > d
if (min_forbidden_multiple[i] <= N) { // Check if this minimum forbidden multiple is encountered before or at N
valid = false;
}
if (valid) {
// Calculate cost for final 'a' operations
ll cost_A = 0;
if (A > 0 && k > 0) {
if (k > INF / A) { // Check for overflow
cost_A = INF;
} else {
cost_A = k * A;
}
}
// Check for overflow before adding dp[i] + cost_A
if (cost_A == INF || dp[i] == INF || cost_A > INF - dp[i]) {
// If cost is INF or would overflow, skip this path
} else {
// Update the overall minimum total cost
min_total_cost = min(min_total_cost, dp[i] + cost_A);
}
}
}
}
// Output the final result
if (min_total_cost == INF) {
cout << -1 << endl; // If INF, it's impossible to reach N
} else {
cout << min_total_cost << endl; // Otherwise output the minimum cost found
}
return 0;
}