Решение задачи Максимизация количества нулей с Codeforces

С пояснением   Просмотров: 283


Задано два массива a и b, каждый состоит из n целых чисел.

Вы хотите создать новый массив c следующим образом: выбрать какое-то вещественное (то есть не обязательно целое) число d, и для каждого i∈[1,n] присвоить ci:=d⋅ai+bi.

Ваша задача — максимизировать количество нулей в массиве c. Чему равен максимально возможный ответ, если вы выберете значение d оптимально?

Код

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

const int N = 200043;

void norm(pair<int, int>& p)
{
	if(p.x < 0)
	{
		p.x *= -1;
		p.y *= -1;
	}
	else if (p.x == 0 && p.y < 0)
	{
		p.y *= -1;
	}
	int d = __gcd(abs(p.x), abs(p.y));
	p.x /= d;
	p.y /= d;
}

map<pair<int, int>, int> m;

int a[N];
int b[N];
int n;

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	for(int i = 0; i < n; i++)
		scanf("%d", &b[i]);
	int ans = 0;
	int cnt0 = 0;
	for(int i = 0; i < n; i++)
	{
		if(a[i] == 0)
		{
			if(b[i] == 0)
				cnt0++;
		}
		else
		{
			pair<int, int> p = make_pair(-b[i], a[i]);
			norm(p);
			m[p]++;
			ans = max(ans, m[p]);
		}
	}
	cout << cnt0 + ans << endl;
}

         

Администратор Photo Автор: Администратор


Код

import math
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
res, d = 0, {}
for a, b in zip(A, B):
    if a != 0:
        gcd = a if b == 0 else math.gcd(a, b)
        key = ((-b/a < 0), abs(b/gcd), abs(a/gcd))
        d[key] = d.get(key, 0) + 1
    elif b == 0:
        res += 1
vals = list(d.values())
if vals:
    print(res + max(vals))
else:
    print(res)

         

Администратор Photo Автор: Администратор


Давайте для каждого индекса i∈[1,n] попробуем найти такое значение d, которое сделает i-й элемент c нулем.

Если ai=0, то ci=bi, и значение d никак не влияет. Поэтому просто проигнорируем этот индекс, а в конце добавим 1 к ответу, если bi=0.

В противном случае надо выбрать d=−biai. Давайте посчитаем требуемую дробь для каждого индекса, и среди всех полученных дробей найдем ту, которая встречается наиболее часто (например, этого можно добиться, сложив все дроби в map).

Надо только научиться правильно сравнивать дроби на равенство, так как числа с плавающей точкой могут быть недостаточно точны. Давайте хранить каждую дробь как пару целых чисел (x,y), где x — числитель, а y — знаменатель. Мы должны нормализовать каждую дробь следующим образом: сначала сократим ее, найдя наибольший общий делитель x и y, а затем поделив оба числа на него. После этого проверим, что числитель неотрицательный, и если числитель не ноль, знаменатель тоже должен быть неотрицательным (можно этого добиться, умножив оба числа на −1).



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться