Bakry's blog

By Bakry, history, 7 years ago, In English

I want to Know what's the answer for this Problem And What's the technique to solve with ? http://codeforces.net/contest/842/problem/A

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just make a for loop from l to r, i for example. Then you should check if i / k is between x and y and also if i / k is an integer (people who didnt check this were hacked). If this statement will be true at least once then answer is "YES", otherwise "NO".

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
#include <bits/stdc++.h>
using namespace std;
#define ll long long int

int main()
{
    ll l, r, x, y, k;
    while(cin >> l >> r >> x >> y >> k)
    {
        for(ll i = x; i <= y; i++)
        {
            if(k * i >= l && k * i <= r)
            {
                cout << "YES\n";
                return 0;
            }
        }
        cout << "NO\n";
    }
}

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

A simple linear search in [x, y] (the given range for the cost)

If, for at least one value , i * k (where k is the efficiency required) lies in the range of the experience ie. [l, r], the answer is "YES" otherwise "NO". Time complexity of this solution is O(y - x)

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't learn linear search , is it the reason that I can't solve the problem ?

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Linear search is just loop/search which works in linear time, what to learn here? :D

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Okay , I thought it as binary search that need to learn