INFOMAN брой 17

/*
                            ПОТОЦИ ОТ ЧИСЛА
                            ---------------

      Числов поток се нарича редица от числа, в които числото n се следва от
 числото, което е n + сумата от неговите цифри. Ако първото от редицата е k,
 тя се нарича поток k.
      Например поток  480 е редицата { 480, 492, 507, 519,... }.
      В природата потоците понякога се срещат и вливат един в друг.  Това се
 случва и на цифровите потоци, когато съдържат едно и също число.
      Например поток 480 се влива в поток 483 в 519 и се влива в поток 507 в
 507, но никога не се влива в поток 481.

 А)   Всеки числов поток евентуално ще се влее в поток 1,  поток 3 или поток
 9. Напишете програма,  която по зададено цяло число n (1<=n<=16384) извежда
 числото, където поток n се влива в един от горните три потока.
 Например:
 Поток: 86
 Резултат: Влива се в поток 1 в 101.

 Б)   Кое е най-малкото число,  което може да бъде намерено в точно 100 циф-
 рови потока.
 Например 8 е най-малкото число в 4 цифрови потока:
 потоци 1, 2, 4 и 8

 Б)   РЕШЕНИЕ: Ще решим задачата за общия случай,  когато търсим най-малкото
 число с N числови потока. Използваният алгоритъм е доста близък до така на-
 реченото решето  на  Ератостен за намиране  на  прости числа (вж. p4.pas от
 бр.2) Идеята е седната: всеки поток (започваме с 1, 2, 3, и т.н.,) увелича-
 ва с 1 елементът flows[i], за всяко число i през което минава. Считаме чис-
 лото N^2 за достатъчно голяма горна граница, която ни гарантира,  че до нея
 има поне едно число с точно N потока.  Решението приключва,  когато намерим
 първото такова число i, че flows[i] = N.  То е минимално, т.к. всички числа
 по-малки от него засега участват в по-малко потоци и няма начин да участват
 в нови. Скоростта на алгоритъма е O(n^2).
                                                                Мартин Русков
*/

#include <stdio.h>

#define N 100

int flows[N * N];

int sum( int x )
{
  int a;

  for( a = 0; x; a += x % 10, x /= 10 );

  return a;
}

void main( void )
{
  int i, j, k;

  for( i = 1; flows[i] <= N && i <= N * N; i++ )
    for( j = i, k = 1; flows[j] <= N && j <= N * N; j += sum( j ) )
      flows[j]++;

  for( i = 1; flows[i] != N; i++ );
  printf( "%d\n", i );
}