HackerEarth Three arrays problem solution

In this HackerEarth Three arrays problem solution You are given three arrays a1…n, b1…n, c1…n and two numbers M and K. Find a lexicographically minimum {x,y,z} such that there are exactly K indices i(1 <= i <= n) where x * ai + y * bi – ci * z = M * f for some integer f.

Also, you are given ranges of x, y, and z — l1..3, r1…3 ((l1 <= x <= r1, l2 <= y <= r2, l3 <= z <= r3. Here, a triplet of integers {x1, y1, z1} is considered to be lexicographically smaller than a triplet {x2, y2, z2} if sequence [x1, y1, z1] is lexicographically smaller than sequence [x2, y2, z2] A sequence a is lexicographically smaller than a sequence b if in the first position where a and b differ, the sequence a has a smaller element than the corresponding element in b.

HackerEarth Three arrays problem solution.

#include <bits/stdc++.h>
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define VAR(v, i) __typeof( i) v=(i)
#define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
 
using namespace std;
 
const int maxn = (int)1e6 + 100;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7; 
const double pi = acos(-1.0);

#define inf mod
 
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;   
typedef vector<ll> Vll;               
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;                        

int n, m, k, a[maxn], b[maxn], c[maxn], l[4], r[4];
inline int sum(int a, int b){
    a += b;
    if(a >= m) a -= m;
    if(a < 0) a += m;
    return a;
}
inline int mult(int a, int b){
    return a * 1ll * b % m;
}
void solve(){
  cin >> n >> m >> k;
  forn(i, 1, n) cin >> a[i] >> b[i] >> c[i];
  forn(i, 1, 3) cin >> l[i] >> r[i];
  forn(x, l[1], min(r[1], l[1] + m - 1))
    forn(y, l[2], min(r[2], l[2] + m - 1))
      forn(z, l[3], min(r[3], l[3] + m - 1)){
        int cnt = 0;
        forn(i, 1, n){
          if(!sum(sum(mult(a[i], x), mult(b[i], y)), m - mult(c[i], z)))
            cnt++;
          if(cnt > k) break;
        }
        if(cnt == k){
          cout << x << " "  << y << " " << z << endl;
          exit(0);
        }
      }
  puts("-1");
}

main () {
  int t = 1;
  //scanf("%d", &t);
  while(t--)
    solve(); 
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 14;

int n, m, k, a[maxn], b[maxn], c[maxn], l[maxn], r[maxn];

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++)
        cin >> a[i] >> b[i] >> c[i];
    for(int i = 0; i < 3; i++)
        cin >> l[i] >> r[i];
    for(int i = l[0]; i <= min(l[0] + m, r[0]); i++)
        for(int j = l[1]; j <= min(l[1] + m, r[1]); j++)
            for(int k = l[2]; k <= min(l[2] + m, r[2]); k++){
                int cnt = 0;
                for(int l = 0; l < n; l++)
                    cnt += ((ll) i * a[l] + (ll) j * b[l] - (ll) k * c[l]) % m == 0;
                cerr << cnt << 'n';
                if(cnt == ::k)
                    return cout << i << ' ' << j << ' ' << k << 'n', 0;
             }
    cout << "-1n";
}

HackerEarth Three arrays problem solution

HackerEarth Three arrays problem solution.

Second solution

Leave a Reply

Pages

Practice