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: