Can you help me.

Question

Armenian schoolchildren have created a robot that moves along the top of the rectangular network of nxm sizes. At the same time it can move,

right
top
up-right
   Your task is to find the number of possible roads that will reach the point (n, m) of the robot (0,0).

Input Details:

   The n and m are the natural numbers

Exit data

   The number of roads that should not exceed 10^18 should be deducted.

Answer 1

I'm doing tests for any scenarios you can think of, but I can't find any pattern in my output which could further reduce my algorithm complexity for n and m.
It's so frustrating.

Answer 2

As a hint, I will say that for every move that gets you one more up, and one more right, there are 3 ways of doing that:
top,right
right,top
up-right

So, if starting from the bottom-left corner, if n=m then there are 3*n ways of doing it. And for the general case there are 3*min(n,m) + |n-m| ways, where |x| is the absolute value of x. So

3*min(n,m) + |n-m|

is your answer.

To add on this, you can see that if the values of n and m are interchanged the answer does not change. This is because the number of paths from (0,0) to (n,m) is the same as the number of paths from (0,0) to (m,n), meaning that it is symmetric across the main diagonal, as the formula suggests. I leave it for you to check why I've chosen to add |n-m|.

Answer 3

I would like to know where I've gone wrong

Answer 4

Nevermind, I've notoced it.

Answer 5

Your integer type for the result needs at least 60 bits, excluding the sign bit.

Answer 6

You could solve that recursively.

Answer 7

If m equals 0, there is one way.
If m equals 1, there are 1 + n * 2 ways.

Answer 8

In general, we have 1 + (n - nRobot) * 2 ways to increment m while still being able to reach (n, m).

Answer 9

There is at least one way to solve this problem.

Answer 10

There are at least m * (1 + n * 2) ways to solve this problem.

Answer 11

//correct but SLOW C++ code

#include <cstdint>

using Int = std::int64_t;

Int ways(const Int n, const Int m)
{
if (n == 0 || m == 0)
return 1;

Int result = ways(n, m - 1);

for (Int new_n = 0; new_n != n; ++new_n)
result += 2 * ways(new_n, m - 1);

return result;
}

Answer 12

Here is some output for squares (side length to way count):

0: 1
1: 3
2: 13
3: 63
4: 321
5: 1683
6: 8989
7: 48639
8: 265729
9: 1462563
10: 8097453
11: 45046719
12: 251595969
13: 1409933619
14: 7923848253
15: 44642381823
16: 252055236609
17: 1425834724419

Answer 13

If m is a constant, as n approaches infinity, ways(n, m)' approaches one and ways(n, m) approaches infinity.

Answer 14

Why is my answer wrong?

Answer 15

Give me two natural numbers n and m where ways(n, m) returns the wrong value.

Answer 16

You can't just claim that something is wrong without proving it or pointing out why you think so.

Answer 17

thanks for replac,but your facts dont true.

Answer 18

there isnt own right anwser