Решение задачи Составление контеста с Codeforces

Без пояснения   Просмотров: 29


Дан набор из n задач. Сложность i-й задачи равна ai. Гарантируется, что все сложности различны и заданы в возрастающем порядке.

Вы хотите собрать контест, состоящий из некоторых задач из заданного набора. Другими словами, контест, который вы хотите собрать, должен быть подмножеством задач (не обязательно подряд идущих) из заданного набора. Должно быть соблюдено только одно условие: для каждой задачи, кроме самой сложной (задачи с максимальной сложностью) задачи контеста, должна быть задача со сложностью больше сложности этой задачи, но не больше, чем удвоенная сложность этой задачи. Другими словами, пусть ai1,ai2,…,aip — сложности задач в собранном контесте в возрастающем порядке. Тогда для каждого j от 1 до p−1 должно выполняться aij+1≤aij⋅2. Это означает, что контест, состоящий из одной задачи всегда является корректным.

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

Код

#include<bits/stdc++.h>
using namespace std;
int n,a,l,t=1,m=1;
int main()
{
	cin>>n>>l;
	for(int i=1;i<n;i++)
	{
		cin>>a;
		if(l*2>=a)
			t++;
		else
		{
			t=1;
		}
		m=max(m,t);
		l=a;
	}
	cout<<m;
	return 0;
}

         

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



Комментарии

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