結果
| 問題 |
No.297 カードの数式
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:16:37 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,437 bytes |
| コンパイル時間 | 891 ms |
| コンパイル使用メモリ | 81,952 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:18:02 |
| 合計ジャッジ時間 | 3,603 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 1 TLE * 1 -- * 21 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <climits> // For LLONG_MAX, LLONG_MIN
#include <vector>
#include <cctype> // For isdigit
// Use standard namespace
using namespace std;
// Define long long type alias for convenience
typedef long long ll;
// Global variables
int N; // Number of cards
vector<char> cards; // Stores the characters on the cards ('0'-'9', '+', '-')
vector<bool> is_digit; // Precomputed check: true if card at index i is a digit
// Variables to store the maximum and minimum results found across all valid expressions
// Initialize max_res to the smallest possible long long value and min_res to the largest.
ll max_res = -LLONG_MAX;
ll min_res = LLONG_MAX;
/**
* @brief Recursive search function to explore all valid permutations of cards forming arithmetic expressions.
*
* This function uses backtracking to try placing each available card at the current position,
* ensuring the placement follows the problem rules (no operator at start/end, no adjacent operators).
* It evaluates the expression on the fly, from left to right.
*
* @param pos Current position in the sequence being built (from 1 to N).
* @param used_mask Bitmask indicating which cards have been used. A '1' at bit `i` means card `i` is used.
* @param current_val The accumulated value of the expression evaluated so far, *before* processing the number currently being formed.
* @param current_num_val The numeric value of the number segment currently being formed by consecutive digits. Example: if sequence is "123", current_num_val becomes 1, then 12, then 123.
* @param has_started_num Flag indicating if the current number segment has received at least one digit. True if yes, False if the number slot is currently empty (e.g., right after an operator). This helps distinguish a number '0' from an empty slot.
* @param last_op The operator ('+' or '-') that appeared immediately before the current number segment. For the very first number, this is initialized to '+', assuming the expression starts effectively as "0 + first_number...".
* @param last_card_type Type indicator for the card placed at position `pos-1`. 0: none (at the start), 1: digit, 2: operator. Used for rule checking.
*/
void search(int pos, int used_mask, ll current_val, ll current_num_val, bool has_started_num, char last_op, int last_card_type) {
// Base case: If we have successfully placed N cards, the sequence is complete. (Position index reaches N+1)
if (pos == N + 1) {
// The expression must end with a digit. This implies the last card placed (at pos=N) must have been a digit.
// Consequently, `has_started_num` must be true, indicating a number segment was being formed or just completed.
if (!has_started_num) {
// If `has_started_num` is false, it means the sequence ended with an operator, which is invalid.
// This path should not be reached if the rule checks within the recursion are correct, but added as a safety check.
return;
}
// Calculate the final value of the expression by applying the `last_op` to the `current_num_val` (the last number segment).
ll final_val;
if (last_op == '+') {
final_val = current_val + current_num_val;
} else { // last_op must be '-'
final_val = current_val - current_num_val;
}
// Update the global maximum and minimum results found so far.
// Check against initial LLONG_MAX/MIN values ensures first valid result sets the initial bounds.
if (max_res == -LLONG_MAX || final_val > max_res) {
max_res = final_val;
}
if (min_res == LLONG_MAX || final_val < min_res) {
min_res = final_val;
}
return; // End recursion for this path.
}
// Recursive step: Iterate through all available cards to decide which one to place at the current position `pos`.
for (int i = 0; i < N; ++i) {
// Check if the i-th card is available (check if the i-th bit in `used_mask` is 0).
if (!((used_mask >> i) & 1)) {
char card = cards[i]; // Get the character ('0'-'9', '+', or '-') from the i-th card.
// Check if the card is a digit.
if (is_digit[i]) {
// Try placing a digit card.
// Calculate the new value of the number segment by appending this digit.
// This handles leading zeros correctly. For example:
// If current_num_val is 0 and card is '0', next_num_val becomes 0*10 + 0 = 0.
// If current_num_val is 0 and card is '1', next_num_val becomes 0*10 + 1 = 1.
// If current_num_val is 12 and card is '3', next_num_val becomes 12*10 + 3 = 123.
ll next_num_val = current_num_val * 10 + (card - '0');
// Placing a digit is generally allowed unless it violates sequence rules.
// Rules checked: Digits can follow digits or operators. Digit can be the first card. Digit must be the last card.
// These rules are enforced by constraints on operators and the base case check. No specific check needed here.
// Recursive call for the next position (`pos + 1`):
// Update `used_mask` by setting the i-th bit.
// `current_val` remains unchanged because we are still forming the same number segment.
// Pass the updated number value `next_num_val`.
// Set `has_started_num` to true, as we've now placed at least one digit in this segment.
// `last_op` remains unchanged.
// Set `last_card_type` to 1 (digit).
search(pos + 1, used_mask | (1 << i), current_val, next_num_val, true, last_op, 1);
} else { // The card is an operator ('+' or '-').
// Try placing an operator card.
// Check validity based on problem rules:
// Rule: Cannot start with an operator. Check if `pos` is 1.
if (pos == 1) continue; // Invalid position for operator: cannot be the first card.
// Rule: Cannot end with an operator. Check if `pos` is N.
if (pos == N) continue; // Invalid position for operator: cannot be the last card.
// Rule: Operators cannot be adjacent. Check if the previous card was also an operator.
if (last_card_type == 2) continue; // Invalid: two operators consecutively.
// Rule: An operator must follow a completed number segment.
// This requires that the previous card was a digit (`last_card_type == 1`).
// Also check `has_started_num` which must be true, ensuring a number segment was actually formed before this operator.
if (!has_started_num) continue; // Invalid: operator must follow a number.
// If the placement is valid, calculate the intermediate accumulated value.
// Apply the `last_op` to the `current_num_val` (the number segment just completed).
ll next_val;
if (last_op == '+') {
next_val = current_val + current_num_val;
} else { // last_op must be '-'
next_val = current_val - current_num_val;
}
// Recursive call for the next position (`pos + 1`):
// Update `used_mask` by setting the i-th bit.
// Pass the newly calculated intermediate value `next_val`.
// Reset `current_num_val` to 0 for the next number segment.
// Set `has_started_num` to false, as the new number segment starts empty.
// Pass the current operator `card` as the new `last_op`.
// Set `last_card_type` to 2 (operator).
search(pos + 1, used_mask | (1 << i), next_val, 0, false, card, 2);
}
}
}
}
int main() {
// Optimize C++ standard streams for faster Input/Output.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read input N, the number of cards.
cin >> N;
// Resize vectors to hold card information for N cards.
cards.resize(N);
is_digit.resize(N);
string card_str; // Temporary string variable to read card characters from input.
// Read N card characters from the second line of input.
for (int i = 0; i < N; ++i) {
cin >> card_str;
cards[i] = card_str[0]; // Store the character.
// Precompute if the card is a digit using standard library function `isdigit`. Store boolean result.
if (isdigit(cards[i])) {
is_digit[i] = true;
} else {
is_digit[i] = false;
}
}
// Start the recursive search process from the first position (pos=1).
// Initial state: mask=0 (no cards used), current_val=0, current_num_val=0, has_started_num=false, last_op='+', last_card_type=0 (none).
search(1, 0, 0, 0, false, '+', 0);
// After exploring all valid permutations, output the final maximum and minimum values found.
// Values are separated by a space.
cout << max_res << " " << min_res << endl;
return 0; // Indicate successful execution.
}