PROBLEM LINK:
Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Cakewalk
PREREQUISITES:
Basic math
PROBLEM:
Given temperatures and prices of N coke cans. You want to drink the cheapest coke which quenches your thirst. You know a coke shall quench your thirst if it’s temperature if within the range [L, R]. All these cokes lie at distance M and the normal temperature is K. For every second, if the current temperature of coke is x, it changes as follows.
- If x > K, x reduces by 1.
- If x < K, x increases by 1.
- If x == K, x remains same.
EXPLANATION
It can be seen that we can consider each coke separately. For each coke, we need to determine whether after M seconds, whether it’s temperature is within the acceptable range, and for all cokes, we can take the one with minimum cost. If no coke satisfies, the answer is -1.
Now, what shall be the temperature of coke after M seconds. If Initial temperature is more than K, then every second, the temperature reduces, until it reaches K. Once it reaches K, it remains K. So, the final temperature can be written as max(K, C_i-M)
In other case, temperature increases every second till it reaches K. So, the final temperature can be written as min(K, C_i+M) (as we want to stop as soon as it reaches temperature K).
Hence, we can check for each code whether it is within the range [L, R] and take minimum cost.
TIME COMPLEXITY
Time complexity is O(N) per test case.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n,m,k,l,r;
int main(){
//freopen("00.txt","r",stdin);
//freopen("00o.txt","w",stdout);
T=readIntLn(1,1000);
while(T--){
n=readIntSp(1,100);
m=readIntSp(1,100);
k=readIntSp(-50,50);
l=readIntSp(-50,50);
r=readIntLn(l,50);
int best = 10000000;
for(int i=0;i<n;i++){
int c,p;
c=readIntSp(-50,50);
p=readIntLn(1,1000000);
for(int j=0;j<m;j++){
if(c > k){
c--;
} else if( c< k){
c++;
}
}
if(l <= c && c<= r){
best=min(best,p);
}
}
if(best == 10000000){
cout<<-1<<endl;
} else {
cout<<best<<endl;
}
}
assert(getchar()==-1);
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int c[123456],p[123456];
int main(){
//std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,m,k,l,r;
cin>>n>>m>>k>>l>>r;
int i;
int mini=inf;
rep(i,n){
cin>>c[i]>>p[i];
if(abs(c[i]-k)<=m){
c[i]=k;
}
else if(c[i]>k){
c[i]-=m;
}
else{
c[i]+=m;
}
if(l<=c[i] && c[i]<=r){
mini=min(mini,p[i]);
}
}
if(mini==inf)
mini=-1;
cout<<mini<<endl;
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class COKE{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), m = ni(), k = ni(), l = ni(), r = ni();
int ans = (int)1e8;
for(int i = 0; i< n; i++){
int c = ni(), p = ni();
if(c > k)c = Math.max(c-m, k);
else if(c < k)c = Math.min(c+m, k);
if(l <= c && c <= r)ans = Math.min(ans, p);
}
if(ans > 1e7)ans = -1;
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new COKE().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, if you want to. (even if its same ) . Suggestions are welcomed as always had been.