Задачи читателей. День второй. «Цирк».

Всем привет! Вчера к нам в редакцию поступила еще одна задача. На этот раз это задача уже олимпиадного уровня, а именно задача из отборочного тура олимпиады ИТИС.

А вот и условие:

У Эрни Макмиллана есть список тех, с кем разговаривал Долиш. Необходимо вывести их фамилии так, что в начале списка будут находиться те, с кем он больше всего говорил. Если он говорил одинаковое количество времени с несколькими людьми, нужно вначале поместить тех, у кого меньше магических способностей. Если же и магические способности у них одинаковы, то вывести их в том порядке, в котором они находятся в телефонном справочнике.

Формат входных данных

В первой строке входного файла находится натуральное число N, которое не меньше 1 и не превосходит 1000

В каждой из последующих N строк ― разделенные пробелами фамилия человека (строка из заглавных и строчных латинских букв, длиной не более 50 символов), время его разговора с Долишем и его магические способности (неотрицательные целые числа, не превосходящие 106

Формат выходных данных

Вывести список в указанном порядке, по одной фамилии на строку.

Входные данные в файле input.txt Результат работы в файле output.txt
6
Dumbledore 0 1000
Riddle 0 900
Grindelwald 0 900
Potter 1 950
Smith 20 500
JohnDoe 10 0
Smith
JohnDoe
Potter
Grindelwald
Riddle
Dumbledore

 

Итак, начнем.

Тело нашей программы построено на сортировке элементов. Сначала мы сортируем волшебников по времени их разговора. Далее, если время разговора двух волшебников одинаково, то мы сортируем волшебников уже по их силам (не сортируя по времени, ибо время у этих волшебников и так одинаково). И последнее: если и время разговора, и силы двух волшебников одинаковы, то мы сортируем их только по именам (сравнение строк происходит по принципу нахождения символов в таблице ASCII ).

Приведем весь код. Условно его можно разделить на три части: объявление процедур и переменных, считывание входных данных и само тело программы.

// ОБЪЯВЛЕНИЕ ПЕРЕМЕННЫХ
type
  zvonki = record {Задаем запись}
    name: string; 
    time: integer; 
    pow: integer;
  end;

var
  wizard: array [1..10000] of zvonki; {масссив записей}
  I, n, j, tmp, ps, kod: integer; 
  tmp1, s, times: string;

// ПРОЦЕДУРЫ
procedure time_sort(x: integer);{ процедуры обмена значениями двух переменных}
begin
  tmp := wizard[x].time;
  wizard[x].time := wizard[x + 1].time;
  wizard[x + 1].time := tmp;
end;

procedure power_sort(x: integer);
begin
  tmp := wizard[x].pow;
  wizard[x].pow := wizard[x + 1].pow;
  wizard[x + 1].pow := tmp;
end;

procedure names_sort(x: integer);
begin
  tmp1 := wizard[x].name;
  wizard[x].name := wizard[x + 1].name;
  wizard[x + 1].name := tmp1;
end;

begin

  // СЧИТЫВАНИЕ ИЗ ФАЙЛА
  assign(input, 'input.txt'); reset(input); {открываем input.txt}
  assign(output, 'output.txt'); rewrite(output);
  readln(n); {считываем количество волшебников}
  for I := 1 to n do 
  begin
    readln(s);  {считываем всю строку из файла.}
    PS := Pos(' ', s); {функция pos() определяет позицию любого символа в строке. если символов несколько, выводит координату первого}
    wizard[I].name := Copy(S, 1, PS - 1); {Копируем имя без пробела}
    Delete(s, 1, PS); {Удаляем имя с пробелом}
    PS := Pos(' ', S); {Определяем позицию пробела}
    times := Copy(S, 1, PS - 1); {Копируем строку во временную переменную}
    Val(times, wizard[I].time, kod); {Используем стандартную функцию преобразования типов.}
    Delete(S, 1, PS); {Удаляем все лишнее}
    Val(S, wizard[I].pow, kod); {Трансформируем оставшуюся строку в целое число.}
  end;
  // ТЕЛО ПРОГРАММЫ
  for I := 1 to n - 1 do {сортируем пузырьком}
    for j := 1 to n - i do 
    begin
      if wizard[j + 1].time > wizard[j].time then {Если время разговора волшебника больше времени следующего волшебника}
      begin
        time_sort(j); {обмениваем значения времени}
        names_sort(j); {обмениваем значения имен}
        power_sort(j); {обмениваем значения сил. таким образом мы перемещаем волшебника с меньшим временем разговора вниз}
      end;
      if wizard[j + 1].time = wizard[j].time then begin{Если время разговора волшебников одинаково, то}
        if wizard[j + 1].pow < wizard[j].pow then  {Если сила одного меньше силы другого, то}
        begin
          power_sort(j); {обмениваем значения сил}
          names_sort(j); {обмениваем значения имен} 
          // Время у них и так одинаковое, поэтому нет смысла производить обмен времени.
        end 
        else 
        if wizard[j + 1].pow = wizard[j].pow then {Если же сила у них равна} 
          if wizard[j + 1].name < wizard[j].name then {Сравниваем имена.} 
            names_sort(j); {обмениваем значения имен} 
        // Время и сила у них одинаковое, поэтому мы обмениваем только имена.
      end; 
    end; 
    // ВЫВОД
  for i := 1 to n do writeln(output, wizard[i].name); 
  close(input); 
  close(output); 
end.

Вроде бы и все! Давайте только немножко поясним процесс считывания из файла, продемонстрировав картинку. Сначала картинка, потом код.

Цирк
Очень понятная схема.
assign(input, 'input.txt'); reset(input); {открываем input.txt}
  assign(output, 'output.txt'); rewrite(output);
  readln(n); {считываем количество волшебников}
  for I := 1 to n do 
  begin
    readln(s);  {считываем всю строку из файла.}
    PS := Pos(' ', s); {функция pos() определяет позицию любого символа в строке. если символов несколько, выводит координату первого}
    wizard[I].name := Copy(S, 1, PS - 1); {Копируем имя без пробела}
    Delete(s, 1, PS); {Удаляем имя с пробелом}
    PS := Pos(' ', S); {Определяем позицию пробела}
    times := Copy(S, 1, PS - 1); {Копируем строку во временную переменную}
    Val(times, wizard[I].time, kod); {Используем стандартную функцию преобразования типов.}
    Delete(S, 1, PS); {Удаляем все лишнее}
    Val(S, wizard[I].pow, kod); {Трансформируем оставшуюся строку в целое число.}
  end;

Если у вас возникли какие-либо вопросы, то не стесняйтесь и пишите их в комментарии. Не забывайте кликать по кнопочкам!

  • Виталий

    Всем привет. Не сказал бы, что это задача олимпиадного уровня. Ничего особенного в ней нет, и вместо того, что бы писать три одинаковые процедуры по замене местами двух элементов легче было завести и использовать переменную типа zvonki и получилась бы задача о сортировке массива по разным параметрам и все.

    • Игорь

      А вы можете написать своё решение?

  • Daim

    Как думаете у 14 летнего поцана есть шансы все с этого сайта изучить?))пока делал только такое и матем заданьки:
    program prikol;
    var a:integer;
    begin
    write(‘Сколько вам лет:’);
    read(a);
    if a>18
    then write(a,’??? Старпер емаё!!!’)
    else write(a,’? хаха, школоло!!!’);
    end.
    Хех))))

  • ARMOTECH /

    да почему вы не чего не объяснили. какие то типы уже. какие то процедуры. да не фига не ясно. это очень отталкивает от изучения языка