EIUASSEMBLY-Assembly line

Assembly line

Given below c++ code is for EIUASSEMBLY spoj or Assembly line spoj.

Hint:- Simple Binary Search Implementation.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 03 June 2016 (Friday) 10:26
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int , int>
#define ll long long
#define mp make_pair
#define pb push_back
bool check(vector<int> &p, vector<int> &m, ll &total_cost, ll level){
    ll total = 0;
    for(int i = 0 ; i < p.size() ; i++){
        ll diff = level - p[i];
        if(diff > 0)
            total += diff*(ll)m[i];
        if(total > total_cost)
            return false;
    }
    return true;
}
ll b_search(vector<int> &p, vector<int> &m , ll total_cost){
    ll low = 0 , high = (LLONG_MAX/10), mid , ans = -1;
    while(low < high){
        mid = (low + high) >> 1;
        if(check(p, m, total_cost , mid)){
            low = mid+1;
            ans = max(mid , ans);
        } else high = mid;
    }
    return ans;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        ll n , total_cost;
        scanf("%lld%lld", &n , &total_cost);
        vector<int> p(n) , m(n);
        for(int i = 0 ; i < n ; i++){
            scanf("%d%d" , &p[i] , &m[i]);
        }
        printf("%lld\n" , b_search(p , m , total_cost));
    }
    return 0;
}

GCD2-GCD2

GCD2

Given below c++ code is for GCD2 Spoj.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 02 June 2016 (Thursday) 11:26
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int mod(char s[], int divider){
    int r = 0;
    for(int i = 0 ;s[i] ; i++){
        r = r*10 + s[i] - 48;
        r = r % divider;
    }
    return r;
}
int gcd(int a , int b){
    return b == 0 ? a : gcd(b , a%b);
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int a;
        char b[259];
        scanf("%d %s",&a , b);
        if(a == 0){
            printf("%s\n" , b);
            continue;
        }
        printf("%d\n", gcd(a , mod(b , a)));
    }
    return 0;
}

INS14A-BSTRING

BSTRING

Given below c++ code is for ins14a spoj or bstring spoj.

Hint :- Think of bringing all one's to it median in windows of 'm' ones.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 18 October 2015 (Sunday) 22:05
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        char s[50009];
        ll m;
        scanf("%lld %s" , &m ,s);
        int n = strlen(s);
        vector<ll> position;
        position.pb(0);
        for(int i = 0 ; i < n ; i++)
            if(s[i] == 49)
                position.pb(i+1);
        ll median = m/2 + 1;
        ll left = 0 , right = 0;
        for(int i = 0 ; i < median ; i++)
            left += position[i];
        for(int i = median + 1 ; i<=m ; i++)
            right += position[i];
        ll ans = right - left + (2*median - m - 1)*position[median];
        int var_median = median;
        for(int i = m+1 , j = 1 ; i < position.size() ;j++, i++){
            left -= position[j];
            left += position[var_median];
            var_median++;
            right -= position[var_median];
            right += position[i];
            ll temp = right - left + (2*median - m - 1)*position[var_median];
            ans = min(ans , temp);
        }
        ans -= (m*m + 2*median*(median - 1) - 2*m*median + m)/2;
        printf("%lld\n", ans);
    }
    return 0;
}

SMILEY1807-1807

1807

Given below c++ code is for smiley1807 spoj or 1807 spoj.

Hint :- This is a basic Dynamic Programming problem , Just use pen and paper you will get the solution.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 11 September 2015 (Friday) 19:56
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009

int main(){
    
    char s[1000009];
    cin>>s;
    int n = strlen(s);
    int arr[4];
    memset(arr , 0 , sizeof arr);
    if(n <=3){
        cout<<0<<endl;
        return 0;
    }
    if(s[0] == '1'){
        arr[0] = 1;
    }
    for(int i = 1 ; i < n ; i++){
        if(s[i] == '1'){
            arr[0] = arr[0] + 1;
        }
        else if(s[i] == '8'){
            if(arr[0] > 0 || arr[1] > 0){
                arr[1] = max(arr[0] , arr[1]) + 1;
            }
        } else if(s[i] == '0'){
            if(arr[1] > 0 || arr[2] > 0){
                arr[2] = max(arr[1] , arr[2]) + 1;
            }
        } else if(s[i] == '7'){
            if(arr[2] > 0 || arr[3] > 0){
                arr[3] = max(arr[2] , arr[3])+1;
            }
        }
    }
    cout<<arr[3]<<endl;
    return 0;
}

TESSER-Finding the Tesserect

Finding the Tesserect

Given below c++ code is for TESSER spoj or Finding the tesserect spoj.

Hint:- Use hashing or suffix array to find pattern in difference string.

#include <bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
ULL hash[100009];
#define MU 123
void preHash(char str[] , int n)
{
    hash[n] = 0;
    for(int i = n-1 ; i>=0 ; i--)
        hash[i] = hash[i+1]*MU + str[i] - 65;
}
void solve(char str[] ,char pattern[] , int n , int m)
{
    ULL phv = 0;//hash value for pattern strings
    ULL multiplier = 1;
    for(int i = m-1 ; i>=0 ; i--){
        phv = phv*MU + pattern[i] - 65;
        multiplier = multiplier*MU;
    }
    preHash(str , n);
    int flag = 0;
    for(int i = 0 ; i < n - m + 1 ; i++)
        if(hash[i] - multiplier*hash[i+m] == phv)
        {
            flag = 1;
            break;
        }
    if(flag)
        printf("YES\n");
    else
        printf("NO\n");
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int arr[n+9];
        for(int i=0 ; i < n ; i++)
            scanf("%d",&arr[i]);
        char str[n+9];
        for(int i = 1 ; i < n ; i++)
            if(arr[i] == arr[i-1])
                str[i-1] = 'E';
            else if(arr[i] > arr[i-1])
                str[i-1] = 'G';
            else
                str[i-1] = 'L';
        n--;
        char pattern[n+9];
        scanf("%s",pattern);
        int m = strlen(pattern);
        solve(str , pattern , n , m);
    }
    return 0;
}

