Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Adding Fractions CodeChef Solution
Problem -Adding Fractions 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.
Adding Fractions CodeChef Solution in C++17
#include <bits/stdc++.h>
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("Ofast")//Comment optimisations for interactive problems (use endl)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
using namespace std;
struct PairHash {inline std::size_t operator()(const std::pair<int, int> &v) const { return v.first * 31 + v.second; }};
// speed
#define Code ios_base::sync_with_stdio(false);
#define By ios::sync_with_stdio(0);
#define Sumfi cout.tie(NULL);
// alias
using ll = long long;
using ld = long double;
using ull = unsigned long long;
// constants
const ld PI = 3.14159265358979323846; /* pi */
const ll INF = 1e18;
const ld EPS = 1e-9;
const ll MAX_N = 1010101;
const ll mod = 998244353;
// typedef
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef array<ll,3> all3;
typedef array<ll,5> all5;
typedef vector<all3> vall3;
typedef vector<all5> vall5;
typedef vector<ld> vld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef deque<ll> dqll;
typedef deque<pll> dqpll;
typedef pair<string, string> pss;
typedef vector<pss> vpss;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef unordered_set<ll> usll;
typedef unordered_set<pll, PairHash> uspll;
typedef unordered_map<ll, ll> umll;
typedef unordered_map<pll, ll, PairHash> umpll;
// macros
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,m,n) for(ll i=n;i>=m;i--)
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define INF(a) memset(a,0x3f3f3f3f3f3f3f3fLL,sizeof(a))
#define ASCEND(a) iota(all(a),0)
#define sz(x) ll((x).size())
#define BIT(a,i) (a & (1ll<<i))
#define BITSHIFT(a,i,n) (((a<<i) & ((1ll<<n) - 1)) | (a>>(n-i)))
#define pyes cout<<"YES\n";
#define pno cout<<"NO\n";
#define endl "\n"
#define pneg1 cout<<"-1\n";
#define ppossible cout<<"Possible\n";
#define pimpossible cout<<"Impossible\n";
#define TC(x) cout<<"Case #"<<x<<": ";
#define X first
#define Y second
// utility functions
template <typename T>
void print(T &&t) { cout << t << "\n"; }
template<typename T>
void printv(vector<T>v){ll n=v.size();rep(i,0,n){cout<<v[i];if(i+1!=n)cout<<' ';}cout<<endl;}
template<typename T>
void printvln(vector<T>v){ll n=v.size();rep(i,0,n)cout<<v[i]<<endl;}
void fileIO(string in = "input.txt", string out = "output.txt") {freopen(in.c_str(),"r",stdin); freopen(out.c_str(),"w",stdout);}
void readf() {freopen("", "rt", stdin);}
template<typename T>
void readv(vector<T>& v){rep(i,0,sz(v)) cin>>v[i];}
template<typename T, typename U>
void readp(pair<T,U>& A) {cin>>A.first>>A.second;}
template<typename T, typename U>
void readvp(vector<pair<T,U>>& A) {rep(i,0,sz(A)) readp(A[i]); }
void readvall3(vall3& A) {rep(i,0,sz(A)) cin>>A[i][0]>>A[i][1]>>A[i][2];}
void readvall5(vall5& A) {rep(i,0,sz(A)) cin>>A[i][0]>>A[i][1]>>A[i][2]>>A[i][3]>>A[i][4];}
void readvvll(vvll& A) {rep(i,0,sz(A)) readv(A[i]);}
struct Combination {
vll fac, inv;
ll n, MOD;
ll modpow(ll n, ll x, ll MOD = mod) { if(!x) return 1; ll res = modpow(n,x>>1,MOD); res = (res * res) % MOD; if(x&1) res = (res * n) % MOD; return res; }
Combination(ll _n, ll MOD = mod): n(_n + 1), MOD(MOD) {
inv = fac = vll(n,1);
rep(i,1,n) fac[i] = fac[i-1] * i % MOD;
inv[n - 1] = modpow(fac[n - 1], MOD - 2, MOD);
rrep(i,1,n - 2) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
ll fact(ll n) {return fac[n];}
ll nCr(ll n, ll r) {
if(n < r or n < 0 or r < 0) return 0;
return fac[n] * inv[r] % MOD * inv[n-r] % MOD;
}
};
struct Matrix {
ll r,c;
vvll matrix;
Matrix(ll r, ll c, ll v = 0): r(r), c(c), matrix(vvll(r,vll(c,v))) {}
Matrix operator*(const Matrix& B) const {
Matrix res(r, B.c);
rep(i,0,r) rep(j,0,B.c) rep(k,0,B.r) {
res.matrix[i][j] = (res.matrix[i][j] + matrix[i][k] * B.matrix[k][j] % mod) % mod;
}
return res;
}
Matrix copy() {
Matrix copy(r,c);
copy.matrix = matrix;
return copy;
}
Matrix pow(ll n) {
assert(r == c);
Matrix res(r,r);
Matrix now = copy();
rep(i,0,r) res.matrix[i][i] = 1;
while(n) {
if(n & 1) res = res * now;
now = now * now;
n /= 2;
}
return res;
}
};
// geometry data structures
template <typename T>
struct Point {
T y,x;
Point(T y, T x) : y(y), x(x) {}
Point(pair<T,T> p) : y(p.first), x(p.second) {}
Point() {}
void input() {cin>>y>>x;}
friend ostream& operator<<(ostream& os, const Point<T>& p) { os<<p.y<<' '<<p.x<<'\n'; return os;}
Point<T> operator+(Point<T>& p) {return Point<T>(y + p.y, x + p.x);}
Point<T> operator-(Point<T>& p) {return Point<T>(y - p.y, x - p.x);}
Point<T> operator*(ll n) {return Point<T>(y*n,x*n); }
Point<T> operator/(ll n) {return Point<T>(y/n,x/n); }
bool operator<(const Point &other) const {if (x == other.x) return y < other.y;return x < other.x;}
Point<T> rotate(Point<T> center, ld angle) {
ld si = sin(angle * PI / 180.), co = cos(angle * PI / 180.);
ld y = this->y - center.y;
ld x = this->x - center.x;
return Point<T>(y * co - x * si + center.y, y * si + x * co + center.x);
}
ld distance(Point<T> other) {
T dy = abs(this->y - other.y);
T dx = abs(this->x - other.x);
return sqrt(dy * dy + dx * dx);
}
T norm() { return x * x + y * y; }
};
template<typename T>
struct Line {
Point<T> A, B;
Line(Point<T> A, Point<T> B) : A(A), B(B) {}
Line() {}
void input() {
A = Point<T>();
B = Point<T>();
A.input();
B.input();
}
T ccw(Point<T> &a, Point<T> &b, Point<T> &c) {
T res = a.x * b.y + b.x * c.y + c.x * a.y;
res -= (a.x * c.y + b.x * a.y + c.x * b.y);
return res;
}
bool isIntersect(Line<T> o) {
T p1p2 = ccw(A,B,o.A) * ccw(A,B,o.B);
T p3p4 = ccw(o.A,o.B,A) * ccw(o.A,o.B,B);
if (p1p2 == 0 && p3p4 == 0) {
pair<T,T> p1(A.y, A.x), p2(B.y,B.x), p3(o.A.y, o.A.x), p4(o.B.y, o.B.x);
if (p1 > p2) swap(p2, p1);
if (p3 > p4) swap(p3, p4);
return p3 <= p2 && p1 <= p4;
}
return p1p2 <= 0 && p3p4 <= 0;
}
pair<bool,Point<ld>> intersection(Line<T> o) {
if(!this->intersection(o)) return {false, {}};
ld det = 1. * (o.B.y-o.A.y)*(B.x-A.x) - 1.*(o.B.x-o.A.x)*(B.y-A.y);
ld t = ((o.B.x-o.A.x)*(A.y-o.A.y) - (o.B.y-o.A.y)*(A.x-o.A.x)) / det;
return {true, {A.y + 1. * t * (B.y - A.y), B.x + 1. * t * (B.x - A.x)}};
}
//@formula for : y = ax + b
//@return {a,b};
pair<ld, ld> formula() {
T y1 = A.y, y2 = B.y;
T x1 = A.x, x2 = B.x;
if(y1 == y2) return {1e9, 0};
if(x1 == x2) return {0, 1e9};
ld a = 1. * (y2 - y1) / (x2 - x1);
ld b = -x1 * a + y1;
return {a, b};
}
};
template<typename T>
struct Circle {
Point<T> center;
T radius;
Circle(T y, T x, T radius) : center(Point<T>(y,x)), radius(radius) {}
Circle(Point<T> center, T radius) : center(center), radius(radius) {}
Circle() {}
void input() {
center = Point<T>();
center.input();
cin>>radius;
}
bool circumference(Point<T> p) {
return (center.x - p.x) * (center.x - p.x) + (center.y - p.y) * (center.y - p.y) == radius * radius;
}
bool intersect(Circle<T> c) {
T d = (center.x - c.center.x) * (center.x - c.center.x) + (center.y - c.center.y) * (center.y - c.center.y);
return (radius - c.radius) * (radius - c.radius) <= d and d <= (radius + c.radius) * (radius + c.radius);
}
bool include(Circle<T> c) {
T d = (center.x - c.center.x) * (center.x - c.center.x) + (center.y - c.center.y) * (center.y - c.center.y);
return d <= radius * radius;
}
};
ll __gcd(ll x, ll y) { return !y ? x : __gcd(y, x % y); }
all3 __exgcd(ll x, ll y) { if(!y) return {x,1,0}; auto [g,x1,y1] = __exgcd(y, x % y); return {g, y1, x1 - (x/y) * y1}; }
ll __lcm(ll x, ll y) { return x / __gcd(x,y) * y; }
ll modpow(ll n, ll x, ll MOD = mod) { n%=MOD; if(!x) return 1; ll res = modpow(n,x>>1,MOD); res = (res * res) % MOD; if(x&1) res = (res * n) % MOD; return res; }
pll parse(string s) {
auto p = s.find('/');
ll l = stoll(s.substr(0,p)), r = stoll(s.substr(p + 1));
return {l,r};
}
bool check(pll A, pll B) {
pll C = {A.first + B.first, A.second + B.second};
return 1. * A.first / A.second < 1. * C.first / C.second;
}
vs solve(vs A) {
ll n = sz(A);
vpll B;
vll jump(n);
vs res(n);
rep(i,0,n) B.push_back(parse(A[i]));
rrep(i,0,n - 1) {
ll j = i + 1;
while(j < n and check(B[i], B[j])) {
B[i].first += B[j].first;
B[i].second += B[j].second;
j = jump[j];
}
jump[i] = j;
ll g = __gcd(B[i].first, B[i].second);
res[i] = (to_string(B[i].first/g) + "/" + to_string(B[i].second/g));
}
return res;
}
int main() {
Code By Sumfi
cout.precision(12);
ll tc = 1;
cin>>tc;
rep(i,1,tc+1) {
ll n;
cin>>n;
vs A(n);
readv(A);
printvln(solve(A));
if(i != tc) print("");
}
return 0;
}Adding Fractions CodeChef Solution in C++14
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int nax=1e5+10;
struct node{
int x,y;
double s;
void init(){
s=1.0*x/y;
}
bool operator<(const node& e)const{
return s<e.s;
}
bool operator>(const node& e)const{
return s>e.s;
}
node operator+(const node& e)const{
node res;
res.x=x+e.x;
res.y=y+e.y;
res.init();
return res;
}
node operator-(const node& e)const{
node res;
res.x=x-e.x;
res.y=y-e.y;
res.init();
return res;
}
}a[nax];
int32_t main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
char c;
int nxt[n+2]={0};
for(int i=1;i<=n;i++)
cin>>a[i].x>>c>>a[i].y,a[i].init();
nxt[n+1]=n+1;
for(int i=n;i>=1;i--){
int j=i+1;
while(j<=n and a[i]+a[j]>a[i]){
a[i]=a[i]+a[j];
j=nxt[j];
}
nxt[i]=j;
}
for(int i=1;i<=n;i++){
int g=__gcd(a[i].x,a[i].y);
a[i].x/=g;
a[i].y/=g;
cout<<a[i].x<<'/'<<a[i].y<<'\n';
}
}
return 0;
}Adding Fractions CodeChef Solution in C
#include<stdio.h>
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a%b);
}
int main(int argc, char ** argv) {
int t;
scanf("%d", &t);
while(t--) {
int n;
float max1,max2;
int i,j,temp;
scanf("%d", &n);
int num[n], den[n];
int rnum[n], rden[n], count[n];
for(int i = 0; i < n; i++) {
scanf("%d/%d", &num[i], &den[i]);
}
n=n-1;
rnum[n]=num[n];
rden[n]=den[n];count[n]=n;
for(i=n-1;i>=0;i--)
{
rnum[i]=num[i];rden[i]=den[i];
for(j=i;j<=n-1;j++,j=count[j])
{
max1=((float)rnum[i]/(float)rden[i]);
max2=((float)(rnum[j+1])/(float)(rden[j+1]));
if(max2<max1)
{
count[i]=j;
break;
}
else
{
rnum[i]+=rnum[j+1];
rden[i]+=rden[j+1];
}
}if(j==n)count[i]=n;
}
for(i=0;i<=n;i++){
temp=gcd(rnum[i],rden[i]);
rnum[i]=rnum[i]/temp;
rden[i]=rden[i]/temp;
printf("%d/%d\n",rnum[i],rden[i]);
}
printf("\n");
}
return 0;
}Adding Fractions CodeChef Solution in JAVA
import java.io.*;
import java.util.*;
/*
This Library is usefull when from Input File we have to extract only numbers.
It's 2 times faster then BasicInputOutput Library made earlier
*/
import java.io.*;
class FastInputOutput
{
private byte[] inputBuffer;
private final static int INPUTBUFFERSIZE = 8192;
private int inputIndex, charRead;
private BufferedWriter writer;
private String delim = " \t\n\r\f";
FastInputOutput()
{
initialize();
}
FastInputOutput( String s )
{
delim = s;
initialize();
}
private void initialize()
{
inputBuffer = new byte[INPUTBUFFERSIZE + 1];
inputIndex = 0;
charRead = inputIndex;
writer = new BufferedWriter( new PrintWriter( System.out ));
}
private void updateInputBuffer()throws IOException
{
if ( inputIndex >= charRead )
{
charRead = System.in.read( inputBuffer, 0, INPUTBUFFERSIZE );
inputIndex = 0;
}
}
private void skipUntilNotDigit()throws IOException
{
updateInputBuffer();
while ( !isDigit( inputBuffer[inputIndex] ) && !isSign( inputBuffer[inputIndex] ))
{
inputIndex++;
updateInputBuffer();
}
}
private void skipUntilDilim()throws IOException
{
updateInputBuffer();
while ( isDelimiter( inputBuffer[inputIndex] ) )
{
inputIndex++;
updateInputBuffer();
}
}
private boolean isDelimiter( byte c )
{
for ( int i = 0; i < delim.length(); i++ )
{
if ( c == ( byte )delim.charAt( i ))
return true;
}
return false;
}
private boolean isDigit( byte c )
{
return ( c >= '0' && c <= '9' );
}
private boolean isSign( byte s )
{
return ( s == '+' || s == '-' );
}
public int getNextInt()throws IOException
{
skipUntilNotDigit();
int ret = 0;
int sgn = 1;
while ( isSign( inputBuffer[inputIndex] ))
{
if ( inputBuffer[inputIndex] == '-' )
sgn = - 1;
inputIndex++;
updateInputBuffer();
if ( !isDigit( inputBuffer[inputIndex] ))
{
sgn = 1;
skipUntilNotDigit();
}
}
while ( isDigit( inputBuffer[inputIndex] ))
{
ret = ( ret * 10 ) + inputBuffer[inputIndex++] - '0';
updateInputBuffer();
}
return ret * sgn;
}
public long getNextLong()throws IOException
{
skipUntilNotDigit();
long ret = 0;
long sgn = 1;
while ( isSign( inputBuffer[inputIndex] ))
{
if ( inputBuffer[inputIndex] == '-' )
sgn = - 1L;
inputIndex++;
updateInputBuffer();
if ( !isDigit( inputBuffer[inputIndex] ))
{
sgn = 1L;
skipUntilNotDigit();
}
}
while ( isDigit( inputBuffer[inputIndex] ))
{
ret = ( ret * 10L ) + inputBuffer[inputIndex++] - '0';
updateInputBuffer();
}
return ret;
}
public String getNextString()throws IOException
{
String ret = "";
skipUntilDilim();
while ( !isDelimiter( inputBuffer[inputIndex] ))
{
ret = ret + ( char )inputBuffer[inputIndex++];
updateInputBuffer();
}
return ret;
}
public String getNextLine()throws IOException
{
String ret = "";
skipUntilDilim();
while ( inputBuffer[inputIndex] != ( byte )'\n' && inputBuffer[inputIndex] != ( byte )'\r' && inputBuffer[inputIndex] != ( byte )'\f' )
{
ret = ret + ( char )inputBuffer[inputIndex++];
updateInputBuffer();
}
return ret;
}
public void skipCurrentLine()throws IOException
{
updateInputBuffer();
while ( inputBuffer[inputIndex] != ( byte )'\n' && inputBuffer[inputIndex] != ( byte )'\r' && inputBuffer[inputIndex] != ( byte )'\f' )
{
inputIndex++;
updateInputBuffer();
}
}
public void skip(int n) throws IOException {
updateInputBuffer();
while(n-->0) {
inputIndex++;
updateInputBuffer();
}
}
public void write( String s )throws IOException
{
writer.write( s );
}
public < T > void write( char sep, T... var )throws IOException
{
if ( var.length == 0 )
return ;
writer.write( var[0].toString());
for ( int i = 1; i < var.length; i++ )
{
writer.write( sep + var[i].toString());
}
}
public void flush()throws IOException
{
writer.flush();
}
}
public class Main
{
public static void main(String[] args)
{
try
{
new Main().run();
}
catch (Exception ex)
{
ex.printStackTrace();
}
}
private int[][] num;
private long[][] ans;
private int[] next;
private FastInputOutput iohandler;
int n;
private void run()throws Exception
{
iohandler = null;
initializeProcess();
getInput();
}
private void getInput()throws Exception
{
int tc = iohandler.getNextInt();
while (--tc >= 0)
{
n = iohandler.getNextInt();
for (int i = 0; i < n; i++)
{
num[i][0] = iohandler.getNextInt();
num[i][1] = iohandler.getNextInt();
}
solve();
output();
if (tc > 0)
{
iohandler.write("\n");
}
}
iohandler.flush();
}
private boolean check(long a, long b, long c, long d)
{
return (a * d < b * c);
}
private void solve()throws Exception
{
ans[n - 1][0] = num[n - 1][0];
ans[n - 1][1] = num[n - 1][1];
next[n - 1] = n - 1;
for (int i = n - 2; i >= 0; i--)
{
ans[i][0] = num[i][0];
ans[i][1] = num[i][1];
next[i] = i;
while (next[i] + 1 < n && check(ans[i][0], ans[i][1], ans[next[i] + 1][0], ans[next[i] + 1][1]))
{
ans[i][0] += ans[next[i] + 1][0];
ans[i][1] += ans[next[i] + 1][1];
next[i] = next[next[i] + 1];
}
}
}
private void output()throws Exception
{
for (int i = 0; i < n; i++)
{
long g = gcd(ans[i][0], ans[i][1]);
ans[i][0] /= g;
ans[i][1] /= g;
iohandler.write(ans[i][0] + "/" + ans[i][1] + "\n");
}
}
private void initializeProcess()throws Exception
{
iohandler = new FastInputOutput();
num = new int[100001][2];
ans = new long[100001][2];
next = new int[100001];
}
private long gcd(long a, long b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
}Adding Fractions CodeChef Solution Review:
In our experience, we suggest you solve this Adding Fractions 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 Adding Fractions CodeChef Solution.
Conclusion:
I hope this Adding Fractions 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!
