Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Grid's paths, River crossing pawn, and avoiding Knight's move, start to end count
Разница между en3 и en4, 42 символ(ов) изменены
// my attemt using Monte Carlo, effective when the number is small, but will resulting in RE when dealing with larger numbers↵
<pre><code
 class="cpp">↵
#include 
<&lt;iostream>&gt;↵
#include 
<&lt;cstdlib>&gt;↵
#include 
<&lt;ctime>&gt;↵
using namespace std;↵
int rand01()↵
{↵
return rand() % 2;↵
}↵
struct point↵
{↵
int x, y;↵
};↵
int distance(point A, point B)↵
{↵
return (A.x &mdash; B.x) * (A.x &mdash; B.x) + (A.y &mdash; B.y) * (A.y &mdash; B.y);↵
}↵
bool cmp(point m, point n)↵
{↵
return (m.x == n.x && m.y == n.y);↵
}↵
int main()↵
{↵
srand(time(0));↵
point horse, end;↵
static point path[399][39];↵
cin >> end.x >> end.y >> horse.x >> horse.y;↵
point temp;  int valid = 0; int fork; int flag = 0; int count = 0;↵
int attempt = 0;↵
while (attempt < 10000)↵
{↵
temp.x = temp.y = 0; int step = 0;↵
while (temp.x <= end.x && temp.y <= end.y && !cmp(temp, end))↵
{↵
fork = rand01();↵
int tempx = temp.x, tempy = temp.y;↵
if (temp.x < end.x && temp.y < end.y)↵
{↵
temp.x = temp.x + fork, temp.y = temp.y + 1 &mdash; fork;↵
}↵
else if (temp.x == end.x && temp.y < end.y)↵
temp.y++;↵
else↵
temp.x++;↵
if (distance(temp, horse) != 5 && !cmp(temp, horse))↵
{↵
path[count][step] = temp;↵
step++;↵
}↵
else↵
{↵
flag = 999;↵
break;↵
}↵
}↵
for (int i = 0; i < count; i++)↵
{↵
for (int j = 0; j < step; j++)↵
{↵
if (cmp(path[count][j], path[i][j]))↵
flag++;↵
}↵
if (flag < step)↵
flag = 0;↵
}↵
if (flag < end.x + end.y &mdash; 1 && cmp(temp, end))↵
{↵
↵
valid++;↵
count++;↵
}↵
flag = 0;↵
attempt++;↵
}↵
cout << valid << endl;↵
}↵
</code></pre>↵
//suggestions :using DP will be better

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский yawn_lento 2026-07-22 05:33:52 33 Tiny change: 'introduced. However,' -> 'introduced(though still not very effective). However,'
en8 Английский yawn_lento 2026-07-22 05:23:58 970
en7 Английский yawn_lento 2026-07-21 05:10:51 12
en6 Английский yawn_lento 2026-07-21 05:09:09 82
en5 Английский yawn_lento 2026-07-21 05:05:33 1583
en4 Английский yawn_lento 2026-07-21 05:01:28 42
en3 Английский yawn_lento 2026-07-21 04:55:47 22
en2 Английский yawn_lento 2026-07-21 04:53:13 26
en1 Английский yawn_lento 2026-07-21 04:51:02 1725 Initial revision (published)