impressive_i

Работа с большими файлами (26 задача ЕГЭ)

May 18th, 2021
1,497
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. {В текстовом файле записан набор натуральных чисел, не превышающих 109.
  2. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе
  3. таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле,
  4. и чему равно наибольшее из средних арифметических таких пар. Первая строка
  5. входного файла содержит целое число N — общее количество чисел в наборе.
  6. Каждая из следующих N строк содержит одно число.
  7. В ответе запишите два целых числа:
  8. сначала количество пар, затем наибольшее среднее арифметическое.
  9. Репетитор IT mentor vk.com/itmentor
  10. }
  11.  
  12. // Вывод : 15 и 976339247
  13. program p27;
  14. uses crt, Utils;
  15.  
  16. type TArray = array[1..5000] of integer;
  17.  
  18. var f : text;
  19.     N : integer;
  20.     k : integer;
  21.     t : integer;
  22.     p : integer;
  23.     x : TArray;
  24.     current : integer;
  25.     count_pair : integer;
  26.     max_average : integer;
  27.     average : integer;
  28.     //Для замера времени выполнения
  29.     start_time : integer;
  30.     time_execution : integer;
  31.  
  32. procedure sort(var ar : TArray; N : integer);
  33. var  index_out, index_in, cursor  : integer;
  34.      template : integer;
  35. begin
  36.     for index_out := 1 to N do begin
  37.        cursor := N - index_out;
  38.        for index_in := 1 to cursor do
  39.            if( ar[index_in] > ar[index_in + 1] ) then begin
  40.                template := ar[index_in + 1];
  41.                ar[index_in + 1] := ar[index_in];
  42.                ar[index_in] := template;
  43.            end;
  44.     end;
  45. end;
  46.  
  47. //Бинарный поиск в массиве
  48. function bin_search( ar : TArray; N : integer; element : integer) : boolean;
  49. var middle, index_start, index_end : integer; is_find : boolean;
  50. begin
  51.     is_find := false;
  52.     index_start := 1; index_end := N;
  53.     while( index_start <= index_end ) do begin
  54.         middle := (index_start + index_end) div 2;
  55.         if((element = ar[index_start]) or (element = ar[index_end])) then begin
  56.             is_find := true; break;
  57.         end;
  58.         if( element < ar[middle] ) then
  59.            index_end := middle - 1
  60.         else if ( element > ar[middle] ) then
  61.            index_start := middle + 1
  62.         else begin is_find := true; break; end;
  63.     end;
  64.     result := is_find;
  65. end;
  66.  
  67. begin
  68.     start_time := Milliseconds;
  69.    
  70.     //Считывание N элементов из файла
  71.     Assign(f, '26.txt');  Reset(f); readln(f, N);
  72.     for k := 1 to N do begin
  73.         readln(f, current );
  74.         x[k] := current;
  75.     end;
  76.     Close(f);
  77.    
  78.     // Сортировка полученного массива
  79.     sort(x, N);
  80.  
  81.     max_average := 0;
  82.     count_pair := 0;
  83.     for k := 1 to N do begin
  84.         if( x[k] mod 2 = 0) then
  85.             for t := k + 1 to N do
  86.               if( x[t] <> x[k] ) and ( x[t] mod 2 = 0) then begin
  87.                    average := (x[t] + x[k]) div 2;
  88.                    //Поиск среднего арифметического в наборе
  89.                    if( bin_search(x, N, average) = true ) then
  90.                        begin //если найдено
  91.                            inc(count_pair);
  92.                            if( average > max_average ) then max_average := average;
  93.                            break;
  94.                        end;
  95.               end;
  96.     end;
  97.  
  98.     time_execution := (Milliseconds - start_time) div 1000;
  99.  
  100.     writeln(' Количество пар из четных чисел, ср.ариф. которых есть в наборе: ', count_pair);
  101.     writeln(' Наибольшее среднее арифметическое: ', max_average);
  102.     writeln;
  103.     writeln('Время выполнения = ', time_execution div 60,' мин ', time_execution mod 60,' сек');
  104. end.
RAW Paste Data