Условие задачи:
В некотором государстве действует N фирм, конкурирующих между собой. У каждой фирмы есть некоторая прибыль в год, равная V[i] американских рублей. У царя есть любимые фирмы, а есть нелюбимые. Соответственно, налог для всех фирм разный и назначается царем в индивидуальном порядке. Налог на i-ую фирму равен p[i] процентов.
Собиратели статистики решили посчитать, с какой фирмы в государственную казну идет наибольший доход (в казну идут все налоги). К сожалению, они не учили в детстве ни математику, ни информатику (так что учитесь, дети!), и их задача резко осложняется.
Входные данные
Во входном файле INPUT.TXT сначала записано число N - число фирм (0 < N ≤ 100). Далее идет N целых неотрицательных чисел, не превышающих 154 - доходы фирм, а затем еще N целых чисел от 0 до 100 - налоги фирм в процентах.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число - номер фирмы, от которой государство получает наибольший налог. Если таких фирм несколько, выведите фирму с наименьшим номером.
Что по сути надо сделать? Вывести индекс максимального элемента, который равен a * (b/100)
.
Первое, что можно сделать: допустим мы выстроили прибыль по возрастанию.
a_1 * (b_1/100) < a_2 * (b_2/100) < ... < a_n * (b_n/100) | *100 (домножим на 100 данное неравенство)
a_1 * b_1 < a_2 * b_2 < a_3 * b_3 < ... < a_n * b_n
Таким образом, нам надо найти индекс n такой, что a_n * b_n = max(a_1 * b_1, a_2 * b_2, ... , a_n * b_n)
, и тогда даже переменные с плавающей точкой не придется использовать.
Мое решение:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
int mxcnt = -1; //переменная для записи максимального значения a_k * b_k
int id = -1; //запись индекса для этого значения.
for (int i = 0; i < t; i++)
{
int a, b;
cin >> a >> b;
if (a * b > mxcnt)
{
mxcnt = a*b;
id = i+1;
}
}
cout << id;
}
Но в одних из начальных тестов, мое решение дает неверный ответ. В чем может быть проблема? Моя идея сама по себе неверная? Или программа спотыкается на каких-то частных случаях?