Решение олимпиадной задачи — Налоги

  • В этой теме 0 ответов, 1 участник, последнее обновление 4 месяца, 3 недели назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6458
      @admin
      StudLance.ru

      Условие задачи взято с сайта acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 20%):

      В некотором государстве действует N фирм, конкурирующих между собой. У каждой фирмы есть некоторая прибыль в год, равная V[i] американских рублей. У царя есть любимые фирмы, а есть нелюбимые. Соответственно, налог для всех фирм разный и назначается царем в индивидуальном порядке. Налог на i-ую фирму равен p[i] процентов.

      Собиратели статистики решили посчитать, с какой фирмы в государственную казну идет наибольший доход (в казну идут все налоги). К сожалению, они не учили в детстве ни математику, ни информатику (так что учитесь, дети!), и их задача резко осложняется.

      Помогите им в этой нелегкой задаче.

      Входные данные

      Во входном файле INPUT.TXT сначала записано число N — число фирм (0 < N ≤ 100). Далее идет N целых неотрицательных чисел, не превышающих 154 — доходы фирм, а затем еще N целых чисел от 0 до 100 — налоги фирм в процентах.

      Выходные данные

      В выходной файл OUTPUT.TXT выведите одно число — номер фирмы, от которой государство получает наибольший налог. Если таких фирм несколько, выведите фирму с наименьшим номером.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 1
      1
      1
      1
      2 2
      1 2
      3 2
      2
      3 3
      100 1 50
      0 100 3
      3

      Разбор решения задачи

      Иными словами — дано 2 массива X, и Y, состоящих из N элементов. Нужно найти максимальное значение X[i]*Y[i] и индекс i будет ответом.

      Задача чуть усложняется из-за неудобного формата входных данных. Сначала идет целиком массив X, а затем — Y, поэтому обойтись без ввода массива X не получится (по крайней мере без бубна). Наиболее простое решение заключается в считывании содержимого файла в два массива и затем поиска максимума:

      #include <fstream>
      #include <vector>
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n;
        ifst >> n;
      
        vector<int> incomes(n), percent(n);
        for (int i = 0; i < n; ++i) {
          ifst >> incomes[i];
        }
        for (int i = 0; i < n; ++i) {
          ifst >> percent[i];
        }
      
        int max_pos = 1;
        int max_tax = incomes[max_pos-1] * percent[max_pos-1];
      
        for (int pos = 2; pos <= n; ++pos) {
          int tax = incomes[pos-1] * percent[pos-1];
      
          if (tax > max_tax) {
            max_tax = tax;
            max_pos = pos;
          }
        }
      
        ofst << max_pos;
      }

      Что тут можно улучшить?:

      1. Завести структуру для Фирмы — код станет понятней.
      2. Использовать алгоритм copy для ввода данных.
      3. не сохранять данные во втором массиве — при считывании процента I-той фирмы можно сразу провести расчет.

      Немного улучшенный вариант:

      #include <fstream>
      #include <vector>
      #include <algorithm>
      #include <iterator>
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n;
        ifst >> n;
      
        vector<int> incomes;
        std::copy_n(istream_iterator<int>(ifst), n, back_inserter(incomes));
      
        size_t max_pos = 0;
        int max_tax = 0;
      
        for (size_t i = 0; i < n; ++i) {
          int percent;
          ifst >> percent;
      
          int tax = incomes[i] * percent;
      
          if (tax > max_tax) {
            max_tax = tax;
            max_pos = i;
          }
        }
      
        ofst << max_pos+1;
      }

      StudLance.ru

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