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

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

Существует два конкурирующих магазина пончиков.

Первый магазин продает пончики в розницу: каждый пончик стоит a долларов.

Второй магазин продает пончики оптом: коробка из b пончиков стоит c долларов. То есть если вы хотите купить x пончиков в этом магазине, то вам придется купить минимальное количество коробок такое, что суммарное количество пончиков больше или равно x.

Код 

for tc in range(int(input())):
	a, b, c = map(int, input().split())
	print(1 if a < c else -1, end=" ")
	print(b if c < a * b else -1)

         

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


Код 

#include<bits/stdc++.h>
using namespace std;

int main(){
	int t;
	cin>>t;
	while(t--){
		long long  a,b,c;
		cin>>a>>b>>c;
		if(c<=a) cout<<-1<<" ";
		else cout<<1<<" ";
		if(a*b<=c) cout<<-1<<endl;
		else cout<<b<<endl;
	} 
}

         

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


Пояснение к задаче

Для начала заметим, что если существует значение для второго магазина, то существует и такое значение, которое делится на b. Любой x можно округлить наверх до ближайшего множителя b. Это не изменит цену во втором магазине и только увеличит цену в первом.

Также можно догадаться, что если существует значение для первого магазина, то значение с 1 по модулю b тоже существует (ровно 1 пончик помимо какого-то количества полных коробок). По той же логике — второму магазину нужна целая новая коробка, а первому магазину нужен только один пончик.

Посмотрим на минимальные значения двух этих типов:

x=b: это значение подходит для второго магазина, если одна коробка дешевле, чем b пончиков в первом магазине. В противном случае, сколько бы коробок мы не взяли, они никогда не будут дешевле, чем соответствующее количество пончиков.
x=1: это значение подходит для первого магазина, если один пончик дешевле, чем одна коробка во втором магазине. Применим ту же идею — в противном случае ни одно значение не подходит для первого магазина.
Асимптотика решения: O(1) на набор входных данных.


Комментарии

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



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp