Chef and cities CodeChef Solution

Problem -Chef and cities 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.
<<Previous CodeChef Problem Next Codechef Problem>>

Chef and cities CodeChef Solution in C++14

#include<bits/stdc++.h>
using namespace std;

#define mx 200005
#define ll long long
#define mod 1000000007 //998244353

ll a[mx];
char ch[mx];
int n, m, ii, k;
ll ans[mx];
long double digit[mx];
vector<int>g[mx];
long double eps = 1e-6;

ll add(ll a, ll b)
{
    a += b;
    if (a >= mod)a -= mod;
    return a;
}
ll sub(ll a, ll b)
{
    a -= b;
    if (a < 0)a += mod;
    return a;
}
ll mul(ll a, ll b)
{
    ll re = a;
    re *= b;
    if (re >= mod)re %= mod;
    return re;
}
ll bigmod(ll b, ll e)
{
    ll ans = 1;
    while (e) {
        if (e & 1)ans = mul(ans, b);
        e >>= 1;
        b = mul(b, b);
    }
    return ans;
}

void solve()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), ans[i] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j += i) {
            g[j].push_back(i);
            ans[i] = mul(ans[i], a[j]);
            digit[i] += log10(a[j] + eps);
        }
    }

    int q;

    scanf("%d", &q);

    while (q--) {
        int type;

        scanf("%d", &type);

        if (type == 1) {
            int id;
            ll val;

            scanf("%d%lld", &id, &val);

            if (id == 1) {
                a[id] = val;
            }
            else {
                for (auto v : g[id]) {
                    ans[v] = mul(ans[v], bigmod(a[id], mod - 2));
                    digit[v] -= log10(a[id] + eps);
                    digit[v] += log10(val + eps);
                    ans[v] = mul(ans[v], val);
                }
                a[id] = val;
            }
        }
        else {
            int r;

            scanf("%d", &r);

            long double fractional = log10(a[1] + eps) + digit[r];

            int re = pow(10.0, fractional - (ll)fractional);

            // cout << ans[r] << " ";

            ll answer = mul(ans[r], a[1]);

            printf("%d %lld\n", re, answer);
        }
    }

    return;
}

int main()
{
    int t = 1;
    // scanf("%d", &t);
    for (int i = 1; i <= t; i++) {
        // printf("Case %d: ", i);
        solve();
    }
    return 0;
}

Chef and cities CodeChef Solution in PYTH 3


import math
import sys

class Main:
	def __init__( self ):
		iterable = self.__input( )
		iterable = self.__solution( iterable )

		self.__output( iterable )

	def __solution( self, iterable ):
		iterable = map( int, iterable )

		count = next( iterable )
		data = [ next( iterable ) for _index in range( count ) ]

		state = State( data )

		queries = next( iterable )

		for _index in range( queries ):
			command = next( iterable )

			if command == 1:
				index = next( iterable ) - 1
				value = next( iterable )

				state.update( index, value )

			else:
				step = next( iterable )

				digit, remainder = state.calculate( step )

				yield digit
				yield " "
				yield str( remainder )
				yield "\n"

	def __input( self ):
		yield from sys.stdin.buffer.raw.read( ).decode( ).split( )

	def __output( self, iterable ):
		sys.stdout.buffer.raw.write( "".join( iterable ).encode( ) )

class State:
	def __init__( self, data ):
		modulus = ( 10 ** 9 ) + 7
		size = len( data )

		self.__modulus = modulus

		self.__remainders = data
		self.__logarithms = [ math.fmod( math.log10( item ), 1 ) for item in data ]

		self.__lookup = [ [ ] for _index in range( size ) ]

		self.__remaindersN = [ 0 ]
		self.__logarithmsN = [ 0 ]

		for step in range( 1, size + 1 ):
			product = 1
			summa = 0

			for index in range( step, size, step ):
				product = product * data[ index ] % modulus
				summa = math.fmod( summa + self.__logarithms[ index ], 1 )

				self.__lookup[ index ].append( step )

			self.__remaindersN.append( product )
			self.__logarithmsN.append( summa )

	def update( self, index, value ):
		inverse = pow( self.__remainders[ index ], self.__modulus - 2, self.__modulus )
		negative = 1 - self.__logarithms[ index ]

		value0 = math.fmod( math.log10( value ), 1 )

		self.__remainders[ index ] = value
		self.__logarithms[ index ] = value0

		for step in self.__lookup[ index ]:
			self.__remaindersN[ step ] = ( self.__remaindersN[ step ] * inverse * value ) % self.__modulus
			self.__logarithmsN[ step ] = math.fmod( self.__logarithmsN[ step ] + negative + value0, 1 )

	def calculate( self, step ):
		remainder = ( self.__remainders[ 0 ] * self.__remaindersN[ step ] ) % self.__modulus
		logarithm = math.fmod( self.__logarithms[ 0 ] + self.__logarithmsN[ step ], 1 )

		top = round( pow( 10, logarithm ), 9 )

		return str( top )[ 0 ], remainder

if __name__ == "__main__":
	Main( )

Chef and cities CodeChef Solution in C


#include <stdio.h>
#include <math.h>

#define ll long long
#define gc getchar_unlocked
#define MOD 1000000007

int getn(){
  int n = 0, c = gc(), f = 1;
  while(c != '-' && (c < '0' || c > '9')) c = gc();
  if(c == '-') f = -1, c = gc();
  while(c >= '0' && c <= '9') n = (n<<3) + (n<<1) + c - '0', c = gc();
  return n * f;
}

int mmul(int a, int b){ return (ll)a * b % MOD; }

int mpow(ll n, int e){
  ll r = 1;
  while(e){
    if(e & 1) r = r * n % MOD;
    n = n * n % MOD, e >>= 1;
  }
  return (int)r;
}

int a[100000], b[100000][256], bn[100000], p[100001];
double s[100001];
int main(){
  int N,Q,O,P,F,R, i,j, u;
  double t;

  N = getn();
  for(i = 0; i < N; ++i) a[i] = getn(), bn[i] = 0;

  for(i = 1; i <= N; ++i) for(j = i, s[i] = 0, p[i] = 1; j < N; j += i)
    p[i] = mmul(p[i], a[j]), s[i] += log10(a[j]), b[j][bn[j]++] = i;

  Q = getn();
  while(Q--){
    O = getn();
    if(O == 1){
      P = getn()-1, F = getn();
      if(!P){ a[0] = F; continue; }
      for(i = 0; i < bn[P]; ++i)
        p[b[P][i]] = mmul(mmul(p[b[P][i]], mpow(a[P], MOD-2)), F),
        s[b[P][i]] += log10(F) - log10(a[P]);
      a[P] = F;
    }else{
      R = getn();
      t = s[R] + log10(a[0]);
      u = (int)(pow(10, t-(int)t)+0.000000001);
      while(u > 9) u /= 10;
      printf("%d %d\n", u, mmul(p[R], a[0]));
    }
  }
  return 0;
}

Chef and cities CodeChef Solution in JAVA

import java.io.*;
import java.util.*;
class frjump 
{
    static int mod=1000000007;
    static int modinv(int a, int p)
    {
        if(p == 1)
        {
            return a%mod;
        }
        else if(p % 2==0)
        {
            int half = p/2;
            long val = modinv(a, half);
            val = (val * val)%mod;
            return (int)val;
        }
        else
        {
            int half = p/2;
            long val =  modinv(a, half);
            val = (((val* val)%mod)*a)%mod;
            return (int)val;
        }
        
    }
    public static void main(String args[])throws IOException
    {
        Reader sc=new Reader();
        int n=sc.nextInt();
        //int q=sc.nextInt();
        List<Integer> list[]=new ArrayList[n];
        //list[0]=new ArrayList<>();
        for(int i=1;i<=n;i++)
        {
            list[i-1]=new ArrayList<>();
        }
        
        int arr[]=new int[n];
        double log[]=new double[n];
        int inv[]=new int[n];
        long mult[]=new long[n];
        double sum[]=new double[n];
        for(int i=0;i<n;i++)
        {
            arr[i]=sc.nextInt();
            log[i]=Math.log10(arr[i]);
            log[i]=log[i]-Math.floor(log[i]);
            inv[i]=modinv(arr[i],mod-2);
            mult[i]=1;
        }
        int first=arr[0];double lo=log[0];
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<n;j=j+i)
            {
                list[j].add(i-1);
                mult[i-1]=(mult[i-1]*arr[j])%mod;
                sum[i-1]=(sum[i-1]+log[j]);
            }
        }
        
        int q=sc.nextInt();
        for(int z=0;z<q;z++)
        {
            int typ=sc.nextInt();
            if(typ==1)
            {
                int ind=sc.nextInt();
                int f=sc.nextInt();
                double l=Math.log10(f);
                l=l-Math.floor(l);
                if(ind==1)
                {
                    first=f;
                    lo=l;
                }
                else
                {
                    for(int j=0;j<list[ind-1].size();j++)
                    {
                        int num=list[ind-1].get(j);
                        mult[num]=(mult[num]*f)%mod;
                        mult[num]=(mult[num]*inv[ind-1])%mod;
                        sum[num]=sum[num]+l-log[ind-1];
                    }
                    arr[ind-1]=f;
                    log[ind-1]=l;
                    inv[ind-1]=modinv(f,mod-2);
                }
                
            }
            else
            {
                int ind=sc.nextInt();
                double fv=sum[ind-1]+lo-log[0];
                double f = fv -Math.floor(fv);
                int fd = (int)Math.floor(Math.pow(10, f+0.000000000001));
                if(fd == 10)
                {
                        fd = 1;
                }
                long value = (mult[ind-1]*first)%mod;
                value = (value * inv[0])%mod;
                System.out.println(fd+" "+value);
            }
            //System.out.println(list[z]);
        }
        
    }
}
class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte [] buffer;
		private int bufferPointer, bytesRead;
		
		public Reader () {
			din = new DataInputStream (System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
		
		public Reader (String file_name) throws IOException {
			din = new DataInputStream (new FileInputStream (file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}
		
		public String readLine () throws IOException {
			byte [] buf = new byte[1024];
			int cnt = 0, c;
			while ((c = read ()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String (buf, 0, cnt);
		}
		
		public int nextInt () throws IOException {
			int ret = 0;
			byte c = read ();
			while (c <= ' ')
				c = read ();
			boolean neg = (c == '-');
			if (neg)
				c = read ();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read ()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}
		
		public long nextLong () throws IOException {
			long ret = 0;
			byte c = read ();
			while (c <= ' ')
				c = read ();
			boolean neg = (c == '-');
			if (neg)
				c = read ();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read ()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}
		
		public double nextDouble () throws IOException {
			double ret = 0, div = 1;
			byte c = read ();
			while (c <= ' ')
				c = read ();
			boolean neg = (c == '-');
			if (neg)
				c = read ();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read ()) >= '0' && c <= '9');
			if (c == '.')
				while ((c = read ()) >= '0' && c <= '9')
					ret += (c - '0') / (div *= 10);
			if (neg)
				return -ret;
			return ret;
		}
		
		private void fillBuffer () throws IOException {
			bytesRead = din.read (buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}
		
		private byte read () throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer ();
			return buffer[bufferPointer++];
		}
		
		public void close () throws IOException {
			if (din == null)
				return;
			din.close ();
		}
	}

Chef and cities CodeChef Solution in PYTH

import math
n = int(raw_input())
friendliness = map(int, raw_input().split())
logSum = [0]
prodSum = [0]
d = [[] for i in range(n)]
for r in range(1, n+1):
	l = 0
	p = 1
	for j in range(r,n, r):
		l += math.log10(friendliness[j])
		p  = (p*friendliness[j])%(10**9 + 7)
		d[j].append(r)

	logSum.append(l)
	prodSum.append(p)
# print logSum
# print prodSum
# print d
q = int(raw_input())
for t in range(q):
	query = map(int, raw_input().split())

	if query[0] == 2:
		x = logSum[query[1]] + math.log10(friendliness[0]) - math.floor(logSum[query[1]] + math.log10(friendliness[0]))
		s = str(math.pow(10,x))
		# print 's =', s
		answer = (prodSum[query[1]]*friendliness[0])%(10**9 + 7)
		
		print s[0],answer
	
	else:
		r = query[1]
		if r == 1:
			friendliness[0] = query[2]
		else:
			temp = pow(friendliness[r-1], 10**9 + 7 - 2, 10**9 + 7)
			# print 'inverse', temp
			for j in d[r-1]:
				prodSum[j] = (prodSum[j]*query[2]*temp)%(10**9+7)
				logSum[j] += math.log10(query[2]) - math.log10(friendliness[r-1])
				
			# print 'updated values'
			# print prodSum
			# print logSum
			friendliness[r-1] = query[2]
			# print friendliness

Chef and cities CodeChef Solution in C#

using System;
using System.Collections.Generic;
using System.Text;

namespace JUMP
{
    class Querie
    {
        public int a, b, c;
        public Querie(int a, int b)
        {
            this.a = a; this.b = b;
            c = 0;
        }

        public Querie(int a, int b, int c)
        {
            this.a = a; this.b = b; this.c = c;
        }
    }

    class Program
    {
        public static List<int>[] D = new List<int>[100001];
        public static int[] A = new int[100001];
        public const int mod = 1000000007;
        public static int[] R = new int[100002];
        public static double[] L = new double[100001];
        public static double[] Log = new double[100001];
        public static StringBuilder sb = new StringBuilder();
        public static List<Querie> queries = new List<Querie>();

        static void Main(string[] args)
        {
            
            int N, Q;
            bool ok = true;
            N = int.Parse(Console.ReadLine());
            if (N > 10) ok = false;
            string[] tokens = Console.ReadLine().Split(' ');
            
            for (int i = 1; i <= N; i++)
            {
                A[i] = int.Parse(tokens[i-1]);
                if (A[i] > 10) ok = false;
                Log[i] = Math.Log10(A[i]);
            }

            // find the divisors
            for (int i = 1; i <= N; i++)
            {
                D[i] = new List<int>();
            }

            int p;
            for (int i = 1; i <= N; i++)
            {
                p = i;
                while (p < N)
                {
                    D[p + 1].Add(i);
                    p += i;
                }
            }

            // preprocess
            for (int i = 1; i <= N; i++)
            {
                R[i] = 1;
                L[i] = 0.0;
                p = 1 + i;
                while(p<=N)
                {
                    R[i] = mult(R[i], A[p]);
                    L[i] += Log[p];
                    p += i;
                }
            }

            // read queries
            Q = int.Parse(Console.ReadLine());

            for (int i = 0; i < Q; i++)
            {
                tokens = Console.ReadLine().Split(' ');
                int a, b, c;
                a = int.Parse(tokens[0]);
                b = int.Parse(tokens[1]);
                if (a == 1)
                {
                    c = int.Parse(tokens[2]);
                    if (c > 10) ok = false;
                }
                else c = 0;
                queries.Add(new Querie(a, b, c));
            }

            if(ok)
            {
                Solve(Q, N);
                return;
            }

            int q;
            double log;
            int f, r, prod;

            for (int i = 0; i < Q; i++)
            {
                q = queries[i].a;

                switch (q)
                {
                    case 1:
                        p = queries[i].b;
                        f = queries[i].c;

                        if (p == 1)
                        {
                            A[p] = f;
                            Log[p] = Math.Log10(f);
                            continue;
                        }

                        prod = mult(inverse(A[p]), f);
                        log = Math.Log10(f) - Log[p];

                        foreach (int d in D[p])
                        {
                            R[d] = mult(R[d], prod);
                            L[d] += log;
                        }

                        A[p] = f;
                        Log[p] = Math.Log10(f);
                        break;

                    case 2:
                        r = queries[i].b;
                        sb.Append(firstDigit(L[r] + Log[1]) + " " + mult(R[r], A[1]) + "\n");
                        break;

                    default: break;
                }
            }

            Console.Write(sb);
        }

        static void Solve(int Q, int N)
        {
            int q, p;
            int f, r;
            long ans;

            for (int i = 0; i < Q; i++)
            {
                q = queries[i].a;
                switch (q)
                {
                    case 1:
                        p = queries[i].b;
                        f = queries[i].c;
                        A[p] = f;
                        break;

                    case 2:
                        r = queries[i].b;
                        ans = 1;
                        for (int j = 1; j <= N; j += r) ans *= A[j];
                        Console.WriteLine(firstDigit(Math.Log10(ans)) + " " + (ans % mod));
                        break;
                    default: break;
                }
            }
        }

        static int mult(int a, int b)
        {
            long t = 1L* a * b;
            if (t >= mod) t %= mod;
            return (int)t;
        }

        static int modPow(int b, int e)
        {
            int ans = 1;
            while(e > 0)
            {
                if (e%2 == 1) ans = mult(ans, b);
                b = mult(b, b);
                e >>= 1;
            }
            return ans;
        }

        static int inverse(int a)
        {
            return modPow(a, mod - 2);
        }

        static int firstDigit(double L)
        {
            double p = Math.Truncate(L);
            double tp = Math.Pow(10.0, L - p);
            int ans = String.Format("{0}", tp)[0] - '0';
            return ans;
        }

    }
}
Chef and cities CodeChef Solution Review:

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

Find on CodeChef

Conclusion:

I hope this Chef and cities 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

Leave a Reply

Your email address will not be published. Required fields are marked *