h2. 'C. Power Calculus':http://acm.tju.edu.cn/toj/vcontest/showp9268_C.html

Problema ne cere să aflăm numărul minim de operaţii pentru a calcula $x ^n^$ pornind de la $x$ fără a folosi puteri negative. De exemplu $x ^31^$ poate fi calculat cu $6$ operaţii (5 înmulţiri şi o împărţire) $x ^2^ = x × x, x ^4^ = x ^2^ × x ^2^, x ^8^ = x ^4^ × x ^4^ , x ^16^ = x ^8^ × x ^8^ , x ^32^ = x ^16^ × x ^16^ , x ^31^ = x ^32^ ÷ x$

Problema ne cere să aflăm numărul minim de operaţii pentru a calcula $x ^n^$ pornind de la $x$ fără a folosi puteri negative şi făcând înmulţiri cu numere calculate deja. De exemplu $x ^31^$ poate fi calculat cu $7$ înmulţiri:
$x ^2^ = x × x, x ^4^ = x ^2^ × x ^2^, x ^8^ = x ^4^ × x ^4^ , x ^10^ = x ^8^ × x ^2^ , x ^20^ = x ^10^ × x ^10^, x ^30^ = x ^20^ × x ^10^ , x ^31^ = x ^30^ × x$
Acesta poate fi calculat şi cu $6$ operaţii (5 înmulţiri şi o împărţire)
$x ^2^ = x × x, x ^4^ = x ^2^ × x ^2^, x ^8^ = x ^4^ × x ^4^ , x ^16^ = x ^8^ × x ^8^ , x ^32^ = x ^16^ × x ^16^ , x ^31^ = x ^32^ ÷ x$
 
Deşi iniţial pare complicată, problema se rezolvă cu o parcurgere în lăţime. Se observă că nu are sens să calculăm pentru numere mai mari de $2000$. Într-o poziţie din coadă vom reţine toate numerele folosite până la numărul curent. Când dorim să trecem într-o stare nouă trebuie doar să aplicăm operaţiile asupra ultimului număr şi al unui număr calculat pe parcurs.
 
==code(cpp) |
#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;
 
struct drum{
  int lst,sz,cst;
  int fol[32];
};
 
int n=-1,dmin[3005];
 
void ins(queue<drum> &c,drum fr,int nxt) {
  if(nxt<2 || nxt>2000) return;
  drum next=fr;
  ++next.cst;
  if(next.cst==dmin[nxt]) {
    next.fol[++next.sz]=next.lst=nxt;
    c.push(next);
  }
  if(dmin[nxt]>next.cst) {
    dmin[nxt]=next.cst;
    next.fol[++next.sz]=next.lst=nxt;
    c.push(next);
  }
}
 
int main() {
  for(int i=2; i<=1000; ++i) dmin[i]=(1<<30);
  queue<drum> c;
  drum fr; fr.sz=0; fr.lst=1; fr.cst=0; fr.fol[++fr.sz]=1;
  for(c.push(fr);c.size(); c.pop()) {
    fr=c.front();
    for(int i=1; i<=fr.sz; ++i) {
      ins(c,fr,fr.lst+fr.fol[i]);
      ins(c,fr,fr.lst-fr.fol[i]);
    }
  }
  while(1) {
    cin>>n;
    if(n==0) break;
    cout<<dmin[n]<<'\n';
  }
  return 0;
}
==

h2. 'D. Polygons on the Grid':http://acm.tju.edu.cn/toj/vcontest/showp9268_D.html