Assignment 4

struct Point

double x,y;

};

Point p[10001];

int compareX(const void* a, const void* b)

Point *p1 = (Point *)a, *p2 = (Point *)b;

return (p1->x - p2->x);

int compareY(const void* a, const void* b)

Point *p1 = (Point *)a, *p2 = (Point *)b;

return (p1->y - p2->y);

double dist(Point p1, Point p2)

return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +(p1.y - p2.y)*(p1.y - p2.y));

double bruteForce(Point P[], int n)

double min = FLT_MAX;

for (int i = 0; i < n; ++i)

for (int j = i+1; j < n; ++j)

if (dist(P[i], P[j]) < min)

min = dist(P[i], P[j]);

return min;

double stripClosest(Point strip[], int size, double d)

double min = d;
qsort(strip, size, sizeof(Point), compareY);

for (int i = 0; i < size; ++i)

for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min;
++j)

if (dist(strip[i],strip[j]) < min)

min = dist(strip[i], strip[j]);

return min;

double closestUtil(Point P[], int n)

if (n <= 3)

return bruteForce(P, n);

int mid = n/2;

Point midPoint = P[mid];

double dl = closestUtil(P, mid);

double dr = closestUtil(P + mid, n - mid);

double d = min(dl, dr);

Point strip[n];

int j = 0;

for (int i = 0; i < n; i++)

//if (abs(P[i].x - midPoint.x) < d)

strip[j ++] = P[i];

return min(d, stripClosest(strip, j, d) );

double closest(Point P[], int n)

qsort(P, n, sizeof(Point), compareX);

return closestUtil(P, n);

int main()

int n;

scanf("%d",&n);

while (n!=0)

for(int i=0; i<n; i++)

scanf("%lf%lf",&p[i].x,&p[i].y);

double a = closest(p,n);

if(a>=10000)

printf("INFINITY\n");

else

printf("%.4f\n",a);

scanf("%d",&n);

Assignment 5

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

int main()

int n, num[10000], lis[10000], lds[10000];

vector<int> v;

while (scanf("%d", &n) != EOF)

{
int i;

for (i = 0; i < n; i++)

scanf("%d", &num[i]);

v.clear();

int size = 1;

v.push_back(num[0]);

lis[0] = 1;

for (i = 1; i < n; i++)

if (num[i] > v.back())

v.push_back(num[i]);

lis[i] = ++size;

else

int temp = lower_bound(v.begin(), v.end(), num[i]) - v.begin();

v[temp] = num[i];

lis[i] = temp + 1;

v.clear();

size = 1;

v.push_back(num[n - 1]);

lds[n - 1] = 1;

for (i = n - 2; i >= 0; i--)

if (num[i] > v.back())

v.push_back(num[i]);

lds[i] = ++size;
}

else

int temp = lower_bound(v.begin(), v.end(), num[i]) - v.begin();

v[temp] = num[i];

lds[i] = temp + 1;

int max = 0;

for (i = 0; i < n; i++)

int temp = min(lis[i], lds[i]);

if (max < temp)

max = temp;

printf("%d\n", max * 2 - 1);

return 0;

Assignment 6

#include <iostream>

int t, T;

struct Item {

int price, weight;

};

Item items[1000];

int nItem;
void init() {

std::cin >> T;

t = 0;

int dp[1000 + 1][30 + 1];

bool input() {

if (t++ == T)

return false;

std::cin >> nItem;

for (int i = 0; i < nItem; i++)

std::cin >> items[i].price >> items[i].weight;

for (int i = 0; i < nItem; i++) {

for (int j = 0; j <= 30; j++)

dp[i][j] = -1;

return true;

int knapsack(int weight, int n) {

if (n < 0)

return 0;

if (dp[n][weight] >= 0)

return dp[n][weight];

dp[n][weight] = knapsack(weight, n-1);

if (weight >= items[n].weight &&

items[n].price + knapsack(weight - items[n].weight, n-1) > dp[n][weight])

dp[n][weight] = items[n].price + knapsack(weight - items[n].weight, n-1);

return dp[n][weight];
}

void run() {

int nCustomer;

std::cin >> nCustomer;

int sum = 0, power;

for (int i = 0; i < nCustomer; i++) {

std::cin >> power;

sum += knapsack(power, nItem - 1);

std::cout << sum << std::endl;

int main() {

init();

while (input())

run();

return 0;

Assignment 7
#include<string>
#include<algorithm>
#include<iostream>

using namespace std;

string arr[300];
int n = 0;
int maxx = 0;

void backT(int t[][300],int i, int j, int l,string s1,string s2,string

s)//back track
{
if(l<=0)
{
if(s!="")
{
if(s.length()>maxx)
{
maxx = s.length();
}
reverse(s.begin(), s.end());
int f = 0;
for(int i =0; i<n; i++)
{
if (s==arr[i])
{
f = 1;
break;
}
}
if(f== 0)
{
arr[n] = s;
n++;
}
s = "";
}
return;
}
if(s1[i-1]== s2[j-1])
{
s+=s1[i-1];
backT(t,i-1,j-1,l-1,s1,s2,s);
}
else
{
if(l ==t[i-1][j])
{
backT(t,i-1,j,l,s1,s2,s);
}
if(l == t[i][j-1])
{
backT(t,i,j-1,l,s1,s2,s);
}
if(l == t[i-1][j-1])
{
backT(t,i-1,j-1,l,s1,s2,s);
}
if(t[i][j]!=t[i-1][j] && t[i][j]!= t[i][j-1] && t[i][j]!= t[i-1]
[j-1])
{
s+=s1[i-1];
backT(t,i-1,j-1,l-1,s1,s2,s);
}
}
}

int main()
{
string string1;
string string2;
while(cin>>string1)
{
cin>>string2;
int s1 = string1.length()+1;
int s2 = string2.length()+1;
int T[300][300];
for(int i = 0; i<=s1-1; i++)
{
for(int j=0; j<=s2-1; j++)
{
if(i==0 || j==0)
{
T[i][j] = 0;
}
else
{
if(string1[i-1] == string2[j-1])
{
T[i][j]= T[i-1][j-1]+1;
}
else
{
T[i][j] = (T[i-1][j]>T[i][j-1]) ? T[i-1][j]:T[i]
[j-1];
}
}
}
}

string S = "";
backT(T,s1-1,s2-1,T[s1-1][s2-1],string1,string2,S);
if(n == 0)
{
cout<<"No common sequence."<<endl;
}
else
{

for(int i = 0; i<n; i++)

{
for (int j = i+1; j<n; j++)
{
if(arr[i]>arr[j])
{
string temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}

for(int i =0; i<n; i++)

{
if(arr[i].length() == maxx)
{
cout<<arr[i]<<endl;
}
arr[i]="\0";
}
}
n = 0;
maxx = 0;
S="";
cout<<endl;
}
return 0;
}

Assignment 8

#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;

struct node
{
double le,ri;
node(double l,double r):le(l),ri(r) {}
bool operator<(const node& e)const
{
return le<e.le;
}
};

int n;
double l,w;
vector<node> v;

int main()
{
while(scanf("%d%lf%lf",&n,&l,&w)==3)
{
v.clear();
for(int i=0; i<n; ++i)
{
double p,r;
scanf("%lf%lf",&p,&r);
if(r<=w/2)
continue;
double x=sqrt(r*r-w*w/4.0);
if(p+x>=0 || p-x<=l)
v.push_back(node(p-x,p+x));
}
sort(v.begin(),v.end());
int ans=0;
bool ok=1;
double maxr=0;
int i=0;
while(1)
{
if(v[i].le>maxr)
{
ok=0;
break;
}
double tmp=0;
++ans;
for(; i<v.size() && v[i].le<=maxr; ++i)
{
tmp=max(tmp,v[i].ri);
}
maxr=max(maxr,tmp);
if(i==v.size()||maxr>=l)
break;
}
if(maxr<l)
ok=0;
if(!ok)
puts("-1");
else
printf("%d\n",ans);
}
return 0;
}

Assignment 9
#include <iostream>
#include <vector>
#include <queue>
#define in pair<int, int>
#include <limits>
using namespace std;
int infinity =numeric_limits<int>::max();
int latency[100000];
int n, m, s, t;
vector< vector<in> > com;

void dijkstra(int s)
{
for(int i = 0; i<n; i++)
latency[i] = infinity;
latency[s] = 0;
priority_queue<in, vector<in>, greater<in> > pq;
pq.push( in(latency[s], s) );
in p;
int t, u;
while(!pq.empty())
{
p = pq.top();
pq.pop();
t = p.first;
u = p.second;
if(t > latency[u] )
continue;
for(int i = 0; i<com[u].size(); i++)
{
if(latency[com[u][i].first] > latency[u] + com[u][i].second)
{
latency[com[u][i].first] = latency[u] + com[u][i].second;
pq.push( in(latency[com[u][i].first], com[u][i].first) );
}
}
}
}

int main()
{
int tc;
scanf("%d", &tc);
for(int k = 1; k<=tc; k++)
{
scanf("%d%d%d%d", &n, &m, &s, &t);
com.assign(n, vector<in>(0));
int c1, c2, cable;
for(int i = 0; i<m; i++)
{
scanf("%d%d%d", &c1, &c2, &cable);
com[c1].push_back( in(c2, cable) );
com[c2].push_back( in(c1, cable) );
}

dijkstra(s);
printf("Case #%d: ", k);
if(latency[t] != infinity)
printf("%d\n", latency[t]);
else
printf("unreachable\n");
}
}

Assignment 10
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int Inf = 1e9;
const int maxstars = 1005;
struct Edge
{
int to, c;
};
vector<Edge> edges[maxstars];
int jarak[maxstars];
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
int N, E;
scanf("%d %d",&N,&E);
for (int i = 0; i < N; ++i)
{
edges[i].clear();
jarak[i] = Inf;
}
Edge e;
while (E--)
{
int x;
cin >> x >> e.to >> e.c;
edges[x].push_back(e);
}
for (int t = 0; t < N - 1; ++t)
{
for (int j = 0; j < N; ++j)
{
for (int e = 0; e < edges[j].size(); ++e)
{
jarak[edges[j][e].to] = min(jarak[edges[j][e].to],
jarak[j] + edges[j][e].c);
}
}
}
bool bisaturun = false;
for (int j = 0; j < N; ++j)
{
for (int e = 0; e < edges[j].size(); ++e)
{
bisaturun |= jarak[edges[j][e].to] > jarak[j] + edges[j]
[e].c;
}
}
cout << (bisaturun ? "possible\n" : "not possible\n");
}
}

Assignment 11
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 9999999999999
#define eps 0.00000000001

vector<int> edge[50];
int cap[50][50], flow[50][50], pre[50];
double cost[50][50], dis[50];

void Initial(int S, int T, int N, int M);

double MCMF(int S, int T);
bool SPFA(int S, int T);
void UpdateFlow(int S, int T, int bottleneck);

int main()
{
int N, M;
while (scanf("%d %d", &N, &M) && (N || M)) {
int S = 0,
T = N+M+1;
Initial(S, T, N, M);

double travel_time;
for (int i = 1; i <= N; ++i) {
for (int j = N+1; j <= N+M; ++j) {
scanf("%lf", &travel_time);
cost[i][j] = travel_time;
}
}
printf("%.2f\n", MCMF(S, T) / N + eps);
}
}
void Initial(int S, int T, int N, int M)
{
for (int i = S; i <= T; ++i) edge[i].clear();
memset(cap, 0, sizeof(cap));
memset(flow, 0, sizeof(flow));
memset(cost, 0, sizeof(cost));

for (int i = 1; i <= N; ++i) {

cap[S][i] = 1; // connect S to all banks
edge[S].push_back(i);
}
for (int i = N+1; i <= N+M; ++i) {
cap[i][T] = 1; // connect all police to T
edge[i].push_back(T);
}
for (int i = 1; i <= N; ++i)
for (int j = N+1; j <= N+M; ++j) {
cap[i][j] = 1; // connect all banks to all police
edge[i].push_back(j);
edge[j].push_back(i);
}
}
double MCMF(int S, int T)
{
double min_cost = 0;
while (SPFA(S, T)) {
UpdateFlow(S, T, 1);
min_cost += dis[T];
}
return min_cost;
}
bool SPFA(int S, int T)
{
fill(begin(dis), end(dis), INF);
queue<int> Q;
bool inQueue[50] = {0};

dis[S] = 0;
Q.push(S);
inQueue[S] = true;

while (!Q.empty()) {
int cur = Q.front();
inQueue[cur] = false;
Q.pop();

for (int nxt : edge[cur]) {

if (flow[nxt][cur] > 0 && dis[cur] + (-cost[nxt][cur]) <
dis[nxt]) {
dis[nxt] = dis[cur] + (-cost[nxt][cur]);
pre[nxt] = cur;
if (!inQueue[nxt]) {inQueue[nxt] = true; Q.push(nxt);}
}
else if (cap[cur][nxt] > flow[cur][nxt] && dis[cur] + cost[cur]
[nxt] < dis[nxt]) {
dis[nxt] = dis[cur] + cost[cur][nxt];
pre[nxt] = cur;
if (!inQueue[nxt]) {inQueue[nxt] = true; Q.push(nxt);}
}
}
}
if (dis[T] == INF) return false;
else return true;
}
void UpdateFlow(int S, int T, int bottleneck)
{
for (int cur = T; cur != S; cur = pre[cur]) {
flow[pre[cur]][cur] += bottleneck;
flow[cur][pre[cur]] -= bottleneck;
}
}