Решение задачи "Гамбургеры" с Codeforces

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


Поликарп очень любит гамбургеры, особенно приготовленные собственноручно. Поликарп считает, что существует только три достойных ингредиента для приготовления гамбургера: хлеб, колбаса и сыр. Рецепт своего знаменитого «гамбургера от Поликарпа» он записывает в виде строки из букв 'B' (хлеб), 'S' (колбаса) и 'C' (сыр). В рецепте ингредиенты перечисляются снизу вверх, например, рецепт «ВSCBS» обозначает гамбургер в котором снизу вверх идут: хлеб, колбаса, сыр, хлеб и снова колбаса.

На кухне у Поликарпа в наличии n b кусочков хлеба, n s кусочков колбасы и n c кусочков сыра. Кроме того, в магазине неподалеку есть в продаже все три ингредиента по цене: p b рублей за кусок хлеба, p s — за кусок колбасы и p c — за кусочек сыра.

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

Код

#include<bits/stdc++.h>
using namespace std;
long long n[10],i,m,S,q,l,h = (1LL<<41);
string s,b("BSC");
int main()
{
	for(cin >> s; i < s.size();i++){
		long long z = b.find(s[i]);
		n[z]++;
	}
	for(i = 3; i < 10; cin >> n[i++]);
	while(l + 1 < h)
	{
		m = l + h >> 1;
		for(S = i = 0; i < 3; i++)
		if((q = n[i] * m - n[3 + i]) > 0)
		S += q * n[6 + i];
		S > n[9] ? h = m : l = m;
	}
	cout << l;
}

         

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


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

Комментарии

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