Saturday 9 September 2017

Identifying tea (UVa 13012, UVaLive 7211, Regionals 2015 >> Latin America) 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
///     Raihan Ruhin (username : raihanruhin)
///     Online resume: https://raihanruhin.github.io

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);

    int tc, n, x, cnt;
    //cin>>tc;
    while(cin>>n)
    {
        cnt=0;
        for(int i=0;i<5;i++)
        {
            cin>>x;
            if(x==n) cnt++;
        }
        cout<< cnt <<endl;
    }
    return 0;
}
at 360 comments:
Labels: , ,

Thursday 24 August 2017

Maximum sum increasing subsequence 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
///     Raihan Ruhin (username: raihanruhin)
///     Resume: https://raihanruhin.github.io

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int dp[102][102], arr[102], n;

int func(int now, int last)
{
    if(now>n) return 0;

    int &ret = dp[now][last];
    if(ret!=-1) return ret;
    ret=0;

    ret = func(now+1, last);
    if(arr[last]<arr[now])
        ret = max(ret, func(now+1, now)+arr[now]);

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);

    int tc, kk=1, x;
    cin>>tc;

    while(tc--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>arr[i];
        SET(dp);
        cout<<func(0, 0)<<endl;
        //cout<<"Case "<<kk++<<": "<< <<"\n";
    }
    return 0;
}
at No comments:
Labels:

Equilibrium point 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
///     Raihan Ruhin (username: raihanruhin)
///     Resume: https://raihanruhin.github.io

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);

    int tc, kk=1, n, x, consecutive_sum[102];
    bool found;
    consecutive_sum[0]=0;
    cin>>tc;

    while(tc--)
    {
        found =false;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            consecutive_sum[i] = consecutive_sum[i-1] + x;
        }
        for(int i=1;i<=n;i++)
        {
            if(consecutive_sum[n]-consecutive_sum[i] == consecutive_sum[i-1])
            {
                found =true;
                cout<<i<<endl;
                break;
            }
        }
        if(!found)
            cout<<-1<<endl;
        //cout<<"Case "<<kk++<<": "<< <<"\n";
    }
    return 0;
}
at 1 comment:
Labels:

Sort an array of 0s, 1s and 2s 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
///     Raihan Ruhin (username: raihanruhin)
///     Resume: https://raihanruhin.github.io

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);

    int tc, kk=1, n, x;
    cin>>tc;

    while(tc--)
    {
        cin>>n;
        int zero=0, one=0, two=0;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            if(!x) zero++;
            else if(x==1) one++;
            else two++;
        }
        for(int i=0;i<n;i++)
        {
            if(i) cout<<" ";
            if(zero)
            {
                cout<<0;
                zero--;
            }
            else if(one)
            {
                cout<<1;
                one--;
            }
            else
            {
                cout<<2;
                two--;
            }
        }
        cout<<endl;
        //cout<<"Case "<<kk++<<": "<< <<"\n";
    }
    return 0;
}
at No comments:
Labels:

Subarray with given sum 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
///     Raihan Ruhin (username: raihanruhin)
///     Resume: https://raihanruhin.github.io

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);

    int tc, kk=1, n, x, arr[102], s;
    cin>>tc;

    while(tc--)
    {
        cin>>n>>s;
        int i;
        for(i=1;i<=n;i++)
            cin>>arr[i];
        arr[0]=0;
        int st = 1, x=0;
        bool found = false;
        i=1;
        while(i<=n || x>s)
        {
            if(x>s)
            {
                x -= arr[st];
                st++;
                i--;
            }
            else if(x<s)
            {
                x += arr[i];
            }
            if(x==s)
            {
                found=true;
                break;
            }
            i++;
        }
        if(found)
            cout<<st<<" "<<i<<endl;
        else 
            cout<<-1<<endl;
        //cout<<"Case "<<kk++<<": "<< <<"\n";
    }
    return 0;
}
at No comments:
Labels:

Saturday 19 August 2017

Missing number in array 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
///     Raihan Ruhin (username : raihanruhin)
///     Online resume: https://raihanruhin.github.io

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);

    int tc, n, x;
    map<int, bool>mp;
    cin>>tc;

    while(tc--)
    {
        cin>>n;
        for(int i=1; i<n; i++)
        {
            cin>>x;
            mp[x]=true;
        }
        for(int i=1; i<=n; i++)
            if(!mp[i])
            {
                cout<< i <<endl;
                break;
            }
        mp.clear();
    }
    return 0;
}
at No comments:
Labels:

