Решение задачи Морковные торты с Codeforces

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


В одной из игр Playrix печь выпекает за t минут k морковных тортов, причем все торты выпекаются одновременно по прошествии t минут с начала выпекания. Аркадию нужно получить хотя бы n тортов для выполнения задания, а сейчас у него нет ни одного, зато есть сколько угодно ингредиентов и одна печь. Кроме того, Аркадий может построить еще одну такую же печь для ускорения процесса, это займет d минут. Во время постройки новой печи выпекать торты может только старая печь, после конца постройки обе печи выпекают параллельно. Аркадий не может построить более одной новой печи.

Определите, целесообразно ли строительство второй печи, то есть уменьшит это минимальное время получения n тортов, или нет. Если время приготовления без второй печи равно времени приготовления тортов с ней, то строительство печи нецелесообразно.

Код

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,t,d,k,i,j,m;
	cin >> n >> t >> k >> d;
	if(t * ((n + k - 1) / k) > d + t) 
        cout << "YES";
	else 
        cout << "NO";
}

         

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


Одно из возможных решений — промоделировать описанный процесс. Для этого нужно поддержать две переменные t 1 и t 2. В них нужно хранить время, в которое освободится каждая их печей. Изначально t 1 равно 0, а t 2 равно d.

После моделирования мы получим время, за которое можно приготовить n тортов с помощью 2 печей (оно равно максимуму из t 1 и t 2). Остаётся сравнить это время со значением (n + k - 1) / k·t — время, за которое можно приготовить n тортов с помощью одной печи.


Комментарии

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