HackerEarth Ratio problem solution YASH PAL, 31 July 2024 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); } }} coding problems