[UVA] 12208 - How Many Ones Needed?

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
LL cnt(LL k){
    if(k<=0) return 0;
    LL ans=0,tmp=1;
    while(tmp*2<=k){
        ans=ans*2+tmp;
        tmp*=2;
    }
    ans+=cnt(k-tmp)+k-tmp;
    return ans;
}
int main(){
    LL n,m,C=0;
    while(scanf("%lld%lld",&n,&m)!=EOF && n+m){
        printf("Case %lld: %lld\n",++C,cnt(m+1)-cnt(n));
    }
}

[UVA] 12347 - Binary Search Tree

#include<bits/stdc++.h>
using namespace std;
struct node{
    int val;
    node *l,*r;
};
void newnode(node *&pt){
    pt=new node;
    pt->l=NULL;
    pt->r=NULL;
}
vector<int> arr;
node* build(node *pt,int l,int r){
    if(l>r) return pt;
    if(pt==NULL) newnode(pt);
    pt->val=arr[l];
    if(l<r){
        int i;
        for(i=l+1;i<=r;i++){
            if(arr[i]>arr[l]) break;
        }
        pt->l=build(pt->l,l+1,i-1);
        pt->r=build(pt->r,i,r);
    }
    return pt;
}
void dfs(node *pt){
    if(pt==NULL) return;
    dfs(pt->l);
    dfs(pt->r);
    printf("%d\n",pt->val);
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        arr.push_back(n);
    }
    node *root=build(root,0,arr.size()-1);
    dfs(root);
}

[UVA] 12442 - Forwarding Emails

#include<bits/stdc++.h>
using namespace std;
#define N 50005
int to[N],pre[N],sccno[N],cnt[N],val[N],dfs_cnt,scc_cnt;
vector<int> sta,G[N];
int dfs(int u){
    int lowu=pre[u]=++dfs_cnt;
    sta.push_back(u);
    /**************/
    int v=to[u];
    if(pre[v]==0){
        int lowv=dfs(v);
        lowu=min(lowu,lowv);
    }
    else if(!sccno[v]){
        lowu=min(lowu,pre[v]);
    }
    /**************/
    if(lowu==pre[u]){
        scc_cnt++;
        while(sta.size()){
            int x=sta.back();
            sta.pop_back();
            sccno[x]=scc_cnt;
            cnt[scc_cnt]++;
            if(x==u) break;
        }
    }
    return lowu;
}
int dfs2(int u){
    if(val[u]) return val[u];
    int i,sum=cnt[u];
    for(i=0;i<G[u].size();i++){
        int v=G[u][i];
        sum+=dfs2(v);
    }
    return val[u]=sum;
}
int main(){
    int t,n,m,x,y,i,j,C=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(pre,0,sizeof(pre));
        memset(sccno,0,sizeof(sccno));
        memset(cnt,0,sizeof(cnt));
        memset(val,0,sizeof(val));
        for(i=0;i<n;i++){
            scanf("%d%d",&x,&y);
            to[x]=y;
        }
        scc_cnt=dfs_cnt=0;
        for(i=1;i<=n;i++){
            if(pre[i]==0){
                sta.clear();
                dfs(i);
            }
        }
        for(i=1;i<=scc_cnt;i++){
            G[i].clear();
        }
        for(i=1;i<=n;i++){
            x=i,y=to[i];
            if(sccno[x]!=sccno[y]){
                G[sccno[x]].push_back(sccno[y]);
            }
        }
        for(i=1;i<=scc_cnt;i++){
            dfs2(i);
        }
        int ans=0,id;
        for(i=1;i<=n;i++){
            if(val[sccno[i]]>ans){
                ans=val[sccno[i]],id=i;
            }
        }
        printf("Case %d: %d\n",++C,id);
    }
}

[UVA] 11728 - Alternate Task

#include<bits/stdc++.h>
using namespace std;
int s[1005];
vector<int> pri;
int main(){
    int t,n,m,i,j,C=0;
    for(i=1;i<=1000;i++){
        for(j=1;j<=i;j++){
            if(i%j==0){
                s[i]+=j;
            }
        }
    }
    while(scanf("%d",&n)!=EOF && n){
        int flag=0;
        for(i=n;i>0;i--){
            if(s[i]==n){
                flag=1;
                break;
            }
        }
        printf("Case %d: %d\n",++C,flag?i:-1);
    }
}

[UVA] 12439 - February 29

#include<bits/stdc++.h>
using namespace std;
string mon[15]={"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November" , "December"};
char s1[15],s2[15];
int main(){
    int t,m1,m2,d1,d2,y1,y2,i,j,C=0;
    scanf("%d",&t);
    while(t--){
        scanf("%s %d, %d",s1,&d1,&y1);
        scanf("%s %d, %d",s2,&d2,&y2);
        for(i=0;i<12;i++){
            if(mon[i]==string(s1)) m1=i+1;
            if(mon[i]==string(s2)) m2=i+1;
        }
        int ans=(y2/4-y2/100+y2/400)-(y1/4-y1/100+y1/400);
        if(y1%4==0 && y1%100!=0 || y1%400==0){
            if(m1<2 || m1==2 && d1<=29) ans++;
        }
        if(y2%4==0 && y2%100!=0 || y2%400==0){
            if(m2<2 || m2==2 && d2<29) ans--;
        }
        printf("Case %d: %d\n",++C,ans);
    }
}

[UVA] 12428 - Enemy at the Gates

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int t,n,m,x,y,i,j;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&m);
        long long int L=0,R=n+1,M;
        while(L+1!=R){
            M=(L+R)/2;
            if(M*(M-1)/2+n-M>=m) R=M;
            else L=M;
        }
        printf("%lld\n",n-R);
    }
}

[UVA] 12694 - Meeting Room Arrangement

#include<bits/stdc++.h>
using namespace std;
struct P{
    int x,y;
};
int cmp(P a,P b){
    return a.y<b.y;
}
int main(){
    int t,n,m,x,y,i,j;
    scanf("%d",&t);
    while(t--){
        vector<P> arr;
        while(scanf("%d%d",&x,&y) && x+y){
            arr.push_back((P){x,y});
        }
        sort(arr.begin(),arr.end(),cmp);
        int dp[15]={0};
        for(i=1,j=0;i<=10;i++){
            dp[i]=dp[i-1];
            while(j<arr.size() && arr[j].y==i){
                dp[i]=max(dp[i],dp[arr[j].x]+1);
                j++;
            }
        }
        printf("%d\n",dp[10]);
    }
}

[UVA] 12650 - Dangerous Dive

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,x,i,j;
    while(scanf("%d%d",&n,&m)!=EOF){
    int is[10005]={0};
        for(i=0;i<m;i++){
            scanf("%d",&x);
            is[x]=1;
        }
        int flag=0;
        for(i=1;i<=n;i++){
            if(is[i]==0){
                flag=1;
                printf("%d ",i);
            }
        }
        if(flag==0) putchar('*');
        puts("");
    }
}

[UVA] 11714 - Blind Sorting

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int n,m,add;
    while(scanf("%lld",&n)!=EOF){
        m=1,add=0;
        while(m<n){
            m*=2,add++;
        }
        printf("%lld\n",n-1+add-1);
    }
}

[UVA] 11730 - Number Transformation

#include<bits/stdc++.h>
using namespace std;
struct P{
    int u,add;
}in,out;
int is[1005];
vector<int> pri;
int main(){
    int t,n,m,i,j,C=0;
    for(i=2;i<=1000;i++){
        if(is[i]==0){
            for(j=i+i;j<=1000;j+=i){
                is[j]=1;
            }
            pri.push_back(i);
        }
    }
    while(scanf("%d%d",&n,&m)!=EOF && n&&m){
        queue<P> que;
        que.push((P){n,0});
        int vi[1005]={0},flag=0;
        vi[n]=1;
        while(que.size()){
            out=que.front();
            que.pop();
            if(out.u==m){
                flag=1;
                break;
            }
            for(i=0;i<pri.size() && pri[i]<out.u;i++){
                in.add=out.add+1;
                if(out.u%pri[i]) continue;
                in.u=out.u+pri[i];
                if(vi[in.u] || in.u>m) continue;
                vi[in.u]=1;
                que.push(in);
            }
        }
        printf("Case %d: %d\n",++C,flag?out.add:-1);
    }
}

[UVA] 11764 - Jumping Mario

#include<bits/stdc++.h>
using namespace std;
int s[55];
int main(){
    int t,n,i,j,C=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%d",&s[i]);
        }
        int a=0,b=0;
        for(i=1;i<n;i++){
            if(s[i]>s[i-1]) a++;
            if(s[i]<s[i-1]) b++;
        }
        printf("Case %d: %d %d\n",++C,a,b);
    }
}

[UVA] 10420 - List of Conquests

#include<bits/stdc++.h>
using namespace std;
map<string,int> ma;
map<string,int>::iterator it;
char s1[100],s2[100];
int main(){
    int n;
    scanf("%d",&n);
    getchar();
    while(n--){
        gets(s1);
        sscanf(s1,"%s",s2);
        ma[string(s2)]++;
    }
    for(it=ma.begin();it!=ma.end();it++){
        printf("%s %d\n",it->first.c_str(),it->second);
    }
}

[UVA] 11547 - Automatic Answer

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        n=(n*567/9+7492)*235/47-498;
        if(n<0) n*=-1;
        printf("%d\n",n/10%10);
    }
}