# HackerEarth Ratio problem solution

In this HackerEarth Ratio problem solution, There are 2 types of chocolates in Chocoland denoted by A and B.

The cholates are lined up in a queue. You want to satisfy your friends by distributing some number of non-empty contiguous chocolates such that the ratio of a number of type A chocolates to a number of type B chocolates is the same for all the friends. You have to distribute all the chocolates and satisfy a maximum number of friends. Therefore you have to find the maximum number of friends that can be satisfied.

## HackerEarth Ratio problem solution.

`#include<bits/stdc++.h>using namespace std;#define ll long long intll t,n,cnt0,cnt1;vector<pair<ll,ll> >v;string c;int main(){    freopen("input.txt","r",stdin);    freopen("out.txt","w",stdout);    ll i,j,k;    cin>>t;    while(t--)    {        cin>>n;        cnt0=cnt1=0;        v.clear();        for(i=1;i<=n;i++)        {            cin>>j>>c;            if(c=="A")            k=0;            else            k=1;            if(k==0)            cnt0+=j;            else            cnt1+=j;            if(v.size()==0)            {                v.push_back({k,j});            }            else            {                ll lst=v[v.size()-1].first;                if(lst==k)                v[v.size()-1].second+=j;                else                v.push_back({k,j});            }        }        if(cnt0==0||cnt1==0)        {            cout<<max(cnt0,cnt1)<<"\n";        }        else        {            ll cx=0;            ll cy=0;            ll ans=0;            for(i=0;i<v.size();i++)            {                j=v[i].first;                k=v[i].second;                if((cx==0&&cy==0)||(j==0&&cy==0)||(j==1&&cx==0))                {                    if(j==0)                    cx+=k;                    else                    cy+=k;                }                else                {                    if(j==0)                    {                        if((cnt0*cy)%cnt1==0)                        {                            ll req=(cnt0*cy)/cnt1-cx;                            if(req<=k&&req>=0)                            {                                ans++;                                cy=0;                                cx=k-req;                            }                            else                            {                                cx+=k;                            }                        }                        else                        {                            cx+=k;                        }                    }                    else                    {                        if((cnt1*cx)%cnt0==0)                        {                            ll req=(cnt1*cx)/cnt0-cy;                            if(req>=0&&req<=k)                            {                                ans++;                                cx=0;                                cy=k-req;                            }                            else                            {                                cy+=k;                            }                        }                        else                        {                            cy+=k;                        }                    }                }            }            cout<<ans<<"\n";        }    }    return 0;}`

### Second solution

`import java.io.OutputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.io.OutputStream;import java.io.Writer;import java.io.IOException;import java.util.InputMismatchException;import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.InputStream;public class Main {    public static void main(String[] args) {        InputStream inputStream = System.in;        OutputStream outputStream = System.out;        FastScanner in = new FastScanner(inputStream);        FastPrinter out = new FastPrinter(outputStream);        Ration solver = new Ration();        int testCount = Integer.parseInt(in.next());        for (int i = 1; i <= testCount; i++)            solver.solve(i, in, out);        out.close();    }    static class Ration {        public void solve(int testNumber, FastScanner in, FastPrinter out) {            int n = in.nextInt();            if (n < 1 || n > 100000) throw new AssertionError();            int[] a = new int[n];            int[] type = new int[n];            long allA = 0;            long allB = 0;            for (int i = 0; i < n; i++) {                a[i] = in.nextInt();                if (a[i] < 1 || a[i] > 1000000000) throw new AssertionError();                type[i] = "AB".indexOf(in.next());                if (type[i] < 0) throw new AssertionError();                if (type[i] == 0) {                    allA += a[i];                } else {                    allB += a[i];                }            }            if (allA == 0 || allB == 0) {                out.println(allA + allB);                return;            }            long g = MathUtils.gcd(allA, allB);            allA /= g;            allB /= g;            long haveA = 0;            long haveB = 0;            int ans = 0;            for (int i = 0; i < n; i++) {                int add = a[i];                if (type[i] == 0) {                    ans += getAns(allA, allB, haveA, haveB, add);                    haveA += add;                } else {                    ans += getAns(allB, allA, haveB, haveA, add);                    haveB += add;                }            }            out.println(ans);        }        private int getAns(long allA, long allB, long haveA, long haveB, int add) {            if (haveA * allB < allA * haveB && (haveA + add) * allB >= allA * haveB && allA * haveB % allB == 0) {                return 1;            }            return 0;        }    }    static class FastScanner extends BufferedReader {        public FastScanner(InputStream is) {            super(new InputStreamReader(is));        }        public int read() {            try {                int ret = super.read();                return ret;            } catch (IOException e) {                throw new InputMismatchException();            }        }        public String next() {            StringBuilder sb = new StringBuilder();            int c = read();            while (isWhiteSpace(c)) {                c = read();            }            if (c < 0) {                return null;            }            while (c >= 0 && !isWhiteSpace(c)) {                sb.appendCodePoint(c);                c = read();            }            return sb.toString();        }        static boolean isWhiteSpace(int c) {            return c >= 0 && c <= 32;        }        public int nextInt() {            int c = read();            while (isWhiteSpace(c)) {                c = read();            }            int sgn = 1;            if (c == '-') {                sgn = -1;                c = read();            }            int ret = 0;            while (c >= 0 && !isWhiteSpace(c)) {                if (c < '0' || c > '9') {                    throw new NumberFormatException("digit expected " + (char) c                            + " found");                }                ret = ret * 10 + c - '0';                c = read();            }            return ret * sgn;        }        public String readLine() {            try {                return super.readLine();            } catch (IOException e) {                return null;            }        }    }    static class MathUtils {        public static long gcd(long a, long b) {            if (a < 0) a = -a;            if (b < 0) b = -b;            while (b != 0) {                long t = a % b;                a = b;                b = t;            }            return a;        }    }    static class FastPrinter extends PrintWriter {        public FastPrinter(OutputStream out) {            super(out);        }        public FastPrinter(Writer out) {            super(out);        }    }}`