Компјутери - Државен 2013

http://mendo.mk/Task.do?id=374

Здраво, ако може идеи за задачава.. Greedy претпоставувам не поминува ако е државен

BFS веројатно ќе падне на време.
Плус ограничувањата за броевите се до 10^15ta изгледа треба и во стринг да се чуваат.. ако има некој поедноставен начин што не го гледам слободно ургирајте

Јас успеав да ја решам задачата со динамичко програмирање. Бидејќи се работи за огромни броеви, субпроблемите ќе ги чуваме во хеш мапа. Имено, проблемот за наоѓање на минимален број операции од [a,b] можеме да го редуцираме до наоѓање на решението за [a, b / 2] и да додадеме 1 и за [a, (b-2) / 2] + 2, па го наоѓаме минималниот од нив. Ако b e непарен, тогаш решаваме: [a, (b-1) / 2] + 2 и [a, (b-3) / 2] + 3. Броевите комотно влегуваат во unsigned long long, така да не треба да работиме со стрингови.

Фала многу, во меѓувреме ја решив со greedy помина ама повеќе ми се свиѓа ова што си го пишал