【頭脳試し】Imagine Cupアルゴリズム【ネタバレ】
■ このスレッドは過去ログ倉庫に格納されています
0280デフォルトの名無しさん
05/02/19 15:41:523 blind spiders and I smart bug. All spiders start from
the same vertex and follow a known (to all spiders and the bug)
algorithm. Spiders are slightly faster then the bug.
One can only travel on the edges.
Can the spiders always catch the bug?
No, because this reduces to NP complete problem.
No. There is no deterministic solution. It is not NP complete.
Yes, because it can be reduced to a simple loop with one spider
chasing the bug and the spider is faster than the bug.
It is not possible to tell since we do not know how slow the
bug is as compared to spiders.
Yes, if and only if the bug is along any edge that starts with
the vertex from which spiders start.
■ このスレッドは過去ログ倉庫に格納されています