SleepyBrain: July 2015

Friday, July 31, 2015

1112 - Curious Robin Hood

#include<bits/stdc++.h>
using namespace std;
long long arry[100010],segment[400050];
 
void build(long long at, long long L, long long R)
{
    if(L==R)
    {
        segment[at] = arry[L];
        return;
    }
    long long mid = (L+R)/2;
    build(at*2,L,mid);
    build(at*2+1,mid+1,R);
    segment[at] = segment[at*2] + segment[at*2+1];
}
 
void update(long long at, long long L, long long R, long long pos, long long u)
{
    if(L==R)
    {
        segment[at] += u;
        return;
    }
    long long mid = (L+R)/2;
    if(pos <= mid)
        update(at*2,L,mid,pos,u);
    else
        update(at*2+1,mid+1,R,pos,u);
    segment[at] = segment[at*2]+segment[at*2+1];
}
 
long long query(long long at,long long L, long long R, long long l, long long r)
{
    if(r<L || l>R)
        return 0;
    if(L==R)
        return segment[at];
    if(l <= L && r >= R)
        return segment[at];
    long long mid = (L+R)/2;
    long long x = query(at*2, L, mid, l, r);
    long long y = query(at*2+1, mid+1, R, l, r);
    return x + y;
}
 
int main()
{
    //freopen("T - Curious Robin Hood.txt","r",stdin);
    long long T,n,q,a,b,i,c=1;
    scanf("%lld", &T);
    while(T--)
    {
        scanf("%lld %lld", &n, &q);
        for(i=1; i<=n; i++)
            scanf("%lld", &arry[i]);
 
        build(1,1,n);
        printf("Case %lld:\n",c++);
        for(i=1; i<=q; i++)
        {
            scanf("%lld",&a);
            if(a==1)
            {
                scanf("%lld",&b);
                update(1,1,n,b+1,-arry[b+1]);
                printf("%lld\n",arry[b+1]);
                arry[b+1] = 0;
            }
            else if(a==2)
            {
                scanf("%lld %lld",&a,&b);
                update(1,1,n,a+1,b);
                arry[a+1] += b;
            }
            else
            {
                scanf("%lld %lld", &a, &b);
                printf("%lld\n",query(1,1,n,a+1,b+1));
            }
        }
    }
    return 0;
}

1082 - Array Queries

#include<bits/stdc++.h>
using namespace std;
 
long long arry[100010],segment[400050];
 
 
void build(long long at, long long L, long long R)
{
    if(L==R)
    {
        segment[at] = arry[L];
        return;
    }
    long long mid = (L+R)/2;
    build(at*2,L,mid);
    build(at*2+1,mid+1,R);
    segment[at] = segment[at*2] > segment[at*2+1]?segment[at*2+1]:segment[at*2];
}
 
long long query(long long at,long long L, long long R, long long l, long long r)
{
    if(r<L || l>R)
        return 1000000;
    if(L==R)
        return segment[at];
    if(l <= L && r >= R)
        return segment[at];
    long long mid = (L+R)/2;
    long long x = query(at*2, L, mid, l, r);
    long long y = query(at*2+1, mid+1, R, l, r);
    return x > y? y:x;
}
 
int main()
{
    //freopen("L - Array Queries.txt", "r",stdin);
    long long T,n,q,i,a,b,c=1;
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld %lld", &n, &q);
        for(i=1; i<=n; i++)
            scanf("%lld",&arry[i]);
        build(1,1,n);
        printf("Case %lld:\n",c++);
        for(i=1; i<=q; i++)
        {
            scanf("%lld %lld", &a, &b);
            printf("%lld\n",query(1,1,n,a,b));
        }
    }
    return 0;
}

Thursday, July 30, 2015

1231 - Coin Change (I)

#include<bits/stdc++.h>
using namespace std;
 
#define mod 100000007
 
int dp[55][1010],coin[55],c[55],n,k,T;
 
int call(int i, int amount)
{
    if(i >= n)
    {
        if(amount == k)
            return 1;
        else
            return 0;
    }
 
    if(amount > k)
        return 0;
    if(amount == k)
        return 1;
 
    if(dp[i][amount] != -1)
        return dp[i][amount];
 
    int ret1=0, ret2=0;
 
    for(int a=1; a<=c[i]; a++)
    {
        if(amount+coin[i]*a <= k)
            ret1 += call(i+1,amount+coin[i]*a)%mod;
        else
            break;
    }
    ret2 = call(i+1,amount)%mod;
 
    return dp[i][amount] = (ret1 + ret2)%mod;
}
 
int main()
{
    int i,C=1;
    //freopen("1231 - Coin Change (I).txt", "r", stdin);
    cin >> T;
    while(T--)
    {
        memset(dp, -1, sizeof(dp));
        cin >> n >> k;
        for(i=0; i<n; i++)
            cin >> coin[i];
        for(i=0; i<n; i++)
            cin >> c[i];
        cout << "Case " << C++ << ": " << call(0,0) << endl;
     }
    return 0;
}

