AMR10F - Cookies Piles | Spoj Solution

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int T;

    int n,a,d;

    cin>>T;

    while (T--)

    {

    scanf("%d %d %d",&n,&a,&d);

    cout<<n*a+n*(n)/2*(d)<<endl;

    }

    return 0;

}

Lightoj-1387 .cpp file

#include <stdio.h>
#include <string.h>

int main ()
{
    int t,s=0,d=0,l,i=1;
    char a [100];
    scanf ("%d", &t);
    while ( t--)
    { scanf("%d",&l);
    getchar();
    s=0;
    printf("Case %d:\n",i++);
        while(l--)
     {
        scanf ("%s", a);
        if (strcmp (a, "donate")==0)
        {
            scanf ("%d", &d);
            s += d;
        }
        else if(strcmp(a,"report")==0)
        printf ("%d\n",s);
    }
    }

    return 0;

}

Lightoj-1353 .cpp file

#include<stdio.h>
#include<math.h>
int binary(long bin)
{
    int reminder,sum=0,h=0;
    while(bin!=0)
    {
        reminder=bin%10;
        bin/=10;
        sum+=reminder*pow(2,h++);
    }
    return sum;


}

int main()
{

    int i,a[4],test,j,h,reminder,sum;
    long b[4];
    scanf("%d",&test);
    for(i=1; i<=test; i++)
    {
        scanf("%d.%d.%d.%d",&a[0],&a[1],&a[2],&a[3]);
        scanf("%ld.%ld.%ld.%ld",&b[0],&b[1],&b[2],&b[3]);
        b[0]=binary(b[0]);
        b[1]=binary(b[1]);
        b[2]=binary(b[2]);
        b[3]=binary(b[3]);


        if(a[0]==b[0]&&a[1]==b[1]&&a[2]==b[2]&&a[3]==b[3])
        {
            printf("Case %d: Yes\n",i);
        }
        else
        {
            printf("Case %d: No\n",i);
        }
    }

    return 0;
}

Lightoj-1281 .cpp file

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <utility>

#define SIZE 5005
#define INT_MAX 2000000000
#define MOD 20071027
#define clr(a) memset(a, 0, sizeof a)
#define reset(a) memset(a, -1, sizeof a)

#define BOUNDARY(i, j) ((i >= 0 && i < row) && (j >= 0 && j < column))

#define max3(x, y, z) max(max(x, y), max(y, z))

using namespace std;

int n, m, row, column;

struct Node
{
int n;
int cost;
Node(){}
Node(int n, int cost) {this->n = n; this->cost = cost;}
bool operator < (const Node &node) const {return cost > node.cost;}
};

vector<Node> adj[SIZE];
bool visited[SIZE];
int weight[SIZE];
int weight2[SIZE];
int minWeight[SIZE];
bool back[SIZE];

int dijkstra(int start, int end)
{
priority_queue<Node> q;
q.push(Node(start, 0));
clr(visited);
reset(weight);
reset(weight2);
clr(back);
weight[start] = 0;
Node node, temp;

for(int i = 1; i <= n; i++)
{
minWeight[i] = INT_MAX;
for(int j = 0; j < adj[i].size(); j++)
minWeight[i] = min(minWeight[i], 2*adj[i][j].cost);
}

while(!q.empty())
{
node = q.top();
q.pop();

if(visited[node.n])
{
if(weight[node.n] < node.cost && (weight2[node.n] == -1 || weight2[node.n] >= node.cost))
weight2[node.n] = node.cost;
else
continue;
}
else visited[node.n] = true;

for(int i = 0; i < adj[node.n].size(); i++)
{
temp = adj[node.n][i];
if(weight[temp.n] == -1 || weight[temp.n] > node.cost + temp.cost)
{
q.push(Node(temp.n, node.cost + temp.cost));
weight2[temp.n] = weight[temp.n];
weight[temp.n] = node.cost + temp.cost;
}
else if(weight2[temp.n] == -1 || weight2[temp.n] > node.cost + temp.cost)
{
if(weight[temp.n] != node.cost + temp.cost)
q.push(Node(temp.n, node.cost + temp.cost));
//printf("--------------\n");
}
}

if(!back[node.n])
{
q.push(Node(node.n, weight[node.n] + minWeight[node.n]));
back[node.n] = true;
}
}

return weight2[end];
}

