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

 Б)   РЕШЕНИЕ: Идеята е както в flowb1.c,  но сега се извършват по-малко съ-
 бирания  и  проверки.  Да забележим,  че ако flows[i] = 0,  това значи,  че
 просто стойността не е сметната,  т.к. през едно число минава поне един по-
 ток (този,  който започва от него.)  От друга страна да забележим,  че няма
 смисъл да обхождаме поток i и поток i + sum( i ) - те очевидно минават през
 едни и същи числа.  Ще направим следното нещо:  ще изчисляваме  само потоци
 започващи от още ненамерени стойностти и за всяко следващо число през което
 минава,  ще увеличаваме брояча с едно повече от предишното.  Ето един прост
 пример:
 flows[1] = 1, flows[2] = 2, flows[4] = 3,...
 Очевидно през 1 минава само един поток, през 2 минават всички потоци от 1 и
 един нов - поток 2 и т.н.
      И все пак остава проблем: какво ще правим с вливащите се потоци? Отго-
 ворът е логичен, просто ако flows[i] <> 0, за всички числа след i няма нуж-
 да да увеличаваме потоците, т.к. новите потоци са вече отчетени. Самият код
 е кратък и затова  лесен за разбиране.  Поогледайте го и ще забележите,  че
 идеята е абсолютно същата като в flowb1.c, но благодарение на оптимизацията,
 сега O(n) е много по-точно приближение.
                                                                Мартин Русков
*/

#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;
}

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

  for( i = 1; flows[i] <= N; i++ )
    if( !flows[i] )
      for( j = i, k = 0; flows[j] <= N; j += sum( j ) )
        if( !flows[j] )
          flows[j] = ++k;
        else
          flows[j] += k;

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

  return 0;
}