304 North Cardinal St.
Dorchester Center, MA 02124

# Glass Measurement CodeChef Solution

## 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
{

while(ntests-->0)
{
x = new int[n];

pw.println(doIt());

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);
}

PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer("");

{
return Integer.parseInt(st.nextToken());
}

{
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!