int main()
{
//freopen("input.txt", "r", stdin);

int i, j, k, l;
int x, y;
int tc, t;

scanf("%d", &tc);

for(t = 1; t <= tc; t++)
{
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++)
adj[i].clear();

for(i = 0; i < m; i++)
{
scanf("%d %d %d", &x, &y, &l);
adj[x].push_back(Node(y, l));
adj[y].push_back(Node(x, l));
}

int result = dijkstra(1, n);

printf("Case %d: %d\n", t, result);
}

return 0;
}

Lightoj-1255 .cpp file

#include <bits/stdc++.h>
using namespace std;
char str[1100000];
char s[1100000];
int b[1100000];

void p(char *s)
{
    const int m = strlen(s);
    int i = 0, j = -1;

    b[i] = -1;
    while(i < m)
    {
        while(j >= 0 && s[i] != s[j])
            j = b[j];

i++;
        j++;
        b[i] = j;
    }
}

int k(char *str, char *s)
{
    int i=0, j=0, c= 0;
    const int n = strlen(str);
    const int m = strlen(s);

p(s);
    while (i<n)
    {
        while (j>=0 && str[i]!=s[j])
            j=b[j];

        i++;
        j++;

        if (j==m)
        {
            c++;
            j=b[j];
        }
    }
    return c;
}

int main()
{
int t, i;
cin>>t;
getchar();
for(i = 0; i <t; i++)
{
gets(str);
gets(s);

printf("Case %d: %d\n", i + 1, k(str, s));
}

return 0;
}

Lightoj-1231 .cpp file

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

const int m= 100000007;

int dp[21][1001], coin[50], cnt[50];

int main()
{
    int test, n, i, j, k, c;
    cin>>test;
     long cs=1;
    while(test--)
    {

        cin>>n>>k;
        for(i = 0; i < n; i++) cin>>coin[i];
        for(i = 0; i < n; i++) cin>>cnt[i];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for(i = 0; i < n; i++)
        {
            for(j = coin[i]; j <= k; j++)
            {
                for(c = 1; c <= cnt[i]; c++)
                {
                    dp[c][j] += dp[c-1][j-coin[i]];
                    if(dp[c][j] >= m) dp[c][j] %= m;
                }
            }
            for(j = coin[i]; j <= k; j++)
            {
                for(c = 1; c <= cnt[i]; c++)
                {
                    dp[0][j] += dp[c][j];
                    if(dp[0][j] >= m) dp[0][j] %= m;
                    dp[c][j] = 0;
                }
            }
        }
        printf("Case %ld: %d\n", cs++, dp[0][k]);
    }
    return 0;
}

Lightoj-1227 .cpp file

#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    long n,p,q,c,i,t,a[20000],d=0;
    scanf("%ld",&t);
    while(t--)
    {
        scanf("%ld%ld%ld",&n,&p,&q);
        for(i=0;i<n;i++)
            scanf("%ld",&a[i]);
        sort(a,a+n);
        c=0;
        for(i=0;i<min(p,n);i++)
        {
            q-=a[i];
            if(q>=0) c++;
        }
        printf("Case %ld: %ld\n",++d,c);
    }
    return 0;
}

Lightoj-1225 .cpp file

#include<stdio.h>
int main()
{
    long long a,n,m,p,i;
    scanf("%lld",&n);
    for( i=1;i<=n;i++)
    {
        p=0;
        scanf("%lld",&a);
       m=a;
       while(m!=0)
       {
           p=p*10+m%10;
           m/=10;
       }
       if(a==p) printf("Case %d: Yes\n",i);
       else  printf("Case %d: No\n",i);
    }
   return 0;
}

Lightoj-1214 .cpp file

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

int main() {
    long int t;
    cin >> t;
    long int i, j,len, b, d,k;
    string a;

    for (i=1; i<=t; i++) {
        cin>>a;
        cin >> b;
        d = 0;
        if (a[0]=='-') j=1;
        else j=0;
        len = a.size();
        for (; j<len; j++) {


            d = d*10 + (a[j]-'0');
            d = d%b;
        }

        cout << "Case " << i << ": ";
        if (d) cout << "not divisible" << endl;
        else cout << "divisible" << endl;

    }
    return 0;
}

Lightoj-1212 .cpp file

