Uva 11500
Link : 11500
Idea :
From a state (a,b) we can go either (a+d,b-d) or (a-d,b+d) . So we can define our recursive relation here.
Base case :
P(i,0) = 1, for i = 0 … a
P(0,i) = 0, for i = 1 … b
So for each step , we can build an equation and using gaussian elimination we can found P(a,b)
Click to See Code
#include <bits/stdc++.h>
using namespace std;
namespace gauss {
double EPS = 1e-8;
typedef double T;
typedef vector<T> VT;
typedef vector<VT> VVT;
int Gauss(VVT &a)
{
int n = a.size(), m= a[0].size();
int r = 0;
for(int c = 0; c < m - 1 && r < n ; c ++ ) {
int j = r;
for(int i = r+1; i < n; i ++ ) {
if(fabs(a[i][c]) > fabs(a[j][c])) j= i;
}
if(fabs(a[j][c]) < EPS) continue;
swap(a[j],a[r]);
T s = 1./a[r][c];
for(int i = 0; i < m ; i ++ ) a[r][i] *= s;
for(int i=0;i < n ;i ++) if(i!=r) {
T t = a[i][c];
for(int j = 0; j < m ; j ++ ) a[i][j] -= t * a[r][j];
}
r++;
}
return r;
}
}
using namespace gauss;
int main()
{
int a,b,l,w;
while(scanf("%d %d %d %d",&a,&b,&l,&w)==4 ) {
if(a+b+l+w == 0) break;
map<pair<int,int> ,int>Map;
int cnt = 0;
for(int i = 0; ; i ++ ) {
Map[make_pair(a+i*w, max(0,b-i*w))] =cnt ++;
if(b-i * w <= 0 ) break;
}
for(int i = 1; ; i ++ ) {
Map[make_pair(max( a - i*w , 0), b + i * w)] =cnt ++;
if(a-i * w <= 0 ) break;
}
int Dim = Map.size();
VVT A ( Map.size() , VT ( Map.size() + 1, 0) );
for(auto a: Map ) {
pair<int,int> P = a.first ;
if(P.first == 0 || P.second == 0 ) {
A[Map[P]][Map[P]] = 1;
A[Map[P]][Dim] = (P.first ? 1 : 0);
continue;
}
pair<int,int> F = make_pair(P.first + w , max(0, P.second - w));
pair<int,int> S = make_pair(max(P.first - w ,0 ) , P.second + w);
A[Map[P]][Map[P]] = 1;
A[Map[P]][Map[F]] = -1. * l / 6;
A[Map[P]][Map[S]] = -1. * (6-l) / 6;
A[Map[P]][Dim] = 0;
}
Gauss(A);
printf("%.1lf\n",A[Map[make_pair(a,b)]][Dim] * 100);
}
}
Uva 11503
Link: 11503 – Virtual Friends
Solution:Disjoint set
* Map the string into integer.
* For each friendship(new edge), If they are already connected,then output the Size of the connected component .if not, Merge them and increase the size of a component
This Problem is basic of Disjoint Set union.
Click to See Code
#include <bits/stdc++.h>
#include <sstream>
using namespace std;
#define MX 100005
string s1,s2;
map<string, int> kl;
int para[MX];
int size[MX];
int find_represent(int a)
{
if(para[a]==a) return a;
else return para[a] = find_represent(para[a]);
}
int friendship(int a,int b)
{
int u = find_represent(a);
int v = find_represent(b);
if(u!=v){
para[u]=v;
size[v] = size[v] + size[u];
}
return size[v];
}
int main()
{
int test,f,inx;
cin>>test;
while (test--) {
cin>>f;
inx=0;
for(int i=0;i<MX;i++) {para[i]=i;size[i]=1;}
while (f--) {
cin>>s1>>s2;
if (kl.count(s1)==0) {
kl[s1]=inx++;
}
if(kl.count(s2)==0) kl[s2]=inx++;
cout<<friendship(kl[s1],kl[s2])<<"\n";
}
kl.clear();
}
return 0;
}
Uva 11505
Link: Uva 11505
Idea:
Easy Problem. Using Vector Translation & Rotation. I use Stanford Geometry Template.
Starting point can be anything, the answer is same. So Pick(0,0) as starting position and initial direction is in +x axis (denoted by a directional vector (1,0))
When we found fd or bk command, we move d distance towards the directional vector.
for lt or rt command , we rotate the directional vector
After executing all commands suppose we are point (x,y) then ans = nearest integer ( sqrt (x*x + y * y ))
Click to See Code
#include <bits/stdc++.h>
using namespace std;
struct PT {
double x,y;
PT(double x,double y):x(x),y(y){}
PT operator + (const PT &p) const {return PT(x+p.x,y+p.y);}
PT operator - (const PT &p) const {return PT(x-p.x,y-p.y);}
PT operator * (double c) const { return PT(x*c, y *c);}
PT operator / (double c) const { return PT(x/c, y /c);}
double mag(){return sqrt(x*x+y*y);}
};
PT RotCCW(PT p,double ang) {return PT(p.x*cos(ang) - p.y*sin(ang) , p.x*sin(ang) + p.y * cos(ang));}
#define PI 0.01745329251994329914588889
int main()
{
int T;
cin>>T;
while(T--) {
int n;
cin >> n;
PT pivot = PT(0,0) , dir = PT(1,0);
double d;
char cmd[11];
for(int i = 0; i < n ; i ++ ) {
scanf("%s %lf",cmd, &d);
if(strcmp(cmd,"fd")== 0) pivot = pivot + dir * d;
if(strcmp(cmd,"bk")== 0) pivot = pivot - dir * d;
if(strcmp(cmd,"lt")== 0) d = PI * d , dir = RotCCW(dir,d);
if(strcmp(cmd,"rt")== 0) d = PI * d , dir = RotCCW(dir, - d) ;
}
printf("%d\n",(int) (pivot.mag() + .5) );
}
}
Uva 11506
Solution:
This problem is a classical problem known as minimum cut of a graph.
We have to split the graph into two part such that node 1 remains in one part, and node n remains in other.
This problem is dual of finding maximum flow of a graph.
For details read : Maxflow
Graph Contruction:
We split each vertex into two nodes.(vin – vout)
for each node other than 1 and n, we give an edge vin to vout with capacity c[i] (cost of destroying i th machine)
for each edge (u,v,w) :
if(u==1 || v ==1 ) then we add (1 -> other node ) with capacity w
else : (uout -> vin ) with capacity w, (vout -> uin) with capacity w, as edges are bidirectional.
Now run standard max-flow algorithm for find max-flow. And ans = maxflow of the graph.
Click to See Code
#include <bits/stdc++.h>
using namespace std;
const int N = 3000;
const int INF = 1e9;
typedef int T;
struct Edge
{
int u, v;
T cap, flow;
Edge(int u, int v, T c, T f):u(u), v(v), cap(c), flow(f) {}
};
struct Dinic
{
int n, m, s, t;
const T oo = 1e9;
vector<Edge> edge;
vector<int> G[N];
bool vis[N];
int d[N];
int cur[N];
void init(int n)
{
this->n=n;
for(int i=0; i<=n; i++)
G[i].clear();
edge.clear();
}
void addEdge(int u, int v, T cap)
{
edge.push_back(Edge(u, v, cap, 0));
edge.push_back(Edge(v, u, 0, 0));
m=edge.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool bfs()
{
memset(vis, 0, sizeof vis);
queue<int> q;
q.push(s);
d[s]=0;
vis[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=0; i<G[x].size(); i++)
{
Edge& e=edge[G[x][i]];
if(!vis[e.v] && e.cap>e.flow)
{
vis[e.v]=true;
d[e.v]=d[x]+1;
q.push(e.v);
}
}
}
return vis[t];
}
T dfs(int x, T a)
{
if(x==t || a==0)return a;
T flow=0, f;
for(int& i=cur[x]; i<G[x].size(); i++)
{
Edge& e=edge[G[x][i]];
if(d[x]+1==d[e.v] && (f=dfs(e.v, min(a, e.cap-e.flow)))>0)
{
e.flow+=f;
edge[G[x][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0)break;
}
}
return flow;
}
T dinitz(int s, int t)
{
this->s=s;
this->t=t;
T flow=0;
while(bfs())
{
memset(cur, 0, sizeof cur);
flow+=dfs(s, oo);
}
return flow;
}
} maxf;
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)==2) {
if(n==0&&m==0) break;
maxf.init(105);
for(int i = 2; i < n ; i ++ ) {
int id,c;
scanf("%d %d",&id,&c);
maxf.addEdge(id,id+n,c);
}
for(int i = 0; i < m; i ++ ){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
if(min(u,v)==1) {
maxf.addEdge(1,max(u,v),w);
}
else {
maxf.addEdge(u+n,v,w);
maxf.addEdge(v+n,u,w);
}
}
int ans = maxf.dinitz(1,n);
printf("%d\n",ans);
}
}
Uva 11508
Link : Uva 11508
Idea: Adhoc
n = count of number
If maximum number in the input < n, there is a solution, else not .The solution is generated by following means.
Each unique number is assigned to pos i, that is if there is a c then array[c] = c, The rest of numbers can be randomly inserted in any position.
Click to See Code
#include <bits/stdc++.h>
using namespace std;
string str;
int main()
{
while(getline(cin,str)) {
int a;
istringstream iss(str);
int iM = -1;
int cnt = 0;
multiset<int> Pos,v;
while(iss >> a) {
iM = max(iM, a);
cnt ++;
v.insert(a);
}
if(iM < cnt ) {
for(int i = 0; i < cnt; i ++ ) Pos.insert(i);
map<int,int> ar;
for(int i = 0; i < cnt ; i ++ ) {
if(v.count(i)) {
v.erase(v.find(i));
Pos.erase(i);
ar[i] = i;
}
}
for(auto a : v ) {
ar[*Pos.begin()] = a ;
Pos.erase(Pos.begin());
}
int f = 0;
for(auto a : ar) {
if(f) printf(" ");
printf("%d",a.second);
f = 1;
}
printf("\n");
}
else {
printf("Message hacked by the Martians!!!\n");
}
}
}
Uva 11509
Link: Uva 11509
Idea: Simple Angle calculation.
Given two vector. We can calculate the angle between them,
Let
where i = unit vector in +x axis, j = unit vector in +y axis
The angle between them =
Now this angle is 0 <= x < PI. This returns the smallest angle between P and Q . To consider only CCW movement, We need to check if Q is in right rotate or left rotate in respect of P.
If Left Rotate : Then we just add angle
If Right Rotate : Then we add 2*PI – angle
After summing all the rotations , to calculate turn we divide sum by 2*PI.
Click to See Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1<<20;
struct PT {
double x,y;
PT(double x=0, double y=0) : x(x), y(y) {}
PT(const PT &p) : x(p.x), y(p.y) {}
PT operator + (const PT &p) const { return PT(x+p.x , y + p.y);}
PT operator - (const PT &p) const { return PT(x-p.x , y - p.y);}
PT operator * (double c) const { return PT(x*c,y*c);}
PT operator / (double c) const { return PT(x/c,y/c);}
void input(){scanf("%lf %lf",&x,&y);}
}p[N];
double dot(PT p,PT q){ return p.x * q.x + p.y * q.y;}
double cross(PT p,PT q) {return p.x*q.y - p.y*q.x;}
double dist2(PT p,PT q) {return dot(p-q , p-q);}
double DIM(PT p) {return sqrt(p.x*p.x+p.y*p.y);}
#define PI 3.1415926535897932
#define EPS 1e-8
double calc(PT a,PT b)
{
double c = cross(a,b);
if(c >= 0){
double oo = dot(a,b) / DIM(a) / DIM(b);
if(oo>1) oo=1;
else if(oo<-1) oo= -1;
return acos(oo);
}
else {
double oo = dot(a,b) / DIM(a) / DIM(b);
if(oo>1) oo=1;
else if(oo<-1) oo= -1;
return 2*PI - acos(oo);
}
}
int main()
{
int n;
while(scanf("%d",&n)==1 && n) {
for(int i = 0; i < n ; i ++) scanf("%lf %lf",&p[i].x, &p[i].y);
double ang = 0;
PT dir = p[1]-p[0];
for(int i = 1; i < n ; i ++) {
PT newdir = p[(i+1) %n] - p[i];
ang += calc(dir, newdir);
dir = newdir;
}
ang += calc(dir, p[1] - p[0]);
printf("%.0lf\n", (ang / (2*PI)));
}
}
Uva 11510
Link : Uva 11510
Idea : Mathematical Problem.
Given
Now at least one of x , y , z is smaller then n. otherwise summation of them will never equal to 4 /n .(verify)
Iterate through x = 1 … n
We need to represent
Lemma : Suppose that n and d are relatively prime positive integers. Then n/d is the sum of two unit fractions if and only if there are positive integer divisors A and B of d such that A+B is divisible by n.
Factorisation of Q :
As Q <= n * x which can be 10^8 at most. We can factorise Q by iterating from 1 to sqrt(Q) and check.
Another way : as Q is at most multiple of n * x . then if we calculate factors of x and factors of n , then The factors of Q
is multiplication of each pair.
Now A and B is factor of Q and A + B is divisible by P. then
D = (A+B) / P;
Click to See Code
#include <bits/stdc++.h>
using namespace std;
vector<int>fac;
const int N = 1e4+5;
bool vis[N];
vector<int> F[N];
void seive()
{
for(int i = 2; i < N; i ++ ) {
F[i].push_back(1);
if(vis[i] == 0 ) {
for(int j = i; j < N; j += i) F[j].push_back(i), vis[j] = 1;
}
}
}
int main()
{
seive();
int n;
while(scanf("%d",&n)==1 && n) {
if(n%2==0) printf("%d %d %d\n",n,n,n/2);
else {
//printf("For = %d\n",n);
for(int x = n; x >= 1 ; x -- ) {
int up = 4 * x - n;
int down = x * n;
if(up < 0) break;
int k = __gcd(up,down);
up = up / k , down /= k;
set<int>S;
vector<int>temp;
fac.clear();
for(auto a: F[x]) {
for(auto b : F[n]) {
S.insert(a*b);
}
}
for(auto a: S) if(down % a) temp.push_back(a);
for(auto a: temp)S.erase(a);
for(auto a: S) fac.push_back(a);
bool f = 1;
for(int i = 0; i < fac.size() &&f; i ++ ) {
for(int j = i; j < fac.size() && f; j ++ ) {
if((fac[i] + fac[j] ) % up == 0) {
long long A = fac[i], B = fac[j];
long long D = (A+B)/up;
printf("%d %lld %lld\n", x, D * down / A , D * down / B);
f = 0;
break;
}
}
}
if(f==0) break;
}
}
}
}
Uva 11512
Link: 11512 – GATTACA
Solution: Suffix Array
This is an easy problem that can be solved using suffix array.
Build suffix array and LCP array
Now, for each i th suffix in suffix array, we know that longest Common prefix of i th and i-1 th suffix is stored in LCP[i].
So the substring starting at sa[i] of length LCP[i] has occurred in another place in the string( i-1 th suffix)
For understanding:
Let S=GAGAGAG I append a dummy end. S = G A G A G A G # index= 0 1 2 3 4 5 6 7 Suffix Array: LCP Array 7 # 0 5 AG# 0 3 AGAG# 2 1 AGAGAG# 4 6 G# 0 4 GAG# 1 2 GAGAG# 3 0 GAGAGAG# 5
Take the maximum of LCP array. What this maximum value means? Here maximum value = 5
Ans : This means, A substring of length 5 has occurred at least twice in between suffix(2) and suffix 0
So this is the longest substring that occurs at least twice.
How to determine the string ?
Ans: Go from the suffix array and stop at the first suffix which has LCP[i] = maximum_value, The substring starting from sa[i] of length maximum value is the answer and the occurance of the substring can be found by iterating the suffix array until the LCP < maximum_value
In our example: index = 0, and maximum_value = 5
For details see my implementation:
Click to See Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
char s[N];
int wa[N],wb[N],wv[N],wc[N];
int r[N],sa[N],rak[N], height[N],dp[N][22], SIGMA = 0 , n;
int cmp(int *r,int a,int b,int l){return r[a] == r[b] && r[a+l] == r[b+l];}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for( i=0;i<m;i++) wc[i]=0;
for( i=0;i<n;i++) wc[x[i]=r[i]] ++;
for( i=1;i<m;i++) wc[i] += wc[i-1];
for( i= n-1;i>=0;i--)sa[--wc[x[i]]] = i;
for( j= 1,p=1;p<n;j*=2,m=p){
for(p=0,i=n-j;i<n;i++)y[p++] = i;
for(i=0;i<n;i++)if(sa[i] >= j) y[p++] = sa[i] - j;
for(i=0;i<n;i++)wv[i] = x[y[i]];
for(i=0;i<m;i++) wc[i] = 0;
for(i=0;i<n;i++) wc[wv[i]] ++;
for(i=1;i<m;i++) wc[i] += wc[i-1];
for(i=n-1;i>=0;i--) sa[--wc[wv[i]]] = y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]] = 0,i=1;i<n;i++) x[sa[i]]= cmp(y,sa[i-1],sa[i],j) ? p-1:p++;
}
}
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) rak[sa[i]] = i;
for(i=0;i<n;height[rak[i++]] = k ) {
for(k?k--:0, j=sa[rak[i]-1] ; r[i+k] == r[j+k] ; k ++) ;
}
}
char str[1005];
int idx[150];
int main()
{
idx['A'] = 1,idx['C'] = 2,idx['T'] = 4, idx['G'] = 3;
int t;
scanf("%d",&t);
while(t--) {
scanf("%s",str);
for(int i= 0 ; str[i]; i++ )r[i] = idx[str[i]];
int n = strlen(str);
r[n] = 0;
da(r,sa,n+1,7);
calheight(r,sa,n);
int ans = 0;
for(int i = 1; i <= n; i ++ ) {
int k = height[i];
ans = max(ans,k);
}
if(ans == 0) {
printf("No repetitions found!\n");
continue;
}
for(int i = 1; i <= n; i ++ ) {
if(height[i]==ans) {// Found the answer.
int end = i;
for(int j = i+1; j <= n; j ++ ) {
if(height[j] >= ans) {// calculating the number of occurrences
end = j;
}
else break;
}
for(int j = 0; j < ans; j ++ ){
printf("%c",str[sa[i] + j]);
}
printf(" %d\n",end - i + 2);
break;
}
}
}
}
Uva 11513
Link : 11513 – 9 Puzzle
Idea: BFS
Each configuration denotes a node in the graph. We have initial configuration starting from {1,2,3,4,5,6,7,8,9}. Run bfs and calculate the distance from the Starting node.
For Horizontal Rotate ,We left rotate (reverse in direction )
For Vertical Rotate, We move down opposite to real move.
To find the path, We keep a nodes parent and by which move We have gone u->v.
Traversing node until initial, get the path
Click to See Code
#include <bits/stdc++.h>
using namespace std;
map<string,int> Map;
map<int,string> RevMap;
map<int,int> dp;
int a[3][3];
int cnt = 0;
string encode(int a[][3])
{
string s;
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < 3; j ++ ) s.push_back(a[i][j] + '0');
}
return s;
}
void decode(int u,int a[][3])
{
string s = RevMap[u];
for(int i = 0, k = 0; i < 3; i ++ )
for(int j = 0; j < 3; j ++ ){
a[i][j] = s[k] - '0';
k++;
}
return;
}
int get(string s)
{
if(Map.count(s)) return Map[s];
Map[s] = ++cnt;
RevMap[cnt] = s;
return cnt;
}
void HR(int a[][3], int row, int b[][3])
{
for(int i=0;i<3;i++)for(int j=0;j<3;j++)b[i][j]=a[i][j];
for(int j = 1; j < 3; j ++ ) b[row][j-1]= a[row][j];
b[row][2] = a[row][0];
}
void VR(int a[][3], int col, int b[][3])
{
for(int i=0;i<3;i++)for(int j=0;j<3;j++)b[i][j]=a[i][j];
for(int i = 1; i < 3; i ++) b[i][col] = a[i-1][col];
b[0][col] = a[2][col];
}
map<int,pair<int,int> > Par;
map<int,int> F;
void solve()
{
string s = encode(a);
int u = get(s);
queue<int>q;
q.push(u);
dp[u] = 0;
int b[3][3];
while(!q.empty()){
int u = q.front(); q.pop();
decode(u,a);
for(int i = 0; i < 3; i ++ ) {
HR(a,i,b);
string vs = encode(b);
int v = get(vs);
if(dp.count(v) == 0 || dp[v] > dp[u] + 1 ) {
dp[v] = 1 + dp[u];
Par[v] = make_pair(0,i);
q.push(v);
F[v] = u;
}
}
for(int i = 0; i < 3; i ++ ) {
VR(a,i,b);
string vs = encode(b);
int v = get(vs);
if(dp.count(v) == 0 || dp[v] > dp[u] + 1 ) {
dp[v] = 1 + dp[u];
Par[v] = make_pair(1,i);
F[v] = u;
q.push(v);
}
}
}
}
int main()
{
int o = 1;
for(int i = 0; i < 3; i ++) for(int j = 0; j < 3; j ++ ) a[i][j] = o , o++;
solve();
int n;
while(scanf("%d",&n) == 1 && n) {
a[0][0] = n;
scanf("%d %d",&a[0][1], &a[0][2]);
for(int i = 1; i < 3;i ++ )for(int j= 0;j<3;j++) scanf("%d",&a[i][j]);
string s = encode(a);
if(Map.count(s)) {
int u = Map[s];
vector<pair<int,int> > path;
while(u != 1) {
path.push_back(Par[u]);
u = F[u];
}
printf("%d ", (int)path.size());
for(int i = 0; i < path.size(); i ++ ) {
printf("%c%d",path[i].first==0 ? 'H' :'V', path[i].second +1);
}
printf("\n");
}
else printf("Not solvable\n");
}
}
Uva 11514
Link : 11514 – Batman
Idea: Dynamic Programming
Let’s assume we are to determine minimum power needed to destroy all the villans. As the power and vilan are to be faced according to list,We can keep each state by (index of the power, index of villan), indexing from 0
dp[i][j] = minimum power needed to destroy all villan from [j..v-1] using power only [i..p-1]
Two case:
* if the i th power can be used against j th villan , then cost1 = damage[i] + dp[i+1][j+1];
* cost2 = dp[i+1][j] // Not using
After that ,We can check if mincost <= power of batman
Click to See Code
#include <bits/stdc++.h>
using namespace std;
int p,v,e;
const int N = 1005;
char name[N][105], vl[N][105];
int at[N], dmg[N];
int def[N];
char l[1000005];
map<string,int> Map;
int Mat[N][N];
long long dp[N][N];
long long F(int p1, int p2)
{
if(p1 == p ) {
if( p2 == v) return 0;
else return 1e15;
}
if(dp[p1][p2] !=-1 )return dp[p1][p2];
long long res = 1e15;
if(Mat[p1][p2] && at[p1] >= def[p2]) res = dmg[p1] + F(p1+1, p2+1);
res = min(res, F(p1+1,p2));
return dp[p1][p2] = res;
}
int main()
{
while(scanf("%d %d %d",&p,&v,&e)==3) {
if(p==0 &&v == 0 && e == 0) break;
memset(Mat,0,sizeof Mat);
for(int i = 0;i < p; i ++) {
scanf("%s %d %d",name[i] , &at[i] , & dmg[i]);
Map[name[i]] = i;
}
for(int i = 0; i < v; i ++ ){
scanf("%s %d %s", vl[i] , &def[i] , l);
for(int i=0; l[i];i++) if(l[i]==',' )l[i]=' ';
istringstream iss (l);
string o;
while(iss >> o ) {
Mat[Map[o]][i] = 1;
}
}
memset(dp,-1,sizeof dp);
long long p = F(0,0);
if(p <= e) printf("Yes");
else printf("No");
puts("");
Map.clear();
}
}
Uva 11515
Idea: Brute Force
As the number of crane <= 15, So we can check every subset of the cranes and check if any intersection present in that subset and then Output the maximum value.
Intersection is Checked by following method:
if (distance(circle1, circle2) <= (r1 + r2) ) return INTERSECT; return NOT_INTERSECT;
Click to See Code
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int x[N],y[N],r[N];
bool iN(int i,int j)
{
long long dx = x[i] - x[j], dy = y[i] - y[j];
if(dx*dx + dy*dy <= (r[i] + r[j]) * (r[i] + r[j])) return 1;
return 0;
}
int main()
{
int t;
scanf("%d",&t);
while(t--) {
int n;
scanf("%d",&n);
for(int i = 0; i < n ;i ++) scanf("%d %d %d",&x[i],&y[i], &r[i]);
long long ans = 0;
for(int i = 0; i < 1 << n; i ++ ) {
vector<int>v;
long long can = 0;
for(int j = 0; j < n ; j ++ ) {
if(i&1<<j) {
v.push_back(j);
can += r[j] * r[j];
}
}
bool flag= 1;
for(int j = 0; j < v.size() ; j ++ ) {
for(int k = j + 1; k < v.size(); k ++ ) {
if(iN(v[j],v[k])){
flag = 0;
break;
}
}
}
if(flag) ans = max(ans, can);
}
printf("%lld\n",ans);
}
}
Uva 11516
Link : 11516 – WiFi
Solution: Binary Search + Greedy
First assume the answer, that is the maximum distance between any house. Then try to cover all the houses using n access points. Follow the binary search rules and that will give you AC.
For greedy: The first access point is placed in ( first person house co-ordinate + ans / 2 ) co-ordinate. Because, The left of first person’s house is no necessary to us. Similarly put all the other access points.
Click to See Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int x[N];
int n,m;
bool can(int M) // Try to place the access points
{
int prv = -1e8 , cnt = 0;
for(int i= 0; i < m ;i ++ ) {
if(x[i] - prv > M) {
cnt ++;
prv = x[i];
}
}
return cnt <= n;
}
int main()
{
int t;
scanf("%d",&t);
while(t--) {
scanf("%d %d",&n,&m);
for(int i = 0; i < m ;i ++ ) scanf("%d",&x[i]);
sort(x,x+m);
int low = 0, high = 1e6+6 , mid , ans = 0;
while(low <= high) {
mid = (low + high) / 2;
if(can(mid)) {
ans = mid;
high = mid-1;
}else low = mid+1;
}
printf("%.1lf\n" , ans * 1./ 2);
}
}
Uva 11517 – Exact Change
Link: 11517 – Exact Change
Idea: DP
Classical coin change dp.
First assume ans = 20000. (Because the denominator are 10000 at most).
Try to find the minimum coin needed to make i cents. Then find the answer.
Click to See Code
#include <bits/stdc++.h>
using namespace std;
int coin[105];
int dp[20005];
int main()
{
int t,n,sum;
scanf("%d",&t);
while(t--){
scanf("%d",&sum);
scanf("%d",&n);
for(int i = 0; i < n; i ++ )scanf("%d",&coin[i]);
memset(dp,-1,sizeof dp);
int N = 20005-1;
dp[0] = 0;
for(int i = 0; i < n ;i ++) {
for(int j = N; j >= coin[i] ; j--) {
if(dp[j-coin[i]] !=-1) {
if(dp[j]==-1) dp[j] = 1 + dp[j-coin[i]];
else dp[j] = min(dp[j], 1 + dp[j-coin[i]]);
if(j >= sum ) N = min(N,j);
}
}
}
printf("%d %d\n",N,dp[N]);
}
}
Uva 11518 – Dominos 2
Link : Uva 11518 – Dominos 2
Idea: DFS
For each starting point,Run a dfs . and mark the visited node.
At the end, output the # of visited nodes.
Click to See Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+1;
vector<int>G[N];
bitset<N>B;
bool vis[N];
void dfs(int u)
{
if(vis[u]) return;
B[u] = 1;
vis[u] = 1;
for(int i = 0; i < G[u].size(); i ++ ) {
int v = G[u][i];
dfs(v);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--) {
int n,m,l;
scanf("%d %d %d",&n,&m,&l);
for(int i = 0; i < m ; i ++) {
int a,b;
scanf("%d %d",&a,&b);
G[a].push_back(b);
}
memset(vis,0,sizeof vis);
B.reset();
for(int i = 0; i < l ; i ++ ) {
int p;
scanf("%d",&p);
dfs(p);
}
printf("%ld\n",B.count());
for(int i = 1;i <= n; i ++) G[i].clear();
}
}
Uva 11519 – Logo 2
Link: Uva 11519 – Logo 2
Idea:
Let's assume the starting position is (0,0).
If the missing is "fd" or "bk"
We execute all the commands and lets finally we are at point P(x,y) and
while we are about to execute "fd" or "bk"
command, we have direction d;
so, for fd,
we have P + d * L = 0, We can write this equation as
x + d_x * L =0, L = -x/d_x , considering x-part
Again for "bk"
We have P - d * L = 0
x - d_x * L = 0, L = x / d_x , considering only x-part
L is the final answer.
if the missing command is type of "lt" or "rt":
as the answer is integer, so we try all possible angle in [0,360], and
see if we can be back in the starting position.
Only problem about solving this was EPS = 1e-2
Click to See Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
string command[N];
int value[N];
struct PT {
double x,y;
PT(){}
PT(double x,double y):x(x),y(y){}
PT operator + (const PT &p) const {return PT(x+p.x,y+p.y);}
PT operator - (const PT &p) const {return PT(x-p.x,y-p.y);}
PT operator * (double c) const { return PT(x*c, y *c);}
PT operator / (double c) const { return PT(x/c, y /c);}
double mag(){return sqrt(x*x+y*y);}
};
PT RotCCW(PT p,double ang) {return PT(p.x*cos(ang) - p.y*sin(ang) , p.x*sin(ang) + p.y * cos(ang));}
#define PI 0.01745329251994329914588889
#define EPS 1e-2
int n;
PT F;
PT calc(int par= -1)
{
PT pivot = PT(0,0) , dir = PT(1,0);
for(int i = 0; i < n ; i ++ ) {
if(i==par) {
F= dir;
continue;
}
string cmd = command[i];
double d = value[i];
if(cmd.compare("fd")== 0) pivot = pivot + dir * d;
if(cmd.compare("bk")== 0) pivot = pivot - dir * d;
if(cmd.compare("lt")== 0) d = PI * d , dir = RotCCW(dir,d);
if(cmd.compare("rt")== 0) d = PI * d , dir = RotCCW(dir, - d) ;
}
return pivot;
}
int main()
{
int t, id ;
cin >> t;
while(t-- ) {
cin>> n;
id = 0;
for(int i = 0; i < n ; i ++ ) {
string cmd,t;
cin >> cmd >> t;
if(t.compare("?") == 0) {
id = i;
command[i] = cmd;
}
else {
command[i] = cmd;
value[i] = atoi(t.c_str());
}
}
if(command[id].compare("fd") == 0 || command[id].compare("bk") == 0) {
PT f = calc(id);
int sig = (command[id].compare("fd") == 0 ? -1 : 1);
printf("%.0lf\n", f.x / F.x * sig + EPS );
}
else {
for(int ang = 0; ang < 360; ang ++ ) {
value[id] = ang;
PT r = calc();
if(fabs(r.mag()) < EPS) {
printf("%d\n", ang);
break;
}
}
}
}
}
Uva 11520 – Fill the Square
Link: 11520 – Fill the Square
Idea: Adhoc
Iterate the grid into row major order.
for each cell,
if it is empty:
We try to put smallest letter so that its adjacent cells don't have this letter.
Put the letter .
As size of letter is 26, So in a cell ,we will never run out of option. Thats why greedy choice works.
else do nothing
Output the grid
Click to See Code
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
string grid[N];
int n ;
bool valid( int x, int y)
{
if( x < 0 || y < 0 || x >= n || y >= n ) return false;
return true;
}
int dir[][2] = {{0,1},{0,-1},{-1,0},{1,0}};
int main()
{
int tc ,cs = 0 ;
scanf("%d",&tc);
while (tc -- ) {
scanf("%d",&n);
for( int i = 0; i < n ; i ++ ) {
cin >> grid[i];
}
for(int i =0 ; i < n ; i ++ ) {
for (int j = 0 ; j < n ; j ++ ) {
if(grid[i][j] !='.') continue;
for( int p = 0 ; p < 26 ;p ++ ) {
bool flag = true;
for( int d = 0 ; d < 4 ; d ++ ) {
int x = i + dir[d][0];
int y = j + dir[d][1];
if(valid(x,y) && grid[x][y] == p + 'A' ) {
flag = false;
}
}
if( flag ) {
grid[i][j] = p +'A';
break;
}
}
}
}
printf("Case %d:\n" , ++cs) ;
for( int i = 0 ;i < n ; i ++) {
for ( int j = 0; j < n ; j ++ ) {
printf("%c",grid[i][j] );
}
printf("\n");
}
}
return 0;
}
Uva 11522 – Pyramid Number
Link :11522 – Pyramid Number
Idea: Recursion + Observation
Using Recursion , first generate some strictly pyramid numbers up to 150. You can see all the numbers greater than 77 is pyramid number. So you only need to generate [1,77] which are not pyramid numbers and this can be done using recursion.
See my implementation for details
Click to See Code
#include <bits/stdc++.h>
using namespace std;
bool flag[101];
const double EPS = 1e-8;
bool dfs(int sum,int p,double fr)
{
if(fr> 1 + EPS || sum < 0) return 0;
if(sum==0){
if(fabs(fr-1) < EPS) return 1;
return 0;
}
if(p>sum) return 0;
return dfs(sum-p,p+1,fr + 1./p) || dfs(sum,p+1,fr);
}
int main()
{
memset(flag,1,sizeof flag);
for(int i= 2; i <= 77; i ++ ) {// Checking pyramid numbers.
if(dfs(i,2,0) == 0) {
flag[i] = 0;
}
}
int t,a,b;
scanf("%d",&t);
while(t--) {
scanf("%d %d",&a,&b);
if(a>b)swap(a,b);
int cnt = 0;
while(a<=77 && a<= b) {
if(flag[a]) cnt++;
a++;
}
cnt += b - a + 1;
printf("%d\n",cnt);
}
}
Uva 11523 – Recycling
Idea : Dynamic Programming
It is a standard Interval Dp problem.
Since it is not allowed to move non-recyclable elements, we can take each maximal contiguous subsequence between non-recyclable materials and solve them independently using an dynamic programming. We need to minimise cost in interval (i,j) inclusive.
First Map the strings into an interger and create an array. A series of same number is replaced by only one integer [1,2,2,2,1] => [1,2,1]
For an interval, We have two case:
* Pick only the ith element. In this case dp(i,j) = 1 + dp(i+1,j)
* for each k in [i+1,j] :
if array[i] = array[k] :
We can pick ith element with k th element.
dp(i,j) = min(dp(i,j) , dp(i+1,k) + dp(k+1,j));
So for removing [i+1,k] segment, when we are about to pick the kth element ,
We pick all the elements in interval [i+1,k-1] and pick ( ith and kth )
element in a single move.
Again the optimal cost for removing [k+1,j] interval.
Try to think about this recursive relations. They never pop into mind easily.
Simmilar Problem:
1. Topcoder – MailArchiving
2. Uva 11283
Click to See Code
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
map<string,int> Name;
int cnt = 0;
int val(string s)
{
if(Name.count(s)) return Name[s];
Name[s] = ++cnt;
return cnt;
}
int ar[N];
int dp[N][N];
int n;
vector<int>v;
int F(int i,int j)
{
if(i>j) return 0;
if(i==j) {
return 1;
}
if(dp[i][j] !=-1) return dp[i][j];
int res = 1e5;
res = F(i+1,j) + 1;
for(int k = i+1; k <= j ; k ++ ) {
if(v[k] == v[i]) {
res = min(res , F(i+1,k) + F(k+1,j));
}
}
return dp[i][j] =res;
}
int main()
{
int t,cs = 0;
cin>>t;
while(t--) {
cin >> n;
string s;
cnt=0;
for(int i = 0; i < n ;i ++ ) {
cin >> s;
if(islower(s[0])) {
ar[i] = val(s);
}
else {
ar[i] = 0;
}
}
int prv = -1;
v.clear();
for(int i = 0; i < n ;i ++ ) {
if(ar[i] != prv) {
v.push_back(ar[i]);
prv = ar[i];
}
}
memset(dp,-1,sizeof dp);
vector<int> R;
R.push_back(-1);
for(int i = 0; i < v.size();i ++ ) if(v[i] == 0) R.push_back(i);
R.push_back(v.size());
int ans = 0;
for(int i = 0; i < R.size()-1; i ++ ) {
ans += F(R[i]+1, R[i+1]-1);
}
printf("Case %d: %d\n",++cs, ans);
Name.clear();
}
}
Uva 11524 – InCircle
Link : 11524 – InCircle
Idea: Binary Search and Geometry
First assume BP = x, Then We know AP from BP,
Now AP = AR ( Proof ? )
Then, We know CR from AR , Again, CQ = CR and calculate BQ from CQ
The equation can be written as follows:
double BP = x;
double AP = m1*BP/n1;
double AR = AP;
double CR = m3 * AR / n3;
double CQ = CR;
double BQ = m2 * CQ / n2;
Now we have length of each sides and can calculate the area of the triangle by herons formula.
From trigonometry, We know radius of incircle of a triangle = Area/(s) where s = perimeter of triangle / 2
So we check if this radius is smaller of larger than give r and work accordingly.
Click to See Code
#include <bits/stdc++.h>
using namespace std;
#define PI acos(-1.0)
double r,m1,n1,m2,n2,m3,n3;
double Tri(double a,double b,double c)
{
double s = (a+b+c)/2;
if(a > s || b > s || c > s) return -1;
return sqrt(s*(s-a)*(s-b)*(s-c));
}
double area;
double calc(double mid)
{
double BP = mid;
double AP = m1 *BP/n1;
double AR = AP;
double CR = m3 * AR / n3;
double CQ = CR;
double BQ = m2 * CQ / n2;
area = Tri(BQ + CQ , AR + CR, BP + AP);
return 2 * area / (BQ + CQ + AR + CR + BP + AP);
}
int main()
{
int t;
cin>>t;
while(t--) {
scanf("%lf %lf %lf %lf %lf %lf %lf",&r,&m1,&n1,&m2,&n2,&m3,&n3);
double low = 0, high = 1e9 , mid , ans;
for(int i = 0; i < 100 ; i ++ ) {
mid = (low+high) / 2;
double r2 = calc(mid);
if(r2 < r) low = mid;
else high = mid;
}
calc(low);
printf("%.4lf\n",area);
}
}
Uva 11525 – Permutation
Link: 11525 – Permutation
Idea: Binary Indexed Tree
For each Si, We need to calculate what is the smallest integer in the current list which has Si numbers smaller in the list.
For example:
4
1 2 1 0At first, We have {1,2,3,4}
Now S1 = 1,What is the smallest number in the current list which has 1 number smaller than his ?
Ans: 2.
Because 1 is smaller than 2. So we output 2 and remove from the list.
Now list = {1,3,4}S2 = 2 ,What is the smallest number in the current list which has 2 number smaller than his ?
Ans: 4.
1 and 3 are smaller than 4,
List = {1,3}S3 = 1,What is the smallest number in the current list which has 1 number smaller than his ?
Ans : 3
List = {1}S4 = 0 ,
Ans = 1
We need an efficient data structure that solves our query and removal from the list. BIT is one of the solution. You can use SG tree also.
For BIT , see here
Click to See Code
#include <bits/stdc++.h>
using namespace std;
int k;
int M;
int B[100005];
void update(int x,int v)
{
while(x<=M) B[x] += v, x+=x&-x;
}
int bs(int x)
{
int r = 0, d = M;
while(d && r < M) {
int t = r + d;
if( x >= B[t]) {
x -= B[t];
r = t;
}
d/=2;
}
return r+1;
}
int main()
{
int t,p;
scanf("%d",&t);
while(t--){
scanf("%d",&k);
memset(B,0,sizeof B);
M = 1;
while(M<=k) M*=2;
for(int i = 1; i <= k; i ++ ) update(i,1);
for(int i = 0; i < k; i ++ ) {
scanf("%d",&p);
int k = bs(p);
update(k,-1);
if(i)printf(" ");
printf("%d",k);
}
puts("");
}
}
Uva 11526 – H(n)
Link : 11526 – H(n)
Idea: Adhoc, Math
We count from both ends.
prev = n sum = 0; for each i = 1 to sqrt(n): k = n/i, so every number in range [k+1,prev] if we divide n by them, the output divident will be same i-1. sum += k + (prev - k) * (i-1); prev= k
To avoid over counting, I break the loop when k – i < 3
Click to See Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n ,sum = 0 , prev, test ;
cin >> test;
while (test -- ) {
cin >> n;
prev = n ;
sum = 0 ;
for (long long i = 1; i * i <= n ; i ++) {
long long k = ( n / i );
sum = sum + (prev - k ) * (i-1);
sum += k ;
prev = k ;
if( k - i < 3){
for (long long j = i + 1; j <= k ; j ++) {
sum += n / j;
}
break;
}
}
printf("%lld\n",sum);
}
return 0;
}
Another Solution from wiki :
This solution is rather easy.
Click to See Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n ,sum = 0 , prev, test ;
cin >> test;
while (test -- ) {
cin >> n;
int sqn = sqrt(n);
long long sum = 0;
for(int i = 1; i <= sqn; i++ ) {
sum += n/i * 2;
}
printf("%lld\n",sum - sqn*sqn);
}
return 0;
}
Uva 11560 – Fixing the Bugs
Link : Uva 11560
Idea : DP, Greedy , Math
Solution :
The problem is bit difficult for my current level. So I searched over the net and found a good post how to solve this problem.
Here is the Link : Solution
Click to See Code
#include <bits/stdc++.h>
using namespace std;
int b,t,CS = 1;
double f;
double p[12];
int s[12];
double dp[1<<10][105][105];
int vis[1<<10][105][105];
int fail[12];
double calc(int Mask, int T, int F )
{
if(Mask+1 == (1<<b))return 0;
if(T == 0 ) return 0;
if(vis[Mask][T][F] == CS) return dp[Mask][T][F];
int id = -1;
double iM = -1e8;
for(int i= 0;i < b; i++) {
if(!(Mask & 1 << i)) {
if(p[i] * s[i] > iM ) {
iM = p[i] * s[i];
id = i;
}
}
}
double res = p[id] * (s[id] + calc(Mask | 1 << id , T-1, F - fail[id]));
double prv = p[id];
p[id] *= f;
fail[id] ++;
res += (1- prv) * calc(Mask, T -1 , F + 1);
p[id] = prv;
fail[id] --;
vis[Mask][T][F] = CS;
return dp[Mask][T][F] = res ;
}
int main()
{
while(scanf("%d %d %lf",&b,&t,&f)==3) {
for(int i = 0; i < b; i ++ ) scanf("%lf %d",&p[i],&s[i]);
printf("%.9lf\n", calc(0,t,0));
CS ++;
}
}
Uva 11561 – Getting Gold
Link : Uva 11561
Idea : BFS, Graph
solution: The square which is near to trap, we can visit it but can not go anywhere from that. This is main trick.
Click to See Code
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
int r,c, x , y;
char grid[55][55];
bool vis[55][55], draft[55][55];
int dir[][2] = {{0,1},{0,-1},{1,0},{-1,0}};
bool ok(pair<int,int> a)
{
if(a.first >= 0 && a.first < r && a.second >= 0 && a.second < c && grid[a.first][a.second] != '#' && grid[a.first][a.second] != 'T') return 1;
return 0;
}
void solve()
{
memset(draft,0,sizeof draft);
for(int i = 0; i < r; i ++ ) {
for(int j = 0; j < c; j ++) {
if(grid[i][j] == 'T') {
for(int k = 0; k < 4; k ++ ) {
int xp = i + dir[k][0];
int yp = j + dir[k][1];
if(ok(MP(xp,yp))) draft[xp][yp] = 1;
}
}
}
}
if(draft[x][y]) {printf("0\n");return;}
memset(vis,0,sizeof vis);
vis[x][y] =1;
queue<pair<int,int> > q;
q.push(MP(x,y));
while(!q.empty()){
auto a = q.front(); q.pop();
for(int i = 0; i < 4; i ++ ) {
auto b = MP(a.first + dir[i][0] , a.second + dir[i][1]);
if(ok(b) && vis[b.first][b.second] == 0 ) {
vis[b.first] [b.second] = 1;
if(draft[b.first][b.second] == 0)q.push(b);
}
}
}
int cnt = 0;
for(int i= 0;i < r; i ++)
for(int j = 0; j < c; j ++ ) {
if(vis[i][j] && grid[i][j] == 'G' ) cnt ++;
}
printf("%d\n",cnt);
}
int main()
{
while(scanf("%d %d",&c,&r)==2) {
for(int i =0 ; i < r;i ++) scanf("%s", grid[i]);
for(int i = 0; i < r;i ++) {
for(int j = 0; j < c; j ++ ) {
if(grid[i][j] == 'P') {
x = i, y = j;
}
}
}
solve();
}
}
/*
7 4
#######
#P.GTG#
#..TGG#
#######
8 6
########
#...GTG#
#..PG.G#
#...G#G#
#..TG.G#
########
4 4
####
#TP#
#GG#
####
*/
Code for Fun 