Getting Points

题面翻译

一个学期共 $n$ 天，每天都会有一节课程，每周第一天会有一次作业，作业可以随时做。

学习课程之后就可以做作业，最多只能做 $2$ 次作业。

Monocarp 在这一学期想要休息最多的天数以使得他能在学期结束之前达到 $p$ 分（休息的话就不能上课和做作业），请问他最多能休息多少天。

题目描述

Monocarp is a student at Berland State University. Due to recent changes in the Berland education system, Monocarp has to study only one subject — programming.

The academic term consists of $ n $ days, and in order not to get expelled, Monocarp has to earn at least $ P $ points during those $ n $ days. There are two ways to earn points — completing practical tasks and attending lessons. For each practical task Monocarp fulfills, he earns $ t $ points, and for each lesson he attends, he earns $ l $ points.

Practical tasks are unlocked “each week” as the term goes on: the first task is unlocked on day $ 1 $ (and can be completed on any day from $ 1 $ to $ n $ ), the second task is unlocked on day $ 8 $ (and can be completed on any day from $ 8 $ to $ n $ ), the third task is unlocked on day $ 15 $ , and so on.

Every day from $ 1 $ to $ n $ , there is a lesson which can be attended by Monocarp. And every day, Monocarp chooses whether to study or to rest the whole day. When Monocarp decides to study, he attends a lesson and can complete no more than $ 2 $ tasks, which are already unlocked and not completed yet. If Monocarp rests the whole day, he skips a lesson and ignores tasks.

Monocarp wants to have as many days off as possible, i. e. he wants to maximize the number of days he rests. Help him calculate the maximum number of days he can rest!

输入格式

The first line contains a single integer $ tc $ ( $ 1 \le tc \le 10^4 $ ) — the number of test cases. The description of the test cases follows.

The only line of each test case contains four integers $ n $ , $ P $ , $ l $ and $ t $ ( $ 1 \le n, l, t \le 10^9 $ ; $ 1 \le P \le 10^{18} $ ) — the number of days, the minimum total points Monocarp has to earn, the points for attending one lesson and points for completing one task.

It’s guaranteed for each test case that it’s possible not to be expelled if Monocarp will attend all lessons and will complete all tasks.

输出格式

For each test, print one integer — the maximum number of days Monocarp can rest without being expelled from University.

样例 #1

样例输入 #1

5
1 5 5 2
14 3000000000 1000000000 500000000
100 20 1 10
8 120 10 20
42 280 13 37

样例输出 #1

0
12
99
0
37

提示

In the first test case, the term lasts for $ 1 $ day, so Monocarp should attend at day $ 1 $ . Since attending one lesson already gives $ 5 $ points ( $ 5 \ge P $ ), so it doesn’t matter, will Monocarp complete the task or not.

In the second test case, Monocarp can, for example, study at days $ 8 $ and $ 9 $ : at day $ 8 $ he will attend a lesson for $ 10^9 $ points and complete two tasks for another $ 5 \cdot 10^8 + 5 \cdot 10^8 $ points. And at day $ 9 $ he only attends a lesson for another $ 10^9 $ points.

In the third test case, Monocarp can, for example, study at day $ 42 $ : attending a lesson gives him $ 1 $ point and solving $ 2 $ out of $ 6 $ available tasks gives him another $ 2 \cdot 10 $ points.

In the fourth test case, Monocarp has to attend all lessons and complete all tasks to get $ 8 \cdot 10 + 2 \cdot 20 = 120 $ points.

In the fifth test case, Monocarp can, for example, study at days: $ 8 $ — one lesson and first and second tasks; $ 15 $ — one lesson and the third task; $ 22 $ — one lesson and the fourth task; $ 29 $ — one lesson and the fifth task; $ 36 $ — one lesson and the sixth task.

直接二分可以避免太多情况

在二分天数时，一天可以完成两个实践，直接把天数*2，就是实践最多可以完成多少，和实践作业数量取一个min值就行了

#include <iostream>
//#include<bits/stdc++.h>
#include <string>
#include <cstring>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <deque>
#include <iomanip>
#include <queue>

#include <unordered_map>
//#define x first
//#define y second
#define int   long long
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
#define endl '\n'
#define buff ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
typedef unsigned long long ULL;
//priority_queue<int, vector<int>, less<int> >dg;
//priority_queue<int, vector<int>, greater<int> >xg;
//int dx[] = { -1,-1,-1,0,0,1,1,1 };
//int dy[] = { -1,0,1,-1,1,-1,0,1 };
//#define INF 0x3f3f3f3f
//ceil函数可以把x上取整。(加取整）(int)
//floor函数可以把x下取整。
//round函数可以把x四舍五入。
//数字分为整型与浮点型，则对应的函数是stoi（）、stod（）、stof（）等。
//unordered_map<long, long> mp;
//string -> int:stoi()
const int N = 2e5 + 10;
int n, p, l, t;
int cheak(int x)
{
    int xx = n - x;
    int zy = xx * l;
    int ok;
    double sx = 1.0 * n / 7;
    int sz = n / 7;
    if (sz == sx) ok = sz;
    else ok = sz + 1;


    int sj = min(ok, xx * 2) * t;

    if (sj + zy >= p) return 1;
    else return 0;
}
void solve()
{
;
    cin >> n >> p >> l >> t;
    int l = 0, r = n;
    int daan = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (cheak(mid))
        {
            daan = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << daan << '\n';
}
signed main()
{
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}
/*string bin2(int n) {
    string str = "";
    while (n != 0) {
        str = to_string(n % 2) + str;
        n = n / 2;
    }
    return str;
}
int bin10(string n)
{

    int sum=0;
    for (int i = 0; i < n.size(); i++)
    {
        if (n[i] == '1')
        {
            int j = pow(2, n.size() - i - 1);
            sum += j;
        }
    }
    return sum;
}*/