Выборы жрецов

      Комментарии к записи Выборы жрецов отключены

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 4 нед., 1 день назад.

  • Автор
    Сообщения
  • #3335

    Условие задачи взято с acmp.ru:

    (Время: 1 сек. Память: 16 Мб Сложность: 28%)

    В стране Олимпиадии снова выборы.
    Страна состоит из маленьких графств. Графства объединяются в конфедерации. Каждая конфедерация раз в год выбирает себе покровителя – одного из 200 жрецов. Этот ритуал называется Великими Перевыборами Жрецов и выглядит так: конфедерации одновременно подают заявления (одно от конфедерации) в Совет Жрецов о том, кого они хотели бы видеть своим покровителем (если заявление не подано, то считают, что конфедерация хочет оставить себе того же покровителя). После этого все заявки удовлетворяются. Если несколько конфедераций выбирают одного и того же Жреца, то они навсегда объединяются в одну. Таким образом, каждый Жрец всегда является покровителем не более чем одной конфедерации. Требуется написать программу, позволяющую Совету Жрецов выяснить номер Жреца-покровителя каждого графства после Великих Перевыборов. В Совете все графства занумерованы (начиная с 1). Все Жрецы занумерованы числами от 1 до 200 (некоторые из них сейчас могут не быть ничьими покровителями).

    Входные данные:
    Во входном файле INPUT.TXT записано число N – количество графств в стране (1<=N<=5000) – и далее для каждого графства записан номер Жреца-покровителя конфедерации, в которую оно входит (графства считаются по порядку их номеров). Затем указаны заявления от конфедераций. Сначала записано число M – количество поданных заявлений, а затем M пар чисел (1< =M<=200): первое число – номер текущего Жреца-покровителя, второе – номер желаемого Жреца-покровителя. Все числа во входном файле разделяются пробелами и (или) символами перевода строки.

    Выходные данные:
    В выходной файл OUTPUT.TXT вывести для каждого графства одно число – номер его Жреца-покровителя после Великих Перевыборов. Сначала – для первого графства, затем – для второго и т.д.

    Описание алгоритма решения задачи

    Блок-схема алгоритма решения задачи:

    После начала в первом блоке (параллелограмм) осуществляется построчный ввод из первых трех строк текстового файла input.txt таких значений, как N – кол-во графств, номера Жрецов-покровителей и M – число поданных заявлений.
    Затем во втором блоке (прямоугольник) осуществляется создание целочисленного массива (posle_viborov) с размерностью, равной считанному из файла числу N (кол-во графств). Созданный массив имеет нулевые значения.

    Далее необходимо считать M – пар чисел из файла input.txt. Каждая пара записана в отдельной строке файла, количество строк, которые необходимо считать представлено числом М. С каждой парой поочередно необходимо произвести дополнительные манипуляции, это реализовано в виде цикла «для i = 0,…,M» с вложенными в него дополнительными операциями. На каждой итерации цикла осуществляется чтение i-ой пары чисел(параллелограмм) из строки файла input.txt. После чтения текущей пары чисел необходимо сравнить первое число из пары с номерами Жрецов покровителей и в случае совпадения заменить номер Жреца покровителя текущего графства на второе число из текущей пары. Это осуществляется с помощью цикла «для j = 0,…,N» где N – кол-во графств. В каждой итерации этого цикла реализуется логический блок(ромб) проверяющий истинность условия совпадения первого числа из текущей пары чисел с номером j–ого Жреца, и в случае совпадения (положительного исхода «ДА») вызывается блок(прямоугольник) реализующий присвоение по найденному номеру Жреца, значения второго числа из текущей пары чисел, это значение присваивается дублирующему (с нулевыми значениями) целочисленному массиву posle_viborov[j].

    Так как в предыдущих циклах значения записывались в новый массив (нулевой), то возможно некоторые значения остались неизменными и равными нулю. Соответственно необходимо на них место записать значения из исходных номеров Жрецов покровителей. Поэтому после того, как первые два цикла завершаются, открывается новый цикл «для i = 0,…,N» где N – кол-во графств в новом(дублирующем массиве). Для каждой итерации этого цикла проверяется условие(ромб) соответствия элементов дублирующего массива «posle_viborov[i]» нулю, и в случае их нулевого значения блок операций(прямоугольник) присваивает текущему элементу массива «posle_viborov[i]» исходный номер соответствующего i-го Жреца. Иначе, блок операций пропускается.

    Во время выполнения цикла так же осуществляется запись полученного (дублирующего) массива в файл output.txt на каждой итерации, и так как элементы массива в файле необходимо записать через пробел, то в цикле реализуется еще одно условие («i == N -1») проверки на истинность последнего элемента, в случае если текущий элемент массива не последний, то он записывается в файл output.txt через блок вывода(параллелограмм) с добавлением символа пробела, иначе записывается просто один элемент.
    После окончания последнего цикла, программа завершает свою работу. Задача решена. Решение представлено в файле output.txt.

    Исходный код программы, соответствующей алгоритму на языке C#:

    using System;
    using System.IO;
    
    namespace _выборы_жрецов {
      class Program
      { 
        static void Main(string[] args)
        {
          int N = 0;
          int M = 0;
          int[] pari = new int[2];
          
          StreamReader input_file = new StreamReader("input.txt");//
          StreamWriter output_file = new StreamWriter("output.txt");
    
          N = Convert.ToInt32(input_file.ReadLine());
    
          int[] do_viborov = new int[N];
          int[] posle_viborov = new int[N];
    
          do_viborov = Array.ConvertAll<string, int>(input_file.ReadLine().Split(), Convert.ToInt32);
          M = Convert.ToInt32(input_file.ReadLine());
          for (int i = 0; i< M; i++) {
            pari = Array.ConvertAll<string, int>(input_file.ReadLine().Split(), Convert.ToInt32);
            for (int j=0; j< N; j++) {
              if (pari[0] == do_viborov[j]) {
                posle_viborov[j] = pari[1];
              }
            }
          }
          for (int i=0; i< N; i++) {
            if (posle_viborov[i] == 0) {
              posle_viborov[i] = do_viborov[i];
            }
            if ( i== N-1 ) {
              output_file.Write(posle_viborov[i]);
            }
            else {
              output_file.Write(posle_viborov[i]+" ");
            }
          }
        
          input_file.Close();
          output_file.Close();
        }
      }
    }

Для ответа в этой теме необходимо авторизоваться.