Блог пользователя Kanao

Need Help in EDU Binary Search Step2
Автор Kanao, история, 23 месяца назад, По-английски

Can someone help me with Step-2 C: Very Easy Task

Problem Link : https://mirror.codeforces.com/edu/course/2/lesson/6/2/practice/contest/283932/problem/C

My Approach: if the task can be done in T time, then 1(good) else 0 (bad). So, making 1 copy of the original document will take min(x,y) time, and then both copy machines can simultaneously work.

we need to check whether n copies can be made in T time or not, if I am updating T1 = T-min(x,y) and then checking that can I make n-1 copies in T1 time. Then find the first occurrence of 1 using binary search. It is throwing me an error "Wrong Answer on test case 5"

Code

Actual Approach : we need to check whether n-1 copies can be made in T time or not. Then, by using binary search find the first occurrence of 1 as it will be the least time to make n-1 copies, and then adding min(x,y) as it will be the time to make the copy of original.

AC Code

I dont know, where am I making mistake, both logics seems similar to me.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Well, I don't really read about your second AC code but in the first code I assume that you need to add

if (mid < min(x,y)) return false;

I also have the same issue and when I fixed it just got accepted

→ Ответить
  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you explain why?

    → Ответить
    • »
      »
      »
      11 месяцев назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      It seems like the checking function $$$ 1 + \lfloor \frac{{t - \mathrm{min}}}{x} \rfloor + \lfloor \frac{{t - \mathrm{min}}}{y} \rfloor \geq n $$$ should work properly since negative numbers are still <n but if $$$t=min$$$, you will get 1 even though no copies can be made. Then again, I can't see TC5 so take it with grain of salt.

      Ex: $$$1\, 5\, 7$$$

      if $$$t=5$$$, $$$1 + (5 - 5)/5 + (5 - 5)/7 >=1$$$ so the function returns true

      → Ответить
    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It is specifically for the case n = 1

      Because you see that when t < min(x, y), to find the number of copies made, we have to do t = t - min(x, y) (Because the first copy was made at min(x,y))

      When t < min(x, y) in that case t < 0 , so t / x + t / y can come 0 if t < x and t < y and in that we will get answer at t < min(x,y) even though our copy wasn't printed out yet

      You can take any example in the form of 1 x y and you will get where you are getting wrong

      → Ответить
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i need an explaination why i got wa on 5 while ans=0 and it got accepted when the ans=-1 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define endl '\n' 
#define mod 1000000007
void solve()
{
    int n,x,y;cin>>n>>x>>y;
    int w=min(x,y);
    ll l=0,r=1e9,ans=-1;
    n--;
    while(l<=r){
        ll mid=l+(r-l)/2;
        int pages=mid/x+mid/y;
        //cout<<l<<" "<<r<<endl<<"pages"<<pages<<endl;
        if(pages>=n){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<ans+w<<endl;
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    ll test=1;
//cin>>test;
    while(test--)
    {
        solve();
    }
    return 0;
}
→ Ответить