Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Trip CodeChef Solution
Problem -Trip CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Trip CodeChef Solution in C++17
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define endl '\n'
#define fi first
#define se second
#define ull unsigned ll
#define lld long double
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define Fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int Mod = 1000000007;
void solve() {
int n, m; cin >> n >> m;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
vector<pair<ll, ll>> que;
int step = -1;
ll cost_ans = 0;
int pos = n - 2;
for (int i = n - 2; i >= 0; i--) {
if (v[n - 1] - v[i] <= m) {
que.pb({v[i], 1});
} else break;
if (i == 0) {
step = 1;
}
pos = i;
}
if (step != -1) {
cout << 0 << " " << 1 << endl;
return;
}
reverse(all(que));
for (int i = 1; i < sz(que); i++) {
que[i].se += que[i - 1].se;
que[i].se %= Mod;
}
vector<pair<ll, ll>> tmp_que;
step = 1;
for (int i = pos; i >= 0; i--) {
while (1) {
if (!sz(que)) {
que = tmp_que;
tmp_que.clear();
reverse(all(que));
for (int j = 1; j < sz(que); j++) {
que[j].se += que[j - 1].se;
que[j].se %= Mod;
}
step++;
}
int len = que.back().fi - v[i];
if (len > m) {
que.pop_back();
continue;
}
tmp_que.pb({v[i], que.back().se});
break;
}
}
cout << step << " " << tmp_que.back().se << endl;
}
int main()
{
Fastio;
int tt = 1;
// cin >> tt;
while (tt--) solve();
return 0;
}Trip CodeChef Solution in C++14
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define endl '\n'
#define fi first
#define se second
#define ull unsigned ll
#define lld long double
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define Fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int Mod = 1000000007;
void solve() {
int n, m; cin >> n >> m;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
vector<pair<ll, ll>> que;
int step = -1;
ll cost_ans = 0;
int pos = n - 2;
for (int i = n - 2; i >= 0; i--) {
if (v[n - 1] - v[i] <= m) {
que.pb({v[i], 1});
} else break;
if (i == 0) {
step = 1;
}
pos = i;
}
if (step != -1) {
cout << 0 << " " << 1 << endl;
return;
}
reverse(all(que));
for (int i = 1; i < sz(que); i++) {
que[i].se += que[i - 1].se;
que[i].se %= Mod;
}
vector<pair<ll, ll>> tmp_que;
step = 1;
for (int i = pos; i >= 0; i--) {
while (1) {
if (!sz(que)) {
que = tmp_que;
tmp_que.clear();
reverse(all(que));
for (int j = 1; j < sz(que); j++) {
que[j].se += que[j - 1].se;
que[j].se %= Mod;
}
step++;
}
int len = que.back().fi - v[i];
if (len > m) {
que.pop_back();
continue;
}
tmp_que.pb({v[i], que.back().se});
break;
}
}
cout << step << " " << tmp_que.back().se << endl;
}
int main()
{
Fastio;
int tt = 1;
// cin >> tt;
while (tt--) solve();
return 0;
}Trip CodeChef Solution in PYTH 3
# cook your dish here
from sys import stdin
def nbest(stops, rng):
MVAL = 1000000007
nst = len(stops)
# accumulate options through step patches along path
opt = [0]*nst
opt[0] = 1
inter = 0
lf = 0
lb = 0
brk = stops[0] + rng
for ix in range(1,nst):
if stops[ix] > brk:
inter += 1
f = ix - 1
b = lf + 1
s = f
p = lf
cml = opt[p]
while p > lb:
p -= 1
rch = stops[p] + rng
while rch < stops[s]:
opt[s] = cml
s -= 1
cml = (cml + opt[p])%MVAL
for p in range(b,s+1):
opt[p] = cml
lb = b
lf = f
brk = stops[f] + rng
rch = stops[nst-1] - rng
while stops[lb] < rch:
lb += 1
cml = sum(opt[lb:lf+1])%MVAL
return [ inter, cml ]
# main
n,m = map(int,input().split())
ays = list(int(stdin.readline()) for _ in range(n))
print( *nbest(ays,m) )Trip CodeChef Solution in C
#include<stdio.h>
#include<stdlib.h>
#define MOD 1000000007
#define BUF 4096
int arr[1000000];
int temp1[1000000];
int temp2[1000000];
char ibuf[BUF];
int ipt = BUF;
int readInt()
{
while (ipt < BUF && ibuf[ipt] < '0') ipt++;
if (ipt == BUF)
{
fread(ibuf, 1, BUF, stdin);
ipt = 0;
while (ipt < BUF && ibuf[ipt] < '0') ipt++;
}
int n = 0;
while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
if (ipt == BUF)
{
fread(ibuf, 1, BUF, stdin);
ipt = 0;
while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
}
return n;
}
int main()
{
int m,n,i,j,min,k;
long long count=0;
n=readInt();
m=readInt();
for(i=0;i<n;i++)
arr[i]=readInt();
temp2[0]=1;
j=k=count=0;
for(i=1;i<n;i++)
{
while(arr[i]-arr[j] > m)
count-=temp2[j++];
temp1[i]=temp1[j]+1;
while(temp1[k]==temp1[j])
count+=temp2[k++];
temp2[i]=count%MOD;
}
printf("%d %d\n",temp1[n-1]-1,temp2[n-1]);
return 0;
}Trip CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
class Main
{
static class Patient implements Comparable<Patient> {
int pos;
int illness;
Patient(int pos,int illness) {
this.pos=pos;
this.illness=illness;
}
@Override
public int compareTo(Patient p) {
return p.illness-this.illness;
}
}
/*
class Pair
{
int f,s;
Pair( int f, int s)
{
this.f=f;
this.s=s;
}
}*/
static class Dish{
int id;
int time;
Dish(int a, int b){
this.id = a;
this.time = b;
}
}
static class compare implements Comparator<Dish>{
public int compare(Dish a, Dish b){
if(a.time!=b.time)return a.time - b.time;
else return a.id - b.id;
}
}
static class Pair {
char prefix;
int suffixId;
Pair(char prefix, int suffixId) {
this.prefix = prefix;
this.suffixId = suffixId;
}
@Override
public int hashCode() {
final int prime = 199;
int hash = 0;
hash = prime * prefix + hash;
hash = prime * suffixId + hash;
return hash;
}
@Override
public boolean equals(Object obj) {
if(obj instanceof Pair) {
Pair p2 = (Pair) obj;
return this.prefix == p2.prefix && this.suffixId == p2.suffixId;
}
return false;
}
}
static class Circle{
long x;
long y;
long r;
public Circle(long x, long y, long r) {
this.x = x;
this.y = y;
this.r = r;
}
}
static class Distance{
long shortest;
long largest;
}
/*static class pair implements Comparable<pair>
{
long x;
int y;
pair(long x,int y)
{
this.x=x;
this.y=y;
}
public int compareTo(pair o)
{
return (int)(x-o.x);
}
}
static class Pair
{
long x,y;
Pair(long x, long y)
{
this.x = x;
this.y = y;
}
}
static class PairComparator implements Comparator<Pair>
{
public long compare(Pair a, Pair b)
{
//if(a.x==b.x)
return a.y-b.y;
// return a.x-b.x;
}
}
static class Point {
public double x, y;
private static final int MAX = (int) 1e6 + 1;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
public int hashCode() {
return (int)x * MAX + (int)y;
}
public boolean equals(Object ob) {
if(ob instanceof Point) {
Point other = (Point) ob;
return other.x == x && other.y == y;
}
return false;
}
public String toString() {
return "(" + x + ", " + y + ")";
}
}*/
/* static int days4=0;
static int all;
static long phi[]=new long[1000001];
static long ans[]=new long[1000001];
//static int tree[],sum[];
//public static long mod = 1000000007; public static long [][] tempMatrix;
public static long max = (long) Math.pow(10, 9) + 7;
static StringBuilder res = new StringBuilder();
//static Node tree[];
//static int a[];
// static long mod = 998244353;
public static int rootColor=0;
static int MX = (1<<18);
// static boolean primes[]=new boolean[10000001];*/
static double pi = 3.1415926535;
private static final int MAXN = 5000;
/* private static final int MOD = 1000_000_007;
private static Modular modular_nCr = new Modular(MOD);
private static Modular modular = new Modular(MOD);
private static final long[][] nCr = new long[MAXN+5][MAXN+5];
static int[] maxval = new int[1000000];
static int[] minval = new int[1000000];
private static long bruteAns = 1;
static double eps = 1e-7;
static {
nCr[0][0]=1;
for(int i=0;i<=MAXN;i++)
nCr[i][0]=1;
for(int i=1;i<=MAXN;i++){
for(int j=1;j<=i;j++){
nCr[i][j]=(nCr[i-1][j-1]+nCr[i-1][j])%MOD;
}
}
}*/
/*
static { nCr[0][0] = 1;
for (int i = 1; i < MAXN; i++) {
nCr[i][0] = 1;
for (int j = 1; j <= i; j++) {
nCr[i][j] = modular_nCr.add(nCr[i - 1][j - 1], nCr[i - 1][j]);
} }
}
static int arr[] , dp[][][];
// static int n ;
static int final_sum=0;
static int mod=1000000007;
static ArrayList<Integer> graph[];
static boolean vis[];
static int seive[]=new int[1000001];
static int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
static int[] calcPower() {
int[] arr = new int[26];
for (int i = 0; i < 26; i++) {
arr[i] = (int) Math.pow(2, i);
}
return arr;
}
// static int p[] = new int[1000001], size[] = new int[1000001], n, m;
static int bits=32;
static class Trie
{
Trie tree[]=new Trie[2];
int val=0;
public Trie()
{
val=0;
tree[0]=null;tree[1]=null;
}
}
static Trie root;
static void insert(int xor)
{
Trie temp=root;
for(int i=bits-1;i>=0;i--)
{
int v = (xor & (1<<i)) >=1 ? 1 : 0;
if(temp.tree[v]==null)
temp.tree[v]=new Trie();
temp=temp.tree[v];
}
temp.val=xor;
}
static int query(int xor)
{
Trie temp=root;
for(int i=bits-1;i>=0;i--)
{
int v = (xor & (1<<i)) >=1 ? 1 : 0;
if(temp.tree[1-v]!=null)
temp=temp.tree[1-v];
else if(temp.tree[v]!=null)
temp=temp.tree[v];
}
return xor^temp.val;
}
public static int getBit(int n, int pos) {
return (n & (1 << pos)) == 0 ? 0 : 1;
}
private static int n, m, ci, cj;
private static char[][] g;
private static boolean[][] vs;
private static int[] v = new int[]{-1, 0, 1, 0};
private static int[] h = new int[]{0, 1, 0, -1};
private static char[] d = new char[]{'U', 'R', 'D', 'L'};
private static boolean v(int i, int j) {
return (i >= 0 && i < n && j >= 0 && j < m);
}
private static boolean pr(int i, int j) {
return g[i][j] == '*';
}
private static double dh, dl, dr, k;
static int zero = Integer.MAX_VALUE, one = Integer.MAX_VALUE;
static ArrayList<Long> leaf=new ArrayList<>();*/
static int mod=1000000007;
static int MX = 1000001;
static int pr[] = new int[MX];
static boolean cmp[] = new boolean[MX];
static int c = 0;
static void pre(){
for(int x = 2;x<MX;x++){
if(!cmp[x]){
pr[c++] = x;
for(int y = x+x; y<MX; y+=x){
cmp[y] = true;
}
}
}
}
// static final int MAXN = (int) 1e6;
static int spf[] = new int[MAXN];
static ArrayList<Integer> primes = new ArrayList<>();
static final int size = 1000001;
static final long MOD = 1000000007L;
static int n;
static int m;
static int a[] = new int[size];
static int dp[] = new int[size];
static int arr[] = new int[size];
static int stops;
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
// FastReader in = new FastReader(System.in);
StringBuilder sb = new StringBuilder();
FastScanner in=new FastScanner();
// Scanner sc = new Scanner(System.in);
PrintWriter out=new PrintWriter(System.out);
HashMap<Character, Integer> h = new HashMap<Character, Integer>();
// TreeMap<Integer, Integer> h1 = new TreeMap<Integer, Integer>();
// HashMap<Integer, Integer> h2 = new HashMap<Integer, Integer>();
// HashSet<Point> s = new HashSet<Point>();
// HashSet<Double> s2 = new HashSet<Double>();
// HashSet<Double> s3 = new HashSet<Double>();
// HashSet<Character> h2 = new HashSet<Character>();
//long t= in.nextLong();
// long t = in.nextLong();
//DecimalFormat df = new DecimalFormat("#,###,##0.000000");
/* boolean prime[]=new boolean[10000000];
int p[]=new int[10000000];
int k=1;
Arrays.fill(prime, true);
prime[0]=false;
prime[1]=false;for(int i=2;i<10000000;i++)
{
if(!prime[i])
{
p[i]=p[i-1];
continue;
}
p[i]=k; k++;
for(long j=(long)i*i;j<10000000;j+=i)
prime[(int)j]=false;
}
// BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
/* int pri[]=new int[1000005];
int p=2;
List<Integer> list=new ArrayList<>();
while(p*p <=1000005)
{
if(pri[p]==0)
{
for(int i=p*2;i<=1000004;i=i+p)
{
pri[i]=1;
}
list.add(p);
}
p++;
}
//System.out.println(list);*/
// int t = in.nextInt();
// while(t-->0)
{
n = in.nextInt();
m = in.nextInt();
for(int i=0; i<n; i++) {
a[i] = in.nextInt();
}
long count=0;
dp[0]=1;
int j=0;
int k=0;
for(int i=1;i<n;i++) {
while(a[i]-a[j] > m)
count-= dp[j++];
arr[i]= arr[j]+1;
while(arr[k]==arr[j])
count += dp[k++];
dp[i]=(int) (count % MOD);
}
out.printf("%d %d\n",arr[n-1]-1, dp[n-1]);
}
out.close();
}
static void sieveOfEratosthenes(int n) {
boolean prime[] = new boolean[n+1];
for(int i=0;i<n;i++)
prime[i] = true;
for(int p = 2; p*p <= n; p++) {
if(prime[p]) {
for(int i = p*p; i <= n; i += p)
prime[i] = false;
}
}
for(int i = 2; i <= n; i++) {
if(prime[i])
primes.add(i);
}
}
private static long findGCD(long number1, long number2) {
long t;
while ( number2 != 0 ) {
t = number2;
number2 = number1 % number2;
number1 = t;
}
return number1;
}
static class dd
{
long left,right;
dd(long X, long Y)
{
this.left=X;
this.right=Y;
}
}
static Comparator<dd> isu = new Comparator<dd>(){
public int compare(dd X, dd Y)
{
if(X.left<Y.left)
return 1;
else if(X.left>Y.left)
return -1;
else
{
if(X.right<Y.right)
return 1;
else
return -1;
}
}
};
public static long gcd(long a,long b,long n){
if(a==b){
return (power(a,n,mod)+power(b,n,mod))%mod;
}
long res=1l;
long num=a-b;
for(long i=1;i*i<=num;i++){
if(num%i==0){
long temp= (power(a,n,i)+ power(b,n,i))%i;
if(temp==0){
res=Math.max(res,i);
}
temp= (power(a,n,num/i) + power(b,n,num/i))%(num/i);
if(temp==0){
res=Math.max(res,num/i);
}
}
}
return res%mod;
}
public static long power(long a,long n,long d){
long res=1l;
while(n>0){
if(n%2==1){
res =((res%d)*(a%d))%d;
n--;
}else{
a=((a%d)*(a%d))%d;
n=n/2;
}
}
return res%mod;
}
/* static long power(long x,long y) {
long res=1;
x%=m;
while(y>0) {
if(y%2!=0)
res=(res*x)%m;
y=y>>1;
x=(x*x)%m;
}
return res;
}
*/
static long gcd(long a, long b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}
static long nextPower_2 ( long x, long y )
{
long count = 0 ;
while ( y < x )
{count ++ ;
y = y << 1 ;
}
return count ;
}
/*
static long power(long a, long b, long p)
{ long x = 1, y = a;
while (b > 0) {
if (b % 2 == 1) {
x = (x * y);
if (x >= p) x %= p;
}
y = (y * y); if (y >= p) y %= p;
b /= 2;}
return x;
}*/
public static class Modular {
private int MOD;
Modular(int MOD) {
this.MOD = MOD;
}
public long add(long a, long b) {
return (a + b) % MOD;
}
public long sub(long a, long b) {
return (a - b + MOD) % MOD;
}
public long mul(long a, long b) {
return (a * b) % MOD;
}
public long div(long a, long b) {
return mul(a, inverseEuler(b));
} public long power(long a, long b) {
long x = 1, y = a;
while (b > 0) {
if (b % 2 == 1) {
x = (x * y);if (x >= MOD) x %= MOD;
}
y = (y * y);
if (y >= MOD) y %= MOD;
b /= 2;}
return x;
}
public long inverseEuler(long n) {
return power(n, MOD - 2);
}
}
static class FastReader {
byte[] buf = new byte[2048];
int index, total;
InputStream in;FastReader(InputStream is) {
in = is;
} int scan() throws IOException {
if (index >= total) {
index = 0;
total = in.read(buf);
if (total <= 0) { return -1;
}
}
return buf[index++];
}
String next() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder(); for (; c > 32; c = scan()) {
sb.append((char) c);}
return sb.toString();
}String nextLine() throws IOException {
int c;for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder();
for (; c != 10 && c != 13; c = scan()) {
sb.append((char) c);
} return sb.toString();
}char nextChar() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan()) ;
return (char) c;
} int nextInt() throws IOException {
int c, val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan(); }
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}long nextLong() throws IOException {
int c;long val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}
}
static class FastScanner{
BufferedReader br;
StringTokenizer st;
public FastScanner(){br=new BufferedReader(new InputStreamReader(System.in));}
String nextToken(){
while(st==null||!st.hasMoreElements())
try{st=new StringTokenizer(br.readLine());}catch(Exception e){}
return st.nextToken();
}
int nextInt(){return Integer.parseInt(nextToken());}
long nextLong(){return Long.parseLong(nextToken());}
double nextDouble(){return Double.parseDouble(nextToken());}
}
}Trip CodeChef Solution Review:
In our experience, we suggest you solve this Trip CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Trip CodeChef Solution.
Conclusion:
I hope this Trip CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
