Ідеї розв'язання задач першого туру у вищій лізі

Задача 1.
  Нехай в числі n цифр. Позначимо c[i] - i-та цифра.
  Переглядаємо всі цифри з 1 до (n div 2)-ої. На кожному кроці треба урівняти i-ту і (n-i+1)-шу цифри.
  Якщо c[i]>c[n-i+1], то оптимальним варіантом буде c[n-i+1]:=c[i].
  Якщо ж c[i]<c[n-i+1], то таке присвоєння приведе до числа,меншого за вхідне.
  В такому випадку доцільніше спочатку збільшити c[n-i] на 1, а потім c[n-i+1]:=c[i].

Задача 2.
  Позначимо F(n,k) - кількість перестановок з n чисел, в яких рівно k інверсій.
  Якщо k<0, то F(n,k)=0; F(0,0)=1. Для всіх інших n, k кількість перестановок обчислюється за рекурентною формулою F(n,k) = F(n-1,k)+F(n-1,k-1)+..+F(n-1,k-n+1). (Якщо на n-ій позиції стоїть цифра i, то вона утворює n-i інверсій, тому на перших n-1 чисел залишаться k-n+i інверсій, 1<=i<=n).
  Маючи цю формулу можна послідовно заповнити матрицю, яка відповідає функції F(n,k).

Задача 3.
  Ця задача зводиться до задачі знаходження максимального потоку в мережі, якщо систему міст і доріг розглянути як граф, поставити пропускні здатності всіх доріг рівними 1, початкове місто - витік, кінцеве місто - стік.
  Алгоритми знаходження максимального потоку можна знайти в книжках, присвячених олімпіадному програмуванню (зокрема алгоритм Форда-Фалкерсона).