INFOMAN брой 17

/*
 ЗМС'2000
 Задача E: Средна дума
 Задача: Да се намери средната лексикографски дума от много дълъг спискък с
 думи (<= 1000000), като се знае, че различните думи са <= 1000 (в последния
 тест на журито имаше около 1500).
 
 Пълно условие: В учебника по Дискретна математика на професор Маньо Красев
 има много думи,може и да са милион.Но тъй като тематиката е доста ограничена
 и нещата се въртят все около едни и същи обекти, не е трудно да се види, че
 различните думи са сравнително малко-не повече от хиляда.Поради вродената си
 любов към сортирането  професорът обича да си представя всички думи от учеб-
 ника сортирани в лексикографски ред. Веднаж, като си представял огромния ма-
 сив от думи сортиран,  му хрумнал следният,  по-скоро глупав отколкото важен
 въпрос: да допуснем, че всички думи в учебника са нечетен брой, тогава някоя
 от думите ще заеме  средно положение,  т.е преди нея в  сортирания списък ще
 има точно толкова думи, колкото и след нея. Коя ли е средната дума в учебни-
 ка? За съжаление нито паметта, нито бързодействието на старичкия компютър на
 професора му  позволяват да сортира  всички думи от  учебника и да  задоволи
 научното си любопитство.
      Не бихте ли  помогнали на  професора като  напишете  програма TEXT.EXE,
 която  въвежда думите от учебника и намира средната дума.  Входът се чете от
 текстов файл TEXT.INP,  всеки ред от който може  да съдържа произволен  брой
 думи,  разделени с по една запетая,  като думите са нечетен брой. Никоя дума
 не е по-дълга от 20 букви. В единствения ред на изходния файл TEXT.OUT прог-
 рамататрябва да изведе намерената средна дума.

 Пример
 TEXT.INP
 азбука е множество от букви дума е всяка крайна редица от
 букви дума която няма букви е празна дума всяко множество
 от думи на азбука е език

 TEXT.OUT
 е

 Решение:
      От условието става ясно,  че не е възможно да  се сортират всички думи.
 Ще приложим следната оптимизация: ще преброим колко пъти се среща всяка дума
 и тогава във  въображаем масив ще ги сортираме.  Т.е. трябва да намерим след
 това коя дума е средна (от ограничението за най-много 1000 различни думи ста-
 ва ясно,  че паметта ще ни стигне.)  Това става като просто добавяме броя на
 всяка следваща лексикографски дума.  Когато общият брой достигне половината,
 средната дума е намерена.
      Сега да видим как броим думите.  Четем от входа дума по дума и ако вече
 сме срещали такава дума увеличаваме брояча, ако пък не сме, просто я добавя-
 ме сред срещнатите думи и инициализираме брояча на 1. За да бъде това по-бър-
 зо,при търсене на мястото къде да вмъкнем думата,използваме двоично търсене.

 Забележка:
     За по-удобно,задачата приема за вход собствения си сорс (т.е. този файл).
 Той не изпълнява условието думите да се повтарят многократно, но все пак ал-
 горитъмът може да се приложи и върху него.
     Мартин Русков (сорсът е писан от Мартин Вълканов по време на самото ЗМС)
*/

#include <stdio.h>
#include <string.h>

typedef struct { char name[21]; long int count; } t_word;

#define MAX 1000

t_word words[MAX];
int word_cnt = 0;

void insert_word( char * word )
{
   int l = 0, r = word_cnt;
   int x = 0;
   int i;
   int comp;

   if ( word_cnt == 0 )
   {
      word_cnt++;
      strcpy( words[0].name, word );
      words[0].count = 1;
      return;
   }

   comp = strcmp( word, words[0].name );
   if ( comp < 0 )
   {
      for ( i = word_cnt; i > 0; i-- )
      {
         words[i+1].count = words[i].count;
         strcpy( words[i+1].name, words[i].name );
      }

      word_cnt++;
      strcpy( words[0].name, word );
      words[0].count = 1;

      return;
   }
   else
   if ( comp == 0 )
   {
      words[0].count++;
      return;
   }

   for (;;)
   {
      x = (l + r) / 2;
      comp = strcmp( word, words[x].name );

      if ( comp < 0 )
      {
         r = x;
      }
      else
      if ( comp == 0 )
      {
         words[x].count++; return;
      }
      else
      {
         l = x;
      }

      if ( l == r ) break;
      if ( l + 1 == r ) break;
   }

   for ( i = word_cnt; i > l; i-- )
   {
      words[i+1].count = words[i].count;
      strcpy( words[i+1].name, words[i].name );
   }

   word_cnt++;
   strcpy( words[l+1].name, word );
   words[l+1].count = 1;
}

int main( void )
{
   char word[21];
   long int i, word_count, half_count, br;

   freopen( "text.c", "r", stdin );

   word_count = 0;
   while ( scanf( "%s", word ) != EOF && word_count < MAX)
   {
      insert_word( word );
      word_count++;
   }

   half_count = ( word_count / 2 ) + ( word_count % 2 );
   br = 0;
   i = 0;

   for (;;)
   {
      br += words[i].count;
      if ( br >= half_count ) break;
      i++;
   }

   printf( "%s", words[i].name );

   return 0;
}