Блог пользователя I_love_PMK

NP problem in Polish OI.
Автор I_love_PMK, 10 лет назад, По-английски

Today I found a problem in XXI Polish OI.

Tourism

But I think it's a NP problem, base on this

I've tried greedy solution, but got 45 points. I'm looking for a solution on Polish OI page but it doesn't have. Someone please help me, thank you.

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

From the original statement:

"The councilor observed that the current road network does not allow for a long journey. Namely, wherever one starts the journey, it is impossible to visit more than 10 towns without passing through some town twice."

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Someone please help :<

→ Ответить