Glass Measurement CodeChef Solution

Problem -Glass Measurement 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.

Glass Measurement CodeChef Solution in C++14

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<sstream>
#include<set>
#include<climits>
#define gc getchar
#define f first
#define s second
#define D(x) ll x = scan()
#define TEST ll T = scan(); while(T--)
#define rep(i, n) for(ll i=0; i<n; i++)
using namespace std;
typedef long long LL;
LL scan()
{
	bool minus = false;
	LL result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}
#define MAXV 100001
#define INF 10000000000000LL
 
using namespace std;
 
int num[11];
int N;
LL frob[MAXV];
 
inline void calc_frobenius()
{
	for(int i=0; i<num[0]; i++){frob[i]=INF;}
	frob[0] = 0;
	
	for(int i=1;i<N;i++)
	{
		LL n;
		int p;
		
		int d = __gcd(num[0],num[i]);
		int t = num[0]/d;
		
		for(int r=0;r<d;r++)
		{
			LL n = INF;
			for(int q=r; q<=r+(num[0]-d); q+=d)
			n = min(n,frob[q]);
			
			if(n < INF)
			{
				for(int steps=0;steps<t;steps++)
				{
					n = n+num[i];
					p = n%num[0];
					n = min(n,frob[p]);
					frob[p] = n;
				}
			}
		}
	}
}
int main()
{
	//freopen("in.txt", "r", stdin);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&N);
		for(int i=0;i<N;i++){scanf("%d",&num[i]);}
		
		sort(num,num+N);
	 calc_frobenius();
	 LL M=-1;
	 for(int i=0; i<num[0]; i++){
             M=max(M,frob[i]);
             }
		printf("%lld\n",M-num[0]);
		
		int Q;
		scanf("%d",&Q);
		LL a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		
		int ret = 0;
		for(int q=1;q<=Q;q++)
		{	
			LL x = (a*q + b)%c;
				int p = x%num[0];
	            if(x>=frob[p]){
                                ret++;
                                }
             }
		printf("%d %d\n",Q-ret,ret);
	}
	return 0;
}

Glass Measurement CodeChef Solution in C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define siz 100100
 
typedef struct {
int n, x;
}int64;
 
int o[siz+1], p;
int64 h[siz+1];
 
int A(const void *a, const void *b)
{
int p=*(int*)a-*(int*)b;
if(p<0)return -1;
return p>0;
}
 
void B()
{
int i=2, t=h[p].x;
for(p--; i<=p; i<<=1)
	if(h[i+=(i+1<=p&&h[i+1].x<h[i].x)].x<t)
		{
		o[h[i].n]=i/2;
		h[i/2]=h[i];
		}
	else
		break;
h[o[h[p+1].n]=i/2]=h[p+1];
}
 
void C(int n)
{
int64 t=h[n];
for(;n>1; n>>=1)
	if(t.x<h[n/2].x)
		{
		o[h[n/2].n]=n;
		h[n]=h[n/2];
		}
	else
		break;
h[o[t.n]=n]=t;
}
 
main()
{
int fall, i, q, n, d, r, x[10], m[siz];
long long a, b, c, v;
int64 t;
for(scanf("%d",&fall); fall--; printf("%d %d\n",q-d,d))
	{
	for(i=!scanf("%d",&n); i<n; scanf("%d",x+i++));
	qsort(x,n,sizeof(int),A);
	for(i=o[h[1].n=h[1].x=0]=!!scanf("%d %lld %lld %lld",&q,&a,&b,&c); i<x[0]; m[i]=h[o[i]=(h[i+1].n=i)+1].x=INT_MAX,i++);
	for(p=x[0]; p&&h[1].x<INT_MAX;)
		{
		t=h[1];
		B();
		for(m[t.n]=t.x+!(i=1); i<n; i++)
			if(h[o[r=(t.n+x[i])%x[0]]].x>t.x+(t.n+x[i])/x[0])
				{
				h[o[r]].x=t.x+(t.n+x[i])/x[0];
				C(o[r]);
				}
		}
	if(!p)
		{
		for(i=!(v=-1); i<x[0]; v=((m[i]-(long long)1)*x[0]+i>v)?((m[i]-(long long)1)*x[0]+i):v,i++);
		printf("%lld\n",v);
		}
	else
		puts("-1");
	for(a%=c,b%=c,i=d=0; i<q; d+=((b-=((b+=a)>=c)?c:0)/x[0]>=m[b%x[0]]),i++);
	}
return 0;
}

Glass Measurement CodeChef Solution in JAVA

 
import java.io.*;
import java.util.*;
import static java.lang.Math.*;
 
public class Main
{
    final long inf = Long.MAX_VALUE;
    
    long[] mn = new long[100010];
    int[] x;
    int n, q;
    long a, b, c;
 
    long gcd(long a,long b){ return b==0?a:gcd(b,a%b); }
 
    long doIt()
    {
        long g = x[0];
        for(int i=1;i<n;i++) g = gcd(g,x[i]);
        if(g>1) return -1;
 
        Arrays.sort(x);
        mn[0] = 0;
        for(int i=1;i<x[0];i++) mn[i] = inf;
 
        for(int i=1;i<n;i++)
        {
            g = gcd(x[0],x[i]);
            for(int r=0;r<g;r++)
            {
                long mnn = inf;
                for(int p=r;p<=r+x[0]-g;p+=g) mnn = min(mnn,mn[p]);
                if(mnn<inf) for(int j=0;j<x[0]/g;j++)
                {
                    mnn+=x[i]; int md = (int)(mnn%x[0]);
                    mnn = min(mnn,mn[md]);
                    mn[md]=mnn;
                }
            }
        }
 
        long mx = 0;
        for(int i=0;i<x[0];i++) mx = max( mx, mn[i] );
        if(mx==inf) return -1;
        return mx - x[0];
    }
 
    void solve() throws Exception
    {
        int ntests = readInt();
 
        while(ntests-->0)
        {
            n = readInt();
            x = new int[n];
            for(int i=0;i<n;i++) x[i] = readInt();
 
            pw.println(doIt());
 
            q = readInt();
            a = readLong(); b = readLong(); c = readLong();
            a%=c; b%=c;
            long v = b;
            int can = 0;
            for(int i=0;i<q;i++)
            {
                v+=a; if(v>=c) v-=c;
                if(v >= mn[(int)(v%x[0])] ) can++;
            }
            pw.println((q-can)+" "+can);
        }
 
        pw.flush();
    }
 
    public static void main(String[] args) throws Exception
    {
        new Main().solve();
        System.exit(0);
    }
 
    BufferedReader bf = new BufferedReader( new InputStreamReader(System.in));
    PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer("");
 
    int readInt() throws IOException
    {
        while(!st.hasMoreTokens()) st = new StringTokenizer(bf.readLine());
        return Integer.parseInt(st.nextToken());
    }
 
    long readLong() throws IOException
    {
        while(!st.hasMoreTokens()) st = new StringTokenizer(bf.readLine());
        return Long.parseLong(st.nextToken());
    }
} 

Glass Measurement CodeChef Solution Review:

In our experience, we suggest you solve this Glass Measurement 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 Glass Measurement CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Glass Measurement 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!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn