Educational Codeforces Round 82 (Rated for Div.2)B. National Project

庸人自扰 5月前   阅读数 100 0

B. National Project
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Your company was appointed to lay new asphalt on the highway of length n. You know that every day you can either repair one unit of the highway (lay new asphalt over one unit of the highway) or skip repairing.

Skipping the repair is necessary because of the climate. The climate in your region is periodical: there are g days when the climate is good and if you lay new asphalt these days it becomes high-quality pavement; after that, the weather during the next b days is bad, and if you lay new asphalt these days it becomes low-quality pavement; again g good days, b bad days and so on.

You can be sure that you start repairing at the start of a good season, in other words, days 1,2,…,g are good.

You don’t really care about the quality of the highway, you just want to make sure that at least half of the highway will have high-quality pavement. For example, if the n=5 then at least 3 units of the highway should have high quality; if n=4 then at least 2 units should have high quality.

What is the minimum number of days is needed to finish the repair of the highway?

Input
The first line contains a single integer T (1≤T≤104) — the number of test cases.

Next T lines contain test cases — one per line. Each line contains three integers n, g and b (1≤n,g,b≤109) — the length of the highway and the number of good and bad days respectively.

Output
Print T integers — one per test case. For each test case, print the minimum number of days required to repair the highway if at least half of it should have high quality.

Example
inputCopy
3
5 1 1
8 10 10
1000000 1 1000000
outputCopy
5
8
499999500000
Note
In the first test case, you can just lay new asphalt each day, since days 1,3,5 are good.

In the second test case, you can also lay new asphalt each day, since days 1-8 are good.

题意:要修长度为n的路,天气是好天气g天 坏天气b天 周期性的 好天气修的路质量高 坏天气修的路质量低 每天可以修长度为1的路 也可以不修 问你最少修多少天 才能让整条路超过一半的长度是质量高的

思路
去计算,修n/2+n%2长度的路 最少ans天,然后输出max(n,ans) 即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
 
        ll n,g,b;
        cin>>n>>g>>b;
        ll q=n/2+n%2;
        ll ans;
        if(q%g==0)
        {
            ans=q/g;
            ans=ans*g+(ans-1)*b;
        }
        else
            ans=q/g+1,ans=(ans-1)*(g+b)+q%g;
            cout<<max(n,ans)<<endl;
 
    }
 
    return 0;
}
发布了58 篇原创文章 · 获赞 12 · 访问量 7251

注意:本文归作者所有,未经作者允许,不得转载

全部评论: 0

    我有话说: