Header Ads Widget

Chef Drinks Coke | codechef solution

Rajnish Tripathi 23:15

 Chef went to the store in order to buy one can of coke. In the store, they offer 

� cans of coke (numbered 1 through �). For each valid �, the current temperature of the �-th can is �� and its price is ��.

After buying a can of coke, Chef wants to immediately start walking home; when he arrives, he wants to immediately drink the whole can. It takes Chef � minutes to get home from the store.

The ambient temperature outside is �. When a can of coke is outside, its temperature approaches the ambient temperature. Specifically, if its temperature is � at some point in time:

  • if �>�+1, then one minute later, its temperature will be �−1
  • if �<�−1, then one minute later, its temperature will be �+1
  • if �−1≤�≤�+1, then one minute later, its temperature will be �

When Chef drinks coke from a can, he wants its temperature to be between � and � (inclusive). Find the cheapest can for which this condition is satisfied or determine that there is no such can.

Input

  • The first line of the input contains a single integer � denoting the number of test cases. The description of � test cases follows.
  • The first line of each test case contains five space-separated integers �, �, �, � and �.
  • � lines follow. For each � (1≤�≤�), the �-th of these lines contains two space-separated integers �� and ��.

Output

For each test case, print a single line containing one integer — the price of the can Chef should buy, or −1 if it is impossible to buy a can such that Chef's condition is satisfied.

Constraints

  • 1≤�≤1,000
  • 1≤�≤100
  • 1≤�≤100
  • ∣��∣≤50 for each valid �
  • ∣�∣≤50
  • −50≤�≤�≤50
  • 1≤��≤106 for each valid �

Sample 1:

Input
Output
2
3 2 5 4 6
1 6
2 8
8 10
3 5 10 20 30
21 20
22 22
23 23
8
-1

Explanation:

Example case 1: Chef should buy the second can (with price 8), even though the first can is cheaper. If Chef bought the first can, its temperature would be 3 when he got home, and that is outside the range [4,6].

Example case 2: No matter which can Chef buys, when he gets home, its temperature will be less than 20, so there is no suitable can available in the store.

Code(C++):-

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
int solve()
{
int n, m, k, l ,r;
cin >> n >> m >> k >> l >> r;
vector<vector<int>> v;

for(int i = 0; i < n; i++) {
int c, p;
cin >> c >> p;
for(int j = 0; j < m; j++) {
if(c < k-1) c++;
else if(c > k+1) c--;
else c = k;
}
v.push_back({p ,c});
}

sort(v.begin(), v.end());
//bool is = true;
for(auto it : v){
if(it[1] >= l && it[1] <= r){
return it[0];
}
}

return -1;
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll test=1;
cin>>test;
while(test--)
{
cout << solve() << endl;
}
return 0;
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        while(T-->0){
         String[] s=(br.readLine()).split(" ");
         int n=Integer.parseInt(s[0]);
         int m=Integer.parseInt(s[1]);
         int k=Integer.parseInt(s[2]);
         int l=Integer.parseInt(s[3]);
         int r=Integer.parseInt(s[4]);
         int ans=Integer.MAX_VALUE;
         boolean flag=false;
         for(int i=0;i<n;i++){
         s=(br.readLine()).split(" ");
         int c=Integer.parseInt(s[0]);
         int p=Integer.parseInt(s[1]);
         int val=-1;
         if(k-1<=c&&c<=k+1){
         val=k;
         }
         else if(c>k+1){
         val=Math.max(k,c-m);
         }
         else{
         val=Math.min(k,c+m);
         }
         if(val>=l&&val<=r){
         if(ans>p){
         ans=p;
         flag=true;
         }
         }
}
System.out.println(flag?ans:-1);
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-




Tags:

Post a Comment

0 Comments