Friday 18 August 2017

Kadane's Algorithm 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
///     Raihan Ruhin (username : raihanruhin)
///     Online resume: https://raihanruhin.github.io

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc, n, arr[1002], tmp, mx, ans;
    cin>>tc;
    while(tc--)
    {
        cin>>n;
        tmp = 0;
        ans = 0;
        mx = -1e9; //single max element of the array
        for(int i=0; i<n; i++)
        {
            cin>>arr[i];
            mx = max(mx, arr[i]);
            tmp += arr[i];
            tmp = max(tmp, 0);
            ans = max(ans, tmp);
        }
        if(ans==0) cout<<mx<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}
at No comments:
Labels:

Monday 10 July 2017

Army Buddies (UVa 12356, UVaLive 5789, Regionals 2011 >> Latin America) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int l[MX], r[MX];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc,kk=1, n, q, lf, rg;

    while(cin>>n>>q)
    {
        if(!n && !q) return 0;
        for(int i=1;i<=n;i++)
            l[i]=i-1, r[i]=i+1;
        r[n]=0;
        while(q--)
        {
            cin>>lf>>rg;
            l[r[rg]] = l[lf];
            r[l[lf]] = r[rg];
            if(l[lf]) cout<<l[lf]<<" ";
            else cout<<"* ";
            if(r[rg]) cout<<r[rg]<<"\n";
            else cout<<"*\n";
        }
        cout<<"-\n";
    }
    return 0;
}
at 1 comment:
Labels: , ,

Sunday 18 June 2017

Almost Shortest Path (UVa 12144, UVaLive 4210, Regionals 2008 >> Latin America - South America) 


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 502

struct Z
{
    int v, cost;
    bool operator < (const Z &p) const
    {
        return p.cost<cost;
    }
};

Z z, z2;

int shortest[MX], forbidden[MX][MX];
vector<Z> adj[MX];
vector<int> parent[MX];
priority_queue<Z>pq;

int dijkstra(int src, int dst, int node)
{
    for(int i=0; i<node; i++)
        shortest[i]=1e9;

    z.v = src;
    z.cost = 0;
    pq.push(z);
    shortest[src]=0;

    while(!pq.empty())
    {
        z = pq.top();
        pq.pop();

        int l = adj[z.v].size();

        for(int i=0; i<l; i++)
        {
            z2 = adj[z.v][i];
            if(forbidden[z.v][z2.v]==1) continue;
            if(shortest[z2.v]>shortest[z.v]+z2.cost)
            {
                parent[z2.v].clear();
                parent[z2.v].push_back(z.v);
                z2.cost = shortest[z2.v]= shortest[z.v]+z2.cost;
                pq.push(z2);
            }
            else if(shortest[z2.v]==shortest[z.v]+z2.cost)
                parent[z2.v].push_back(z.v);

        }
    }
    return shortest[dst];
}

void removeEdge(int src, int dst)
{
    if(dst==src) return;
    for(int i=0;i<parent[dst].size();i++)
    {
        forbidden[ parent[dst][i] ][dst] = 1;
        removeEdge(src, parent[dst][i]);
    }
return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc,kk=1, node, edge, u, v, cost, src, dst;

    while(cin>>node>>edge && node)
    {
        cin>>src>>dst;


        for(int i=0; i<edge; i++)
        {
            cin>>u>>v>>cost;

            z.v = v;
            z.cost = cost;
            adj[u].push_back(z);
        }

        int tmp = 1e9;
        int mn = dijkstra(src, dst, node); //initial

        if(mn<1e9)
        {
            removeEdge(src, dst); //remove edges of shortest
            tmp = dijkstra(src, dst, node); //second time
        }
        if(tmp==1e9) tmp = -1;
        cout<<tmp<<endl;


        CLR(forbidden);
        for(int i=0;i<node;i++)
        {
            adj[i].clear();
            parent[i].clear();
        }
    }
    return 0;
}
at 2 comments:
Labels: , ,

Thursday 8 June 2017

Reverse Integer (LeetCode) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int reverse(int x) {
        
        bool flag = false;
        if(x<0)
        {
            flag = true;
            x*=-1;
        }
        int rev = 0;
        while(x)
        {
            if((rev*10)/10 != rev) return 0; // checking overflow
            rev = rev*10 + x%10;
            x/=10;
        }
        
        if(flag) rev*=-1;
        
        return rev;
    }
};
at No comments:
Labels:

Median of Two Sorted Arrays (LeetCode) 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int l1 = nums1.size();
        int l2 = nums2.size();
        if(l1>l2)
            return findMedianSortedArrays(nums2, nums1);
        int k = (l1+l2-1)>>1;
        int lft = 0, rgt = l1;
        while(lft<rgt)
        {
            int md = (lft+rgt)>>1;
            if(nums1[md]<nums2[k-md])
                lft = md+1;
            else rgt = md;
        }
        double x, y;
        
        if(lft>0 && (k-lft)>=0) 
            x = max(nums1[lft-1], nums2[k-lft]);
        else if(lft>0)
            x = nums1[lft-1];
        else if(k-lft>=0)
            x = nums2[k-lft];
            
        if((l1+l2) & 1) return x; //total odd size, single median
        
        if(lft<l1 && (k-lft+1)<l2)
            y = min(nums1[lft], nums2[k-lft+1]);
        else if(lft<l1)
            y = nums1[lft];
        else if((k-lft+1)<l2)
            y = nums2[k-lft+1];
        return (x+y)/2.0;
        
    }      
    
};
at No comments:
Labels:

Sunday 4 June 2017

Football (UVa 12673, UVaLive 6530, Regionals 2013 >> Latin America) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

struct match{
    int score, receive;
    bool operator < (const match &m) const{
        return m.score-m.receive < score-receive ;
    }
};

match mth[MX];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc,kk=1, n, g;
    //cin>>tc;
    while(cin>>n>>g)
    {
        for(int i=0;i<n;i++)
            cin>>mth[i].score>>mth[i].receive;
        sort(mth, mth+n);

        int point = 0;

        for(int i=0;i<n;i++)
        {
            //cout<<mth[i].score<<" "<<mth[i].receive<<endl;
            if(mth[i].score>mth[i].receive)
                point += 3;
            else if(mth[i].score==mth[i].receive)
            {
                if(g>0)
                {
                    point += 3;
                    g--;
                }
                else point += 1;
            }
            else if(mth[i].score<mth[i].receive)
            {
                if(g>(mth[i].receive-mth[i].score))
                {
                    point += 3;
                    g= g-(mth[i].receive-mth[i].score)-1;
                }
                else if(g==(mth[i].receive-mth[i].score))
                {
                    point += 1;
                    g= g-(mth[i].receive-mth[i].score);
                }
                
            }
        }
        cout<<point<<endl;
    }
    return 0;
}
at No comments:
Labels: , ,

Saturday 3 June 2017

Proving Equivalences (UVa 12167, UVaLive 4287, Regionals 2008 >> Europe - Northwestern) 


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

vector<int>adj[20002];
stack<int>stk;

int t, lo[20002], tim[20002], vis[20002], sccrm[20002], scc, done;

void tarjan_scc(int u)
{
    t++;
    vis[u]=1;
    lo[u]=tim[u]=t;
    stk.push(u);

    for(int i=0;i<adj[u].size();i++)
    {
        int v = adj[u][i];
        if(!vis[v])
        {
            tarjan_scc(v);
            lo[u]=min(lo[u], lo[v]);
        }
        else if(vis[v]==1)
            lo[u]=min(lo[u], tim[v]);
    }

    if(lo[u]==tim[u])
    {
        scc++;
        do{
            done = stk.top();
            stk.pop();
            sccrm[done]=scc;
            vis[done]=2;
        }while(done!=u);
    }
return;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int kk=1, tc, n, m, u, v;
    string s;
    cin>>tc;
    while(tc--)
    {
        cin>>n>>m;
        t=scc=0;
        while(!stk.empty()) stk.pop();
        for(int i=1;i<=n;i++)
        {
            adj[i].clear();
            vis[i]=0;
        }

        while(m--)
        {
            cin>>u>>v;
            adj[u].push_back(v);
        }
        for(int i=1;i<=n;i++)
            if(!vis[i])
                tarjan_scc(i);

        // checking zero indegree and outdegree of scc
        bool hasIndegree[scc+2], hasOutdegree[scc+2];
        CLR(hasIndegree);
        CLR(hasOutdegree);

        for(int i=1;i<=n;i++)
            for(int j=0;j<adj[i].size();j++)
                if(sccrm[i]!=sccrm[adj[i][j]]) //not in same scc
                {
                    hasIndegree[sccrm[i]]=true;
                    hasOutdegree[sccrm[adj[i][j]]]=true;
                }
        int zeroIndgree=0, zeroOutdegree=0;
        for(int i=1;i<=scc;i++)
        {
            if(!hasIndegree[i]) zeroIndgree++;
            if(!hasOutdegree[i]) zeroOutdegree++;
        }
        if(scc==1) cout<<0<<endl;
        else cout<<max(zeroIndgree, zeroOutdegree)<<endl;
        //cout<<"Case "<<kk++<<": "<< <<"\n";
    }

    return 0;
}
at No comments:
Labels: , ,