NAJPF-Pattern Find

Pattern Find

given below code is for NAJPF spoj or Pattern Find spoj.

Hint:- Use hashing for string and find pattern (very basic)

#include <bits/stdc++.h>
using namespace std;
#define MU 123
#define ULL unsigned long long
ULL hash[1000009];
void preHash(char str[] , int n)
{
    hash[n] = 0;
    for(int i = n-1 , j = 1 ; i>=0 ; i-- , j++){
        hash[i] = hash[i+1]*MU + str[i] - 97;
    }
}
void solve(char text[] , char pattern[] , int p , int t){
    ULL p_hash = 0 , check , pre = 1;
    for(int i = p-1 ; i>=0 ; i--){
        p_hash = p_hash*MU + pattern[i] - 97;
        pre = pre*MU;
    }
    check = p_hash;
    vector<int> v;
    int flag = 0;
    preHash(text , t);
    for(int i = 0; i < t - p + 1 ; i++ )
        if(hash[i] - pre*hash[i+p] == check){
            flag++;
            v.push_back(i+1);
        }
    if(flag == 0)
        printf("Not Found\n");
    else
    {
        printf("%d\n",flag);
        for(int i = 0 ; i < flag ; i++)
            printf("%d ",v[i]);
        printf("\n");
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        char text[1000009] ,  pattern[1000009];
        scanf("%s%s",text , pattern);
        int n , m ;
        n = strlen(text);
        m = strlen(pattern);
        solve(text , pattern , m , n);
    }
    return 0;
}

OHANISER-Ohani And The Series

Ohani And The Series

Given below code is for OHANISER spoj or Ohani And The Series spoj.

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MOD 1000000007
LL pow_mod(int n)
{
    LL a = 1 , p = 2;
    while(n)
    {
        if(n&1)
            a = (a*p)%MOD;
        p = (p*p)%MOD;
        n>>=1;
    }
    return a;
}
int main()
{
    int t , j = 1;
    cin>>t;
    while(t--)
    {
        LL n;
        cin>>n;
        if(n==1)
        {
            cout<<"Case "<<j<<": "<<1<<endl;
            j++;
            continue;
        }
        if(n == 2)
        {
            cout<<"Case "<<j<<": "<<3<<endl;
            j++;
            continue;
        }
        cout<<"Case "<<j<<": "<<((n+1) * (pow_mod(n-2)))%MOD<<endl;
        j++;
    }
    return 0;
}

SUFEQPRE-Suffix Equal Prefix

Suffix Equal Prefix

Given below code is for SUFEQPRE spoj or suffix equal prefix spoj.

Hint :-> Read Z-function . After that this question is just simple implementation of  Z-function.

#include <bits/stdc++.h>
using namespace std;
int Z_function(char s[] , int n)
{
    int z[n+9] , count = 0;
    memset(z , 0 , sizeof z);
    int l=0,r=0;
    z[0] = n;
    for(int i=1;i<n;i++)
    {
        if(i<=r)
            z[i] = min(r-i+1 , z[i-l]);
        while(i+z[i] < n && s[z[i]] == s[i+z[i]])
            z[i]++;
        if(i+z[i]-1 > r)
            l = i, r = i+ z[i] - 1;
        if(z[i] == n - i)
            count ++;
    }
    return count;
}
int main()
{
    int t , n , j = 1;
    char s[1000009];
    scanf("%d ",&t);
    while(t--)
    {
        gets(s);
        n = strlen(s);
        printf("Case %d: %d\n",j,Z_function(s , n));
        j++;
    }
    return 0;
}

DCEPC206 - Its a Murder!

Its a Murder!

Given below code is for decpc206 spoj or its a murder spoj .

Hint : - > BIT 

#include <bits/stdc++.h>
using namespace std;
#define LL long long 
#define MAX 100001
LL tree[100009];
LL read(int pos)
{
    LL res = 0;
    while(pos)
    {
        res += tree[pos];
        pos -= (pos & -pos);
    }
    return res;
}
void update(int pos , int val)
{
    while(pos<=MAX)
    {
        tree[pos] += val;
        pos +=(pos & -pos);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        int arr[n+9] , hold[n+9] ;
        for(int i = 0; i < n ; i++){
            scanf("%d",&arr[i]);
            hold[i] = arr[i];
        }
        sort(arr,arr+n);
        for(int i = 0; i < n ; i++)
        {
            int pos = lower_bound(arr , arr + n , hold[i]) - arr;
            hold[i] = pos;
        }
        LL sum = 0;
        memset(tree, 0 , sizeof tree);
        for(int i = 0; i < n ; i++)
        {
            sum += read(hold[i]);
            update(hold[i] + 1 , arr[hold[i]]);
        }
        printf("%lld\n",sum);
    }
    return 0;
}