UVa 10541 - Stripe

//\\__ hr1212 __//\\

import java.io.*;
import java.math.*;
import java.util.*;

public class Main{

static int n,m,z,x,y,k,l,r,i,j,t;
static int a[]=new int[500];;
static String s,p[],q;
static int MAX=1000010;
static BigInteger dp[][]=new BigInteger[500][500];;

public static void main(String[] args) throws IOException{
InputReader in=new InputReader(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(System.out);

t=Integer.parseInt(br.readLine());
for(k=0;k<t;k++){
for(i=0;i<500;i++){
for(j=0;j<500;j++)
dp[i][j]=BigInteger.valueOf(-1);
}
s=br.readLine();
p=s.split(" ");

m=Integer.parseInt(p[0]);
n=Integer.parseInt(p[1]);
for(i=0;i<n;i++){
a[i]=Integer.parseInt(p[i+2]);
}
System.out.println(solve(1,0));
}

out.close();

}

static BigInteger solve(int i,int j){
if(j==n && i<=m+2)
return BigInteger.ONE;
if(j>=n || i>m)
return BigInteger.ZERO;
z=dp[i][j].compareTo(BigInteger.valueOf(-1));
if(z!=0)
return dp[i][j];
return dp[i][j]=solve(i+1,j).add(solve(i+a[j]+1,j+1));
}

static class InputReader {

private InputStream stream;
private byte[] buf = new byte[8192];
private int curChar;
private int snumChars;
private SpaceCharFilter filter;

public InputReader(InputStream stream) {
this.stream = stream;
}

public int snext() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}

public int nextInt() {
int c = snext();
while (isSpaceChar(c))
c = snext();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}

int res = 0;

do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));

return res * sgn;
}

public long nextLong() {
int c = snext();
while (isSpaceChar(c))
c = snext();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}

long res = 0;

do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));

return res * sgn;
}

public String readString() {
int c = snext();
while (isSpaceChar(c))
c = snext();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = snext();
} while (!isSpaceChar(c));
return res.toString();
}

public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}

UVa 1056 - Degrees of Separation

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,graph[100][100];

map<string,int> mm;

int main(){
    int tt=1,r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p,q;

    while(sii(n,m)!=EOF){
        if(n==0 && m==0)
            break;
        k=0;
        f(i,0,n){
            f(j,0,n)
                graph[i][j]=1e9;
        }
        f(i,0,n)
            graph[i][i]=0;
        while(m--){
            cin>>p>>q;
            if(mm.find(p)==mm.end())
                mm[p]=k++;
            if(mm.find(q)==mm.end())
                mm[q]=k++;
            graph[mm[p]][mm[q]]=1;
            graph[mm[q]][mm[p]]=1;
        }

        f(k,0,n){
            f(i,0,n){
                f(j,0,n){
                    graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
                }
            }
        }
        z=0;
        f(i,0,n){
            f(j,0,n){
                z=max(z,graph[i][j]);
            }
        }
        printf("Network %d: ",tt++);
        if(z==1e9)
            printf("DISCONNECTED\n");
        else
            pi(z);
        nl;
        mm.clear();
    }

    return 0;
}

UVa 11437 - Triangle Fun

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%lld\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m;

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    double ax,ay,bx,by,cx,cy,dx,dy,ex,ey,fx,fy,px,py,qx,qy,rx,ry,mad,cad,mbe,cbe,mcf,ccf,lpr,lqr,lpq,s,area;

    si(t);
    while(t--){
        cin>>ax>>ay>>bx>>by>>cx>>cy;
        dx=(cx+2*bx)/3;dy=(cy+2*by)/3;
        ex=(ax+2*cx)/3;ey=(ay+2*cy)/3;
        fx=(bx+2*ax)/3;fy=(by+2*ay)/3;

        mad=(ay-dy)/(ax-dx);cad=ay-mad*ax;
        mbe=(by-ey)/(bx-ex);cbe=by-mbe*bx;
        mcf=(cy-fy)/(cx-fx);ccf=cy-mcf*cx;

        px=(cbe-cad)/(mad-mbe);py=(mad*cbe-mbe*cad)/(mad-mbe);
        qx=(cbe-ccf)/(mcf-mbe);qy=(mcf*cbe-mbe*ccf)/(mcf-mbe);
        rx=(ccf-cad)/(mad-mcf);ry=(mad*ccf-mcf*cad)/(mad-mcf);

        lpr=sqrt((px-rx)*(px-rx)+(py-ry)*(py-ry));
        lqr=sqrt((qx-rx)*(qx-rx)+(qy-ry)*(qy-ry));
        lpq=sqrt((px-qx)*(px-qx)+(py-qy)*(py-qy));

        s=(lpr+lqr+lpq)/2;

        area=sqrt(s*(s-lpr)*(s-lqr)*(s-lpq));

        ans=(area+0.5);
        pi(ans);
    }

    return 0;
}

UVa 10003 - Cutting Sticks

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,dp[100][100];
vi v;

int solve(int i,int j){
    int k,z=1e9;
    if(i==j || i+1==j)
        return 0;
    if(i>j)
        return 1e9;
    if(dp[i][j]!=-1)
        return dp[i][j];
    f(k,i+1,j)
        z=min(z,solve(i,k)+solve(k,j));
    return dp[i][j]=z+v[j]-v[i];
}

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    while(si(m)){
        if(m==0)
            break;

        v.clear();
        clr(dp,-1);

        v.pb(0);
        si(n);
        f(i,0,n){
            si(x);
            v.pb(x);
        }
        v.pb(m);
        n++;
        printf("The minimum cutting is %d.\n",solve(0,n));
    }

    return 0;
}

UVa 11777 - Automate the Grades

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 1000100
#define MOD 1000000007

int n,m,a[MAX];

int main(){
    int tt=1,r,k,i,c=0,x=0,y=0,j,t,l,x1=0,y1=0;
    ll ans=0;string p;
    double z;

    si(t);
    while(t--){
        z=0;
        f(i,0,7)
            si(a[i]);
        sort(a+4,a+7);
        f(i,0,4)
            z+=a[i];
        z+=(a[5]+a[6])/2.0;
        printf("Case %d: ",tt++);
        if(z>=90)
            printf("A");
        else if(z>=80)
            printf("B");
        else if(z>=70)
            printf("C");
        else if(z>=60)
            printf("D");
        else
            printf("F");
        nl;
    }

    return 0;
}