Official

C - False Hope Editorial by en_translator


There are \(9!=362880\) orders that he reveals the digits, which occur with the same probability.
Therefore, if we can determine for each of these \(362880\) cases whether he is disappointed or not, then the answer can be obtained as \((\) the number of ways that Takahashi is not disappointed \()/(\) the total number of ways to reveal the digits \()\).

One can determine if he will be disappointed by checking, for each vertical, horizontal, or diagonal line, whether there is a pair of squares with the same digit written on them, and if there are, inspecting if those two squares are seen prior to the other.

The sample code follows.
As in this problem, it is useful to use the next_permutation function to iterate through all permutations. Given an array, next_permutation returns the lexicographically next array. If there is no such array (\(=\) if the given array is sorted in descending order), it returns false.

Note that cout prints only six decimal places by default, so you must specify the precision to reduce the error to less than \(10^{-8}\).

#include <array>
#include <iostream>
#include <vector>
#include <tuple>
#include <numeric>
#include <algorithm>

int main() {
    using namespace std;

    array<int, 9> cells;
    for (auto &&c : cells)
        cin >> c;

    // vertical, horizontal, and diagonal lines
    vector<tuple<int, int, int>> row{{0, 1, 2}, // 1-st row from the top
                                     {3, 4, 5}, // 2-nd row from the top
                                     {6, 7, 8}, // 3-rd row from the top
                                     {0, 3, 6}, // 1-st column from the left
                                     {1, 4, 7}, // 2-nd column from the left
                                     {2, 5, 8}, // 3-rd column from the left
                                     {0, 4, 8}, // top-left to bottom-right
                                     {2, 4, 6}};// top-right to bottom-left

    array<int, 9> order; // the i-th square is opened for the order[i]-th time
    iota(begin(order), end(order), 0);

    int not_disappoint = 0, all = 0; // the number of disappointing and total ways
    do {
        ++all;
        bool disappoint_flag = false; // determines if this order disappoints him
        for (auto &&[a, b, c] : row) // For each triple of squares (a, b, c) that is in a line
            // it's disappointing if squares a and b are equal, and c are last square to be opened within these three
            if (cells[a] == cells[b] && order[a] < order[c] && order[b] < order[c])
                disappoint_flag = true;
            // same applies for the two other pairs that can be the same digit
            else if (cells[a] == cells[c] && order[a] < order[b] && order[c] < order[b])
                disappoint_flag = true;
            else if (cells[b] == cells[c] && order[b] < order[a] && order[c] < order[a])
                disappoint_flag = true;

        // If it is not disappointing, increment the count
        if (!disappoint_flag)
            ++not_disappoint;
    } while (ranges::next_permutation(order).found); // Try all ways to reveal it

    // Instruct to print 10 decimal places
    cout << setprecision(10);

    // Divide the number of ways that do not disappoint him by the total number of ways
    // Note that it must be calculated as a decimal
    cout << (double)not_disappoint / all << endl;

    return 0;
}

posted:
last update: