Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Array Filling CodeChef Solution – Queslers
Problem: Array Filling CodeChef Solution
You are given an array AA of size NN. Initially, the array is filled with 00-s.
There are MM types of operations that you can perform on array AA. The ithith operation can be described by two integers (xi,yi)(xi,yi). In this operation, you choose a set of indices SS such that
- 1≤j≤N1≤j≤N,
- (jmodyi)≠0(jmodyi)≠0,
- Aj=0Aj=0,
, then you set Aj=xiAj=xi for all j∈Sj∈S.
You can perform the operations in any order, but one type of operation can’t be done more than once. What is the maximum sum of integers of the array AA you obtain if you perform the MM operations optimally?
For example, consider the array A=[0,0,0,0]A=[0,0,0,0].
- Suppose x=3,y=2x=3,y=2. Here you can choose indices 11 and 33 and set A1=A3=3A1=A3=3. So the array A becomes [3,0,3,0][3,0,3,0]. In this operation you can’t choose the indices 22 and 44 because (2mod2)=0(2mod2)=0, (4mod2)=0(4mod2)=0.
- Suppose x=5,y=3x=5,y=3 and you set A2=5A2=5. So the array AA becomes [3,5,3,0][3,5,3,0]. Here you can’t choose index 11 because A1>0A1>0 and index 33 because (3mod3)=0(3mod3)=0 and A3>0A3>0. However, you could also set A4=5A4=5.
- Suppose x=4,y=4x=4,y=4. Now you can’t choose any index because Aj>0Aj>0 for all 1≤j≤31≤j≤3 and (4mod4)=0(4mod4)=0. So the array remains same.
Note: Since input-output is large, prefer using fast input-output methods.
Input Format
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- Each testcase contains M+1M+1 lines of input.
- The first line of each test case contains two space-separated integers N,MN,M.
- MM lines follow. For each valid ii, the ithith of these lines contains two space-separated integers xi,yixi,yi – parameters of the ithith operation.
Output Format
For each test case, output in a single line the maximum sum of integers of the array AA after MM operations.
Constraints
- 1≤T≤126001≤T≤12600
- 1≤N≤1091≤N≤109
- 1≤M≤1051≤M≤105
- 1≤xi≤1091≤xi≤109
- 2≤yi≤1092≤yi≤109
- The sum of MM over all test cases does not exceed 106106.
Subtasks
Subtask #1 (100 points): original constraints
Sample Input 1
3
10 1
5 2
8 2
5 2
6 3
3 2
2 2
1 3
Sample Output 1
25
41
5
Explanation
Test case 11: Optimal filling is [5,0,5,0,5,0,5,0,5,0][5,0,5,0,5,0,5,0,5,0].
Test case 22: Optimal filling is [6,6,5,6,6,0,6,6][6,6,5,6,6,0,6,6].
Test case 33: Optimal filling is [2,1,2][2,1,2].
Array Filling CodeChef Solution Using Python
# cook your dish here
def gcd(a,b):
if a == 0:
return b
return gcd(b % a, a)
def lcm(a,b):
return (a // gcd(a,b))* b
t = int(input())
for i in range(t):
n, m = map(int, input().split())
arr = []
for k in range(m):
a, b = map(int, input().split())
arr.append([a, b])
arr.sort(key = lambda x: x[0], reverse = True)
low, res, high = 1, 0, n
for j in range(0, m):
if(high > 0):
low = lcm(arr[j][1], low)
high = (high//low)*low
temp = high//low
res += (n-temp)*(arr[j][0])
n = temp
print(res)Array Filling CodeChef Solution Using C++
#include<bits/stdc++.h>
using namespace std;
//#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e18
#define nline "\n"
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define getunique(x) {sort(all(x)); v.erase(unique(all(x)), x.end());}
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
ll lcm(ll num1, ll num2)
{
return (num2 * num1) / (__gcd(num2, num1));
}
int main() {
#ifndef ONLINE_JUDGE
freopen("Error.txt", "w", stderr);
#endif
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ll t;
cin >> t;
ll n, m;
ll xi, yi;
while (t--)
{
cin >> n >> m;
ll temp = m;
vector < pair<ll, ll>> vecop;
while (m--)
{
cin >> xi >> yi;
vecop.push_back(make_pair(xi, yi));
}
sort(vecop.rbegin(), vecop.rend());
// debug(vecop)
ll ans = 0;
ll curlcm = 1;
ll pos = n;
ll curfill;
ll rem;
ll posfilled;
for (int i = 0; i < temp; ++i)
{
curlcm = lcm(curlcm, vecop[i].second);
rem = n / curlcm;
ans += vecop[i].first * (pos - rem);
pos = rem;
if (pos == 0)
break;
}
cout << ans << "\n";
}
}
Array Filling CodeChef Solution Using Java
// Working program using Reader Class
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
static 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[1000000]; // line length
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();
}
}
static final int MAXN = 100001;
static int spf[] = new int[MAXN];
public static void sieve()
{
spf[1] = 1;
for (int i=2; i<MAXN; i++)
spf[i] = i;
for (int i=4; i<MAXN; i+=2)
spf[i] = 2;
for (int i=3; i*i<MAXN; i++)
{
if (spf[i] == i)
{
for (int j=i*i; j<MAXN; j+=i)
if (spf[j]==j)
spf[j] = i;
}
}
}
public static Vector<Integer> getFactorization(int x)
{
Vector<Integer> ret = new Vector<>();
while (x != 1)
{
ret.add(spf[x]);
x = x / spf[x];
}
return ret;
}
public static void main(String[] args) throws IOException
{
Reader sc=new Reader();
int t=sc.nextInt();
while(t-->0){
long n = sc.nextLong();
long m = sc.nextLong();
ArrayList<mi> ma = new ArrayList<mi>();
for(int i = 0; i < m; i++) {
long x = sc.nextLong();
long y = sc.nextLong();
ma.add(new mi(x, y));
}
long ans = 0;
Collections.sort(ma, new A());
long maxLcm = -1;
long prevLcm = 1;
for(int i = (int) m-1; i >= 0; i--) {
long x = ma.get(i).x;
long y = ma.get(i).y;
long count = 0;
if (y > n) {
ans += prevLcm * x;
break;
}
if (i == m-1) {
count = n - ( n / y);
prevLcm = n - count;
maxLcm = y;
} else {
long c = lcm(maxLcm, y);
count = (prevLcm - (n / c));
prevLcm = n / c;
maxLcm = c;
}
ans += (count * x);
if (prevLcm == 0) break;
}
System.out.println(ans);
}
}
public static long lcm(long a, long b) {
long temp = a * b;
return temp / gcd(Math.min(a, b), Math.max(a, b));
}
public static long gcd(long a, long b) {
if (a == 0) return b;
return gcd(b%a, a);
}
}
class mi {
long x;
long y;
mi (long x, long y) {
this.x = x;
this.y = y;
}
}
class A implements Comparator<mi> {
public int compare(mi a, mi b)
{
return (int) (a.x - b.x);
}
}
Array Filling CodeChef Solution Review:
In our experience, we suggest you solve this Array Filling CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
Array Filling Problem is available on Hacker Rank for Free, if you are stuck anywhere between a compilation, just visit Queslers to get Array Filling CodeChef Solution.
Conclusion:
I hope this Array Filling 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 Hacker Rank, Leetcode, Codechef, Codeforce Solution.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More on Queslers >>