1044 - Palindrome Partitioning

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int T,i,j,l,n,C=1;
    string str;
    cin >> T;
    while(T--)
    {
        cin >> str;
        n = str.length();
        int c[n];
        bool p[n][n];
        for(i=0; i<n; i++)
            p[i][i] = true;
        for(l=2; l<=n; l++)
            for(i=0; i<n-l+1; i++)
            {
                j = i+l-1;
                if(l == 2)
                    p[i][j] = (str[i] == str[j]);
                else
                    p[i][j] = (str[i] == str[j] && p[i+1][j-1]);
            }
 
        for(i=0; i<n; i++)
        {
            if(p[0][i] == true)
                c[i] = 0;
            else
            {
                c[i] = INT_MAX;
                for(j=0; j<i; j++)
                {
                    if((1+c[j]) < c[i] && p[j+1][i] == true)
                        c[i] = 1+c[j];
 
                }
            }
        }
        cout << "Case " << C++ << ": " << c[n-1]+1 << endl;
 
    }
    return 0;
}

1038 - Race to 1 Again

#include<bits/stdc++.h>
using namespace std;
vector<int> divisors[100002];
 
void Divisors(int n)
{
    int i,j;
    for(i = 1; i<=n; i++)
        for(j=i; j<=n; j+=i)
            divisors[j].push_back(i);
}
 
int main()
{
    long long T,N,c=1;
    Divisors(100010);
    cin >> T;
    while(T--)
    {
        cin >> N;
        double store[100010];
        long  long l;
        l = divisors[N].size();
        for(long long i=0; i<l; i++)
        {
            if(divisors[N][i] == 1)
                store[divisors[N][i]] = 0;
            else if(divisors[divisors[N][i]].size() == 2)
                store[divisors[N][i]] = 2.000;
            else
            {
                store[divisors[N][i]] = divisors[divisors[N][i]].size();
                for(int j=0; j<divisors[divisors[N][i]].size()-1; j++)
                    store[divisors[N][i]] += store[divisors[divisors[N][i]][j]];
                store[divisors[N][i]] /= divisors[divisors[N][i]].size()-1;
            }
        }
        cout << "Case " << c++ << ": ";
        printf("%.10lf\n",store[divisors[N][l-1]]);
    }
    return 0;
}

1326 - Race

#include<bits/stdc++.h>
using namespace std;
#define mx 1005
#define mod 10056
int dp[mx][mx],result[mx];
 
void calculate()
{
    int i,j;
    dp[1][1] = 1;
    dp[2][1] = 1;
    dp[2][2] = 2;
    for(i=3; i<mx; i++)
    {
        dp[i][1] = 1;
        for(j=2; j<i; j++)
            dp[i][j] = ((dp[i-1][j]+dp[i-1][j-1])*j)%mod;
        dp[i][i] = ((dp[i-1][j-1])*i)%mod;
    }
 
    for(i=1; i<mx; i++)
    {
        result[i] = 0;
        for(j=1; j<=i; j++)
            result[i] = (result[i] + dp[i][j])%mod;
    }
}
 
 
int main()
{
    int T,n,c=1;
    calculate();
    cin >> T;
    while(T--)
    {
        cin >> n;
        cout << "Case " << c++ << ": " << result[n] << endl;
    }
    return 0;
}

1140 - How Many Zeroes?

#include<bits/stdc++.h>
using namespace std;
 
long long calculate(long long a)
{
    long long len,st[100],l=1,n=a;
 
    while(1)
    {
        if(a < 10)
        {
            st[l++] = a;
            break;
        }
        st[l++] = a%10;
        a /= 10;
    }
    long long res = 0;
    for(int i=1; i<l; i++)
    {
        if(i==1 || st[i] != 0)
        {
            res += pow(10,i-1) * floor(n/pow(10,i));
        }
 
        else
        {
            res += (pow(10,i-1) * (floor(n/pow(10,i))-1))+n+1-pow(10,i)*floor(n/pow(10.00,i));
        }
    }
    return res;
}
 
int main()
{
    long long T,i,k,m,n,l,result1,result2,c=1;
    cin >> T;
    while(T--)
    {
        cin >> m >> n;
        result1 = calculate(m-1);
        result2 = calculate(n);
        cout << "Case " << c++ << ": " << result2-result1 << endl;
    }
    return 0;
}

1027 - A Dangerous Maze

#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b)
{
    return (b == 0) ? a : gcd(b, a%b);
}
 
int main()
{
    long long T,n,i,sum,nValue,x,c=1;
    cin >> T;
    while(T--)
    {
        cin >> n;
        sum = 0;
        nValue = 0;
        for(i=0; i<n; i++)
        {
            cin >> x;
            sum += abs(x);
            if(x < 0)
                nValue++;
        }
        if(n == nValue)
        {
            cout << "Case " << c++ << ": inf" << endl;
            continue;
        }
        x = gcd(sum, n-nValue);
        if(n != nValue)
            cout << "Case " << c++ << ": " << sum/x << "/" << (n-nValue)/x << endl;
    }
    return 0;
}

1005 - Rooks

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    unsigned long long T,n,k,ans,c=1,i;
    cin >> T;
 
    while(T--)
    {
        cin >> n >> k;
        ans = 1;
        if(n<k)
        {
            cout << "Case " << c++ << ": 0" << endl;
            continue;
        }
        for(i=1; i<=k; i++)
        {
            ans = ans*n*n/i;
            n -= 1;
        }
        cout << "Case " << c++ << ": " << ans << endl;
 
    }
    return 0;
}