On the coordinate plane, when the ant is at (a, b), it can randomly move to one of the points (a-1, b), (a, b-1), or (a-1, b-1), and the probability of moving to any of these points is 1/3. Subsequent moves are independent of previous moves. Now, an ant is starting its movement from (x, y), and it stops moving when it encounters any coordinate axis for the first time. What is the probability that the ant's last stop is not at the origin (0, 0)?
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| EOF inputs: each test case inputs two positive integers x and y. (x, y <= 10) | The answer is represented as a fraction in its simplest form, output as "numerator/denominator." |
| 3 3 2 2 1 1 | 70/81 22/27 2/3 |
Thought Process
Since working with fractions can be challenging, we can simplify the computation by multiplying the probability of the origin (which is 100% or 1) by 3 raised to the power of a + b. We can use a two-dimensional array to store the probability of each point and iterate over each point using nested for loops. The numerator of the answer will be the probability of the original point (0, 0), and the denominator will be the probability of the original point. Finally, we simplify the fraction to its simplest form and output it.
Sample Code－ZeroJudge M283: Diffusion of Ants
#include <iostream>
#include <math.h>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int x, y;
while (cin >> x >> y)
{
long long int arr[20][20] = {0};
long long int og = pow(3, x+y);
arr[y][x] = og;
for (int yy = y; yy>0; yy--)
{
for (int xx = x; xx>0; xx--)
{
long long int tmp = arr[yy][xx] / 3;
arr[yy-1][xx] += tmp;
arr[yy][xx-1] += tmp;
arr[yy-1][xx-1] += tmp;
}
}
long long int up = og - arr[0][0];
long long int down = og;
bool stop = false;
while (!stop)
{
stop = true;
for (long long int i = 2; i<=sqrt(up)+1; i++)
{
if (up % i == 0 && down % i == 0)
{
up /= i;
down /= i;
stop = false;
}
}
}
cout << up << "/" << down << "\n";
}
}
//ZeroJudge M283
//Dr. SeanXD