Thursday 1 June 2017

Interval Product (UVa 12532, UVaLive 6139, Regionals 2012 >> Latin America) 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

int z1, z2, node[MX*4];

void insert(int idx, int st, int ed, int s, int e, int val)
{
    if(st==s && ed==e)
    {
        if(val>0) node[idx]=1;
        else if(val<0) node[idx]=-1;
        else node[idx]=0;
        return;
    }
    int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1;
    if(e<=mid) insert(lft, st, mid, s, e, val);
    else if(s>mid) insert(rgt, mid+1, ed, s, e, val);
    else
    {
        insert(lft, st, mid, s, mid, val);
        insert(rgt, mid+1, ed, mid+1, e, val);
    }
    node[idx] = node[lft] * node[rgt];
    return;
}

int query(int idx, int st, int ed, int s, int e)
{
    if(st==s && ed==e)
    {
        return node[idx];
    }
    int mid=(st+ed)>>1, lft=idx<<1, rgt=lft|1;
    if(e<=mid) return query(lft, st, mid, s, e);
    else if(s>mid) return query(rgt, mid+1, ed, s, e);
    else return query(lft, st, mid, s, mid)*query(rgt, mid+1, ed, mid+1, e);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc,kk=1, n, q, x, y;
    char c;
    string s;
    while(cin>>n>>q)
    {
        for(int i=1;i<=n*4;i++)
            node[i]=1;

        for(int i=1; i<=n; i++)
        {
            cin>>x;
            insert(1, 1, n, i, i, x);
        }
        while(q--)
        {
            cin>>c>>x>>y;
            if(c=='C')
                insert(1, 1, n, x, x, y);
            else
            {
                z1 = query(1, 1, n, x, y);
                //cout<<z1.pos<<" "<<z1.neg<<" "<<z1.zero<<endl;
                if(z1==0)
                    cout<<"0";
                else if(z1<0)
                    cout<<"-";
                else cout<<"+";
            }
        }
        cout<<endl;
    }
    return 0;
}
at No comments:
Labels: , ,

Monday 24 April 2017

Tidy Numbers (Codejam Qualification Round 2017, Problem B) 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

#define READ freopen("B-large-practice.in", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)

vector<long long>tidy;

void precal(int sz, long long number)
{
    if(sz==18)
    {
        tidy.push_back(number);
        return;
    }
    int lastDigit = number%10;
    for(int i=lastDigit;i<=9;i++)
        precal(sz+1, number*10+i);
return;
}

int main()
{
    READ;
    WRITE;
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc,kk=1;
    long long n;
    string s;
    cin>>tc;
    precal(0, 0);
    while(tc--)
    {
        cin>>n;
        auto it = upper_bound(tidy.begin(), tidy.end(), n);
        it--;
        cout<<"Case #"<<kk++<<": "<< *it <<"\n";
    }
    return 0;
}
at No comments:
Labels:

Oversized Pancake Flipper ( Codejam Qualification Round 2017, Problem A) 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva ), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

#define READ freopen("A-large-practice.in", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)

int minFlip(string s, int k)
{
    int n = s.length();
    int cnt = 0;
    for(int i=0;i<=n-k;i++)
    {
        if(s[i]=='-')
        {
            cnt++;
            for(int j=i;j<i+k;j++)
                s[j] = s[j]=='-' ? s[j]='+' : s[j]='-';
        }
    }
    for(int i=n-1;i>n-k;i--)
        if(s[i]!='+')
            return -1;
return cnt;
}

int main()
{
    READ;
    WRITE;
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc,kk=1, n, k;
    string s;
    cin>>tc;
    while(tc--)
    {
        cin>>s;
        cin>>k;
        n = minFlip(s, k);
        if(n==-1)
            cout<<"Case #"<<kk++<<": IMPOSSIBLE\n";
        else cout<<"Case #"<<kk++<<": "<< n <<"\n";
    }
    return 0;
}
at No comments:
Labels:
Subscribe to: Posts (Atom)