#include<bits/stdc++.h>
using namespace std;
int main()
{
    map<string,int>mp;
    mp["pushLeft"]=1;
    mp["pushRight"]=2;
    mp["popLeft"]=3;
    mp["popRight"]=4;
    int t;
    cin>>t;
    int co=1;
    while(t--)
    {   cout<<"Case "<<co++<<":"<<endl;
        deque<int>q;
        int n,m;
        cin>>n>>m;

        for(int i=0; i<m; i++)
        {
            string s;
            int a;
            cin>>s;
            if(mp[s])
            {
                if( mp[s]==1)
                { cin>>a;
                    if(n==q.size())
                        cout<<"The queue is full"<<endl;
                    else q.push_front(a),cout<<"Pushed in left: "<<a<<endl;
                    //  break;
                }
                else if(mp[s]==2)
                {
                    cin>>a;
                    if(n==q.size())
                        cout<<"The queue is full"<<endl;
                    else q.push_back(a),cout<<"Pushed in right: "<<a<<endl;
                    // break;
                }
                else if(mp[s]== 3)
                {
                    if(q.empty())
                        cout<<"The queue is empty"<<endl;
                    else
                    {
                        //int m=;
                        cout<<"Popped from left: "<<q.front()<<endl;
                        q.pop_front();
                    }
                    // break;
                }
                if(mp[s]==4)
                {
                    if(q.empty())
                        cout<<"The queue is empty"<<endl;
                    else
                    {
                        //int l=;
                        cout<<"Popped from right: "<<q.back()<<endl;
                        q.pop_back();
                    }
                }
                // break;
                //default:
                //break;
            }
        }

    }

    return 0;
}

Lightoj-1185 .cpp file

#include<stdio.h>
int main()
{
    unsigned long int n;
    int i,c,b[1000],d,k,s;
    scanf("%lu",&k);
    while(k--)
    {
        scanf("%lu",&n);
        d=0;
        //if(n==0)
       // break;
        i=0;s=0;
        while(n!=0)
        {
            b[i]=n%2;
            n/=2;
            s=s+b[i];
            i++;
        }


        if(s%2==0)
        printf("Case %d: even\n",++d);
        else printf("Case %d: odd\n",++d);

    }
    return 0;
}

Lightoj-1182 .cpp file

#include<stdio.h>
int main()
{
    int a,n,c[10000],i,sum,m,z;
    while((scanf("%d",&m))==1)
    {
        for(z=1;z<=m;z++)
        {
            scanf("%d",&n);
            sum=0;
            for(i=0;n>0;i++)
            {
                 c[i]=n%2;
                 n=n/2;
                 sum=sum+c[i];
            }
            if(sum%2==0)
                printf("Case %d: even\n",z);
            else
                printf("Case %d: odd\n",z);
        }
    }
    return 0;
}

Lightoj-1146 .cpp file

///    Md.ASADUZZAMAN
///    Dept of ICT
///    MBSTU
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

#define fr(i,a,b) for(int i=(a);i<(b);i++)
#define rfr(i,a,b) for(int i=(b-1);i>=(a);i--)
#define freach(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)


#define PINF INT_MAX
#define MINF INT_MIN
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define mset(a,c) memset(a,c,sizeof a)
#define clr(a) memset(a,0,sizeof a)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>
#define psi pair<sting,int>
#define pis pair<int,string>
#define ff first
#define ss second
#define vs vector<string>
#define vi vector<int>
#define vll vector<long long>
#define vpi vector<pair<int,int> >
#define vpl vector<pair<long long,long long> >
#define vpcl vector<pair<c,long long> >
#define vpsl vector<pair<string,long long> >

#define qi  queue<int>
#define ql  queue<long>
#define qll queue<long long>
#define PQ priority_queue

#define mpii map<int,int>
#define mpsl map<string,long long>
#define mpcl map<char,long long>
#define mpll map<long long,long long>

#define stl set<ll>
#define sts set<string>
/// Bug
#define bug(x) cout<<#x<<": "<<x<<endl
#define bug1(x,y) cout<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<endl
#define bug2(x,y,z) cout<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<"  |  "<<#z<<": "<<z<<endl
#define bug3(w,x,y,z) cout<<#w<<": "<<w<<"  |  "<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<"  |  "<<#z<<": "<<z<<endl
/// Trigonometry
#define pi acos(-1.0)
#define rad(x) (((1.0 * x * pi) / 180.0))
#define deg(x) (((x * 180.0) / (1.0 * pi)))
#define sinr(x) (sin(rad(x)))
#define cosr(x) (cos(rad(x)))
#define tanr(x) (tan(rad(x)))
#define asind(x) (deg((asin(x))))
#define acosd(x) (deg((acos(x))))
#define atand(x) (deg((atan(x))))

