На карте «Шестёрочки» у Луки уже есть t бонусных баллов, за которые он может покупать фигурки динозавров. Лука хочет купить всю коллекцию новых динозавров, состоящую из r фигурок. Один динозавр стоит l бонусных баллов.
Баллы в «Шестёрочке» можно получить следующим образом: за покупку первого товара на карту начисляется p1 баллов, за покупку второго товара — p2 баллов, за покупку третьего товара — p3 баллов, за покупку четвёртого товара — снова p1 баллов, за покупку пятого товара — p2 баллов, и так далее. Какое минимальное количество товаров должен купить Лука, чтобы приобрести всю коллекцию динозавров?
Обратите внимание на то, что покупка товаров осуществляется не на бонусные баллы, а за настоящие деньги.
Формат входных данных
Первая строка содержит одно целое число t (0≤t≤1018) — изначальное количество баллов на карте.
Вторая строка содержит одно целое число r (0≤r≤109) — количество динозавров в коллекции.
Третья строка содержит одно целое число l (0≤l≤109) — стоимость одного динозавра.
Четвёртая строка содержит одно целое число p1 (0≤p1≤1017) — количество баллов, начисляемых за покупку.
Пятая строка содержит одно целое число p2 (0≤p2≤1017) — количество баллов, начисляемых за покупку.
Шестая строка содержит одно целое число p3 (0≤p3≤1017) — количество баллов, начисляемых за покупку.
Гарантируется, что p1+p2+p3>0.
Обратите внимание, что входные данные и ответ могут быть достаточно большими, поэтому следует использовать 64-битный тип данных, например, long long в C/C++, long в Java, int64 в Pascal.
Формат выходных данных
Выведите одно число — минимальное количество товаров, которые должен купить Лука, чтобы приобрести всю коллекцию динозавров.
Система оценки
Решения, правильно работающие только для случаев, когда t не превосходит 106, l и r не превосходят 103, а p1, p2 и p3 не превосходят 106, будут оцениваться в 35 баллов.
Решения, правильно работающие только для случаев, когда Луке потребуется покупать по три товара, будут оцениваться в 25 баллов.
Пояснение
Рассмотрим второй пример. Изначально у Луки есть два бонусных балла, при том что в коллекции два динозавра, каждый из которых стоит по пять баллов. Сначала Лука купит первый товар и получит два балла за первую покупку. Далее Лука купит второй товар, получит один бонусный балл, в сумме пять. Далее он купит третий товар и получит ещё три бонусных балла, в итоге восемь баллов. На покупку всех моделей из коллекции до сих пор не хватает, поэтому Луке придётся сделать ещё одну, четвёртую покупку, после чего он получит два балла (потому что за четвёртую покупку начисляется столько же, сколько и за первую). Теперь у Луки десять баллов, на которых он может купить всю коллекцию динозавров. Значит, ответ — четыре.
1 Ответ
Ответ:
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(«unroll-loops»)
#pragma GCC optimize(«Ofast»)
#pragma GCC optimize(«no-stack-protector»)
#pragma GCC target(«sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=na tive»)
#pragma GCC optimize(«fast-math»)
#pragma GCC optimize «-O3»
typedef long long ll;
typedef unsigned long long ull;
typedef ll ld;
#define P pair
typedef P<int, int> Pii;
typedef P<ll, ll> Pll;
typedef P<string, string> Pss;
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define add_fill(a, c) setw(a) << setfill(c)
#define endl ‘\n’
#define slimming(a) a.shrink_to_fit()
#define len(a) (ll)a.size()
#define f first
#define s second
//const ll INF = (ll) (1e9);
// #define MOD 1000000009
#define yes «YES\n»
#define no «NO\n»
#define imp «impossible»
#define pb push_back
#define eb emplace_back
const int alpha = 256;
const char FirstSymbol = ‘a’;
struct pair_hash {
inline std::size_t operator()(const std: air<int,int> & v) const {
return v.first*239+v.second;
}
};
bool bit(ll mask, ll k){
return ((mask >> k)&1);
}
ll get_rand() {
return (rand() << 16) ^ rand();
}
#define PI 3.14159265359
ll func(ll num){
return (num<<1);
}
ll SumBit(ll num1, ll num2) {
ll res = 0, carry = 0;
res = num1^num2;
carry = (num1&num2) << 1;
while (carry) {
ll tmp = res;
res = res^carry;
carry = (tmp&carry) << 1;
}
return res;
}
ll RevNum(ll n) {
return SumBit(~n, 1LL);
}
ll SubNum(ll a, ll b) {
return SumBit(a, RevNum(b));
}
void solve(){
ll t, r, l, p1, p2, p3;
cin >> t >> r >> l;
cin >> p1 >> p2 >> p3;
ll need = r*l — t;
if(need <= 0){
cout << 0;
return;
}
ll lbin = -1, rbin = (need / (p1 + p2 + p3)) + ((need % (p1 + p2 + p3)) > 0);
while(lbin + 1 < rbin){
ll m = (SumBit(lbin, rbin) >> 1);
if((m / 3) * (p1 + p2 + p3)
+ (m % 3 > 0) * p1
+ (m % 3 > 1) * p2
+ (m % 3 > 0) * p3 < need){
lbin = m;
}else{
rbin = m;
}
}
cout << r;
return;
}
int main() {
// freopen(«input.txt», «r», stdin);
// freopen(«output1.txt», «w», stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll t = 1;
// cin >> t;
while(t—)
solve();
return 0;
}