///Bit

#define setbiton(x, i) (x |= (1 << i))
#define setbitoff(x, i) (x &= (~(1 << i)))
#define togglebit(x, i) (x ^= (1 << i))
#define checkbiton(x,i)   ((x &(1 << i))!=0)
#define ispow2 (x!=0 && (x&(x-1))==0)
#define countbit(x) __builtin_popcountll((ll)x)
#define countlead(x) __builtin_clzll((ll)x)  ///give wrong ans for zero (0)
#define counttrail(x) __builtin_ctzll((ll)x)  ///give wrong ans for zero (0)
/// Search
#define LB(a,x) (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x) (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define bin_sa(a,n,x) (binary_search(a, a+n,x))
#define bin_sv(v,x) (binary_search(v.begin(), v.end(),x))

/// Algorithm
#define Unique(store) store.resize(unique(store.begin(),store.end())-store.begin())
#define mxe(a,n) (*max_element(a,a+n))
#define mxv(v)   (*max_element(v.begin(), v.end()))
#define mne(a,n) (*min_element(a,a+n))
#define mnv(v)   (*min_element(v.begin(), v.end()))
#define SUM(a,n) (accumulate(a,a+n,0))
#define SUMv(v)   (accumulate(v.begin(), v.end(), 0))
#define occurx(v,x) (count(v.begin(), v.end(),x))
#define findx(v,x)  (find(v.begin(), v.end(),x))
#define swap(a,b)  a^=b^=a^=b
#define sgn(x,y) ((x)+eps<(y)?-1:((x)>eps+(y)?1:0))

///I/O
#define input() freopen("in0.txt","r",stdin)
#define output()freopen("out0.txt","w",stdout)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ppc(x,y) cout<<fixed<<setprecision(y)<<x<<endl

#define IN scanf
#define OUT printf
///    #define SI(a) scanf("%d",&a)
///   #define SL(a) scanf("%lld",&a)
///    #define SD(a) scanf("%lf",&a)
///   #define OI(a) printf("%d",a)
///    #define OL(a) printf("%lld",a)
///    #define OD(a) printf("%lf",a)
///     #define ON() printf("\n")


#define EPS 1e-9
#define inf 1e18
#define MOD 1000000007
template<typename T>inline string toString(T a){ ostringstream os("");os<<a;return os.str();}
template<typename T>inline ll toLong(T a){ll res;istringstream os(a);os>>res;return res;}

///----------------------Main Code-------------------------------------///

double fun(double m,vpl v,vpl v1)
{
    double x1=v[0].ff+(v[1].ff-v[0].ff)*m*1.0;
    double y1=v[0].ss+(v[1].ss-v[0].ss)*m*1.0;
    double x2=v1[0].ff+(v1[1].ff-v1[0].ff)*m*1.0;
    double y2=v1[0].ss+(v1[1].ss-v1[0].ss)*m*1.0;

    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);

}
int main()
{
#ifndef ONLINE_JUDGE
    input();
    output();
#endif
    fast();
//    clock_t begin, end;
//    double time_spent;
//    begin = clock();
    ll n, x, y, a, b, c=1, t, q;
    string s;
    //char c;
    cin>>t;
    while (t--)
    {
        vpl v,v1;
        fr(i,0,2)
        cin>>x>>y,v.pb(mp(x,y));
         fr(i,0,2)
        cin>>x>>y,v1.pb(mp(x,y));
        ll k=200;
        double s=0.0,e=1.0;
        while(k--)
        {
            double l1=(2*s+e)/3.0;
            double l2=(2*e+s)/3.0;
            if(fun(l1,v,v1)<fun(l2,v,v1))
            e=l2;
            else s=l1;
        }
        //bug(n);
        double r=(double)sqrt(fun(e,v,v1));
        q=r;
        if(r!=q)
        cout<<"Case "<<c++<<": "<<fixed<<setprecision(10)<<sqrt(fun(e,v,v1))<<endl;
        else cout<<"Case "<<c++<<": "<<q<<endl;

    }
//    end = clock();
//    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
//   cout<<"Time spent = "<<time_spent<<endl;


    return 0;
}

Lightoj-1136 .cpp file

#include <bits/stdc++.h>
using namespace std;
#define calc(n) (n/3*2+(n%3==2))

int main()
{
    int a, b, cs, test;
    scanf("%d", &test);
    for(cs = 1; cs <= test; cs++)
    {
        scanf("%d %d", &a, &b);
        a--;
        printf("Case %d: %d\n", cs, calc(b) - calc(a));
    }
    return 0;
}

Lightoj-1123 .cpp file

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

struct data
{
    int u,v,w;
    bool operator< (const data& p)const
    {
        return w<p.w;
    }
    data(int x,int y, int z)
    {
        u=x,v=y,w=z;
    }
};

vector<data>edge;
int n,m,cnt=0;
int par[210];

int find(int n)
{
    return par[n]=(par[n]==n)?n:find(par[n]);
}

int mst()
{
    int cnt=0,sum=0;
    sort(edge.begin(),edge.end());
    vector<data>temp;
    for(int i=0; i<edge.size(); i++)
    {
        int u=find(edge[i].u);
        int v=find(edge[i].v);
        if(u!=v)
        {
            cnt++;
            par[u]=v;
            sum+=edge[i].w;
            temp.push_back(edge[i]);
            if(cnt==n-1)
            break;
        }
    }
    edge.clear();
    edge=temp;
    if(cnt==n-1) return sum;
    return -1;
}

int main()
{
    int t;
    cin>>t;
    int co=1;
    while(t--)
    {
       cin>>n>>m;
         cout<<"Case "<<co++<<":"<<endl;
        while(m--)
        {
            int x,y,z;
            cin>>x>>y>>z;
            edge.push_back(data(x,y,z));
            for(int i=0;i<=n;i++)
            par[i]=i;
            printf("%d\n",mst());
        }
        edge.clear();
    }
    return 0;
}

Lightoj-1122 .cpp file

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, a[10], dp[11][10], test;;
    cin>>test;
    for(int i = 1; i <= test; i++)
    {
        cin>>m>>n;
        for(int j = 0; j < m; j++)
        {
            cin>>a[j];
            dp[1][j] = 1;
        }
        for(int k = 2; k <= n; k++)
        {
            for(int j = 0; j < m; j++)
            {
                dp[k][j] = 0;
                for(int l = 0; l < m; l++)
                {
                    if(abs(a[j]-a[l]) <= 2) dp[k][j] += dp[k-1][l];
                }
            }
        }
        int r=0,x=0;
        for( r = x = 0; x< m; x++)
            r+= dp[n][x];
        printf("Case %d: %d\n", i, r);
    }
    return 0;
}

Lightoj-1116 .cpp file

#include<stdio.h>
int main()
{
    int t,m,l=0;
    long long int w;
    scanf("%d",&t);
    if(t<=10000)
        while(t--)
        {
            scanf("%lld",&w);
            if(w%2!=0)
                printf("Case %d: Impossible\n",++l);
            else
            {
                m=1;
                while(w%2==0)
                {
                    m*=2;
                    w/=2;
                }
                printf("Case %d: %lld %d\n",++l,w,m);
            }

        }

    return 0;
}

Lightoj-1112 .cpp file

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

#define SIZE 100005
int f[SIZE];
int tree[SIZE];
int MaxIdx;
int read(int idx)
{
int sum = 0;
while(idx > 0)
{
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}

int update(int idx, int val)
{
while(idx <= MaxIdx)
{
tree[idx] += val;
idx += (idx & -idx);
}
}

int query(int i, int j)
{
return read(j) - read(i-1);
}

int main()
{
//freopen("input.txt", "r", stdin);
//freopen("out.txt", "w", stdout);

unsigned i, j, k, l, sum = 0;
int tc, t, d, x, y, r, n, m, p, q,current, first;
char ch;
bool flag;

scanf("%d", &tc);
getchar();

for(t = 1; t <= tc; t++)
{
scanf("%d %d", &n, &q);
printf("Case %d:\n", t);
MaxIdx = n;

memset(tree, 0, sizeof tree);

for(i = 1; i <= n; i++)
{
scanf("%d", &f[i]);
update(i, f[i]);
}

for(i = 0; i < q; i++)
{
scanf("%d", &m);

switch(m)
{
case 1:
scanf("%d", &j); j++;
update(j, -f[j]);
printf("%d\n", f[j]);
f[j] = 0;
break;
case 2:
scanf("%d %d", &j, &k); j++;
update(j, k);
f[j] += k;
break;
case 3:
scanf("%d %d", &j, &k); j++, k++;
printf("%d\n", query(j, k));
break;
}
}
}

return 0;
}