Subhashis_Mollick's Blog

আমার ব্লগে আপনাকে স্বাগতম...... আমি সুভাশিষ মল্লিক... পড়াশোনা করছি কুষ্টিয়ার ইসলামী বিশ্ববিদ্যালয়ের কম্পিউটার সায়েন্স এন্ড ইঞ্জিনিয়ারিং বিভাগে... প্রোগ্রামিং করতে অনেক ভালো লাগে আর তার চেয়েও বেশি ভালো লাগে প্রোগ্রামিং এর যেকোনো কাজে কাওকে সাহায্য করতে,আর সেই জন্যই আমার এই ব্লগ... আপনার জন্যই আমার এই ব্লগ... নিজে প্রোগ্রামিং করুন ও অন্যকে প্রোগ্রামিং করতে উৎসাহ প্রদান করুন.... Happy Coding

শুক্রবার, ৩১ মে, ২০১৯

UVA 706 LC-Display

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
using namespace std;

char a[1000][1000];

void one(int s, int pos)
{
int m,i,j,x,y,p,q;
x=s+2;
y=2*s+3;
m=(y+1)/2;
p=(x*(pos-1))+pos;
q=p+x-1;
for(i=2; i<y; i++)
if(i!=m)
a[i][q]='|';
}
void two(int s, int pos)
{
int m,i,j,x,y,p,q;
x=s+2;
y=2*s+3;
m=(y+1)/2;
p=(x*(pos-1))+pos;
q=p+x-1;
for(i=2; i<m; i++)
a[i][q]='|';
for(i=m+1; i<y; i++)
a[i][p]='|';
for(j=p+1; j<q; j++)
{
a[1][j]='-';
a[m][j]='-';
a[y][j]='-';
}
}
void three(int s, int pos)
{
int m,i,j,x,y,p,q;
x=s+2;
y=2*s+3;
m=(y+1)/2;
p=(x*(pos-1))+pos;
q=p+x-1;
for(i=2; i<y; i++)
if(i!=m)
a[i][q]='|';
for(j=p+1; j<q; j++)
{
a[1][j]='-';
a[m][j]='-';
a[y][j]='-';
}
}
void four(int s, int pos)
{
int m,i,j,x,y,p,q;
x=s+2;
y=2*s+3;
m=(y+1)/2;
p=(x*(pos-1))+pos;
q=p+x-1;
for(i=2; i<m; i++)
a[i][p]='|';
for(i=2; i<y; i++)
if(i!=m)
a[i][q]='|';
for(j=p+1; j<q; j++)
a[m][j]='-';
}
void five(int s, int pos)
{
int m,i,j,x,y,p,q;
x=s+2;
y=2*s+3;
m=(y+1)/2;
p=(x*(pos-1))+pos;
q=p+x-1;
for(i=2; i<m; i++)
a[i][p]='|';
for(i=m+1; i<y; i++)
if(i!=m)
a[i][q]='|';
for(j=p+1; j<q; j++)
{
a[1][j]='-';
a[m][j]='-';
a[y][j]='-';
}
}
void six(int s, int pos)
{
int m,i,j,x,y,p,q;
x=s+2;
y=2*s+3;
m=(y+1)/2;
p=(x*(pos-1))+pos;
q=p+x-1;
for(i=2; i<y; i++)
if(i!=m)
a[i][p]='|';
for(i=m+1; i<y; i++)
a[i][q]='|';
for(j=p+1; j<q; j++)
{
a[1][j]='-';
a[m][j]='-';
a[y][j]='-';
}
}
void seven(int s, int pos)
{
int m,i,j,x,y,p,q;
x=s+2;
y=2*s+3;
m=(y+1)/2;
p=(x*(pos-1))+pos;
q=p+x-1;
for(i=2; i<y; i++)
if(i!=m)
a[i][q]='|';
for(j=p+1; j<q; j++)
a[1][j]='-';
}
void eight(int s, int pos)
{
int m,i,j,x,y,p,q;
x=s+2;
y=2*s+3;
m=(y+1)/2;
p=(x*(pos-1))+pos;
q=p+x-1;
for(i=2; i<y; i++)
if(i!=m)
{
a[i][p]='|';
a[i][q]='|';
}
for(j=p+1; j<q; j++)
{
a[1][j]='-';
a[m][j]='-';
a[y][j]='-';
}
}
void nine(int s, int pos)
{
int m,i,j,x,y,p,q;
x=s+2;
y=2*s+3;
m=(y+1)/2;
p=(x*(pos-1))+pos;
q=p+x-1;
for(i=2; i<y; i++)
if(i!=m)
a[i][q]='|';
for(i=2; i<m; i++)
a[i][p]='|';
for(j=p+1; j<q; j++)
{
a[1][j]='-';
a[m][j]='-';
a[y][j]='-'
;
}
}
void zero(int s, int pos)
{
int m,i,j,x,y,p,q;
x=s+2;
y=2*s+3;
m=(y+1)/2;
p=(x*(pos-1))+pos;
q=p+x-1;
for(i=2; i<y; i++)
if(i!=m)
{
a[i][p]='|';
a[i][q]='|';
}
for(j=p+1; j<q; j++)
{
a[1][j]='-';
a[y][j]='-';
}
}

int main()
{
int x,y,i,k,s,f,j,l;
string n;
while(cin>>s>>n)
{
stringstream nt(n);
nt>>l;
if(s==0 && l==0)
return 0;
x=s+2;
y=2*s+3;
f=(n.length()*x)+n.length()-1;
for(i=1; i<=y; i++)
for(j=1; j<=f; j++)
a[i][j]=' ';
for(k=0; k<n.length(); k++)
{
if(n[k]-'0'==1)
one(s,k+1);
else if(n[k]-'0'==2)
two(s,k+1);
else if(n[k]-'0'==3)
three(s,k+1);
else if(n[k]-'0'==4)
four(s,k+1);
else if(n[k]-'0'==5)
five(s,k+1);
else if(n[k]-'0'==6)
six(s,k+1);
else if(n[k]-'0'==7)
seven(s,k+1);
else if(n[k]-'0'==8)
eight(s,k+1);
else if(n[k]-'0'==9)
nine(s,k+1);
else if(n[k]-'0'==0)
zero(s,k+1);
}
for(i=1; i<=y; i++)
{
for(j=1; j<=f; j++)
cout<<a[i][j];
cout<<endl;
}
cout<<endl;
}
return 0;
}

UVA 13244 - Space Happiness

#include<bits/stdc++.h>
using namespace std;
int main()
{
long long num,t,sum=0;
cin>>t;
while(t--)
{
cin>>num;
for(long long i=1; i<=num; i++)
{

if(i%2!=0)
{
if(i==num)
sum+=i;
else
sum+=2*i;
}
}
cout<<sum<<endl;
sum=0;
}
return 0;
}

UVA 13130 - Cacho

#include <cstdio>

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int a1, a2, a3, a4, a5;
scanf("%d %d %d %d %d", &a1, &a2, &a3, &a4, &a5);
puts(
(a1 == 1 && a2 == 2 && a3 == 3 && a4 == 4 && a5 == 5 ||
a1 == 2 && a2 == 3 && a3 == 4 && a4 == 5 && a5 == 6) ? "Y" : "N");
}
return 0;
}

UVA 11839 - Optical Reader

#include<stdio.h>
int main()
{
char ans[5]={'A','B','C','D','E'};
int t,i,x,pos,a;
while(scanf("%d",&t) &&t!=0)
{
while(t--)
{
x=0;
for(i=0;i<5;i++)
{
scanf("%d",&a);
if(a<=127) {x++;pos=i;}
}
if(x>1||x==0) printf("*\n");
else printf("%c\n",ans[pos]);
}
}
return 0;
}

শুক্রবার, ২৪ মে, ২০১৯

Dijkstra: Shortest Reach 2 (Hackerrank)

একটা সোর্স থেকে অন্য সকল নোডের মিনিমাম দুরুত্ত বের করে
INPUT:
1
4 4
1 2 24
1 4 20
3 1 3
4 3 12
1

OUTPUT:
24 3 15

#include<bits/stdc++.h>
using namespace std;
#define wl(n) while(n--)
#define fl(i,a,b) for(i=a; i<b; i++)
#define rev(i,a,b) for(i=a; i>=b; i--)
#define scan(n) scanf("%d", &n)
#define scans(s) scanf("%s", s)
#define scanc(c) scanf("%c", &c)
#define scanp(f) scanf("%f", &f)
#define print(n) printf("%d\n", n)
#define prints(s) printf("%s\n", s)
#define printc(c) printf("%c\n", c)
#define printp(f) printf("%f\n", f)
#define nline printf("\n")
#define mclr(strn) strn.clear()
#define ignr cin.ignore()
#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define PB push_back
#define SZ size
#define MP make_pair
int dist[3005];
bool vis[3005];
std::vector<int> adj[3003];
int mat[3005][3005];
queue<pair<int,int> > pro;
int n, e;
int main()
{
int i, j;
int cases;
scan(cases);
wl(cases)
{
cin>>n>>e;
fl(i,0,n+1)
{
adj[i].clear();
vis[i]=0;
dist[i]=0;
dist[i]=INT_MAX;
}
fl(i,0,n+1)
fl(j,0,n+1)
mat[i][j]=INT_MAX;
fl(i,0,e)
{
int x, y;
cin>>x>>y;
adj[x].PB(y);
adj[y].PB(x);
int val;
cin>>val;
mat[x][y]=mat[y][x]=min(val,mat[x][y]);
}
int ini;
cin>>ini;
int node=ini;
dist[node]=0;
vis[node]=1;
fl(i,0,n-1)
{
int this_dist=INT_MAX;
fl(j,1,n+1)
{
if(!vis[j] && dist[j]<this_dist)
{
this_dist=dist[j];
node=j;
}
}
vis[node]=1;
int limit=adj[node].SZ();
fl(j,0,limit)
{
if(!vis[adj[node][j]] && dist[node]+mat[node][adj[node][j]]<dist[adj[node][j]])
{
dist[adj[node][j]]=dist[node]+mat[node][adj[node][j]];
}
}
}
fl(i,1,n+1)
{
if(i==ini)
continue;
if(dist[i]==INT_MAX)
cout<<-1;
else
cout<<dist[i];
cout<<" ";
}
cout<<endl;
}
return 0;
}

বৃহস্পতিবার, ২৩ মে, ২০১৯

UVA 10025 - The ? 1 ? 2 ? ... ? n = k problem

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define timesave ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
main()
{
timesave;
long ts,cs=1;
cin>>ts;
while(ts--)
{
ll n,sum=0,x,i;
cin>>n;
if(cs>1)
cout<<endl;
cs=2;
n=abs(n);
for(i=1;; i++)
{
sum+=i;
if(sum>=n)
{
x=sum-n;
if(x%2==0)
{
break;
}
}
}
cout<<i<<endl;
}
}

Graph Minimum distance

Problem Link: https://toph.co/p/road-minister-techboy

এখানে বলা হয়েছে যে ১ হল রুট
১ থেকে আমার সব নোডে যাওয়া লাগবে তাহলে মিনিমাম কত ডিস্ট্যান্স লাগবে?
এক নোড থেকে অন্য টায় যেতে এবং ব্যাক আসতে হলে দুইটা ডিস্ট্যান্স ই যোগ করা লাগবে

INPUT:
2
3
1 2 3
2 3 4
3
1 2 3
1 3 3

OUPUT:
Case 1: 7
Case 2: 9

প্রথম টার জন্য ৩+৪=৭
আর ২য় টার জন্য ১->২=৩,২->১=৩,১->৩=৩ মোট হবে ৩+৩+৩=৯

#include<bits/stdc++.h>
using namespace std;
#define LL long long
vector<LL>graph[10003], cost[10003];
bool visited[10003];
int level[10003];
LL node, temp;

void DFS(LL u, LL sum)
{
visited[u] = true;
if(sum>temp)
{
temp = sum;
node = u;
}
for(int i=0; i<graph[u].size(); i++)
{
LL v = graph[u][i];
if(!visited[v])
{
level[v] = level[u] + 1;
DFS(v, sum+cost[u][i]);
}
}
return;
}

LL DFS2(LL u)
{
visited[u] = true;
if(u==1)
{
return 0;
}
LL sum = 0;
for(int i=0; i<graph[u].size(); i++)
{
LL v = graph[u][i];
if(!visited[v] && level[v]<level[u])
{
sum = sum + cost[u][i] + DFS2(v);
}
}
return sum;
}
int main()
{
int test;
scanf("%d", &test);
for(int i=1; i<=test; i++)
{
for(int i=0; i<=10000; i++)
{
graph[i].clear();
cost[i].clear();
level[i] = 0;
}
LL n, e, u, v, w;
scanf("%lld", &n);
LL ans = 0;
for(int i=1; i<n; i++)
{
scanf("%lld %lld %lld", &u, &v, &w);
graph[u].push_back(v);
graph[v].push_back(u);
cost[u].push_back(w);
cost[v].push_back(w);
ans = ans + 2*w;
}
memset(visited,false,sizeof(visited));
node = 0;
temp = 0;
level[1] = 1;
DFS(1, 0);
memset(visited,false,sizeof(visited));
LL bad = DFS2(node);
printf("Case %d: %lld\n",i,ans - bad);
}
return 0;
}

মঙ্গলবার, ২১ মে, ২০১৯

UVA 10539 - Almost Prime Numbers { Important }

Almost prime numbers are the non-prime numbers which are divisible by only a single prime number. In this problem your job is to write a program which finds out the number of almost prime numbers within a certain range.
Limit: Low and high (0 < low ≤ high < 10^12).
Input:
3
1 10
1 20
1 5
Output:
3
4
1

Secuence:- 4 8 9 16 25 27 32 49 64 81..........................

From 1 to 10 ans is 4,8,9
So output 3
From 1 to 20 ans is 4,8,9,16
So output 4
From 1 to 5 ans is 4
So output 1

#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#define sz 1000001
using namespace std;
vector<int>prime;
vector<long long int>ans;
bool flag[1000001];
int prsz;
void sieve(void)
{
int i,j,add;
flag[0]=flag[1]=1;
prime.push_back(2);
for(i=4; i<sz; i+=2)
flag[i]=1;
for(i=3; i<sz; i+=2)
{
if(!flag[i])
{
prime.push_back(i);
if(sz/i>=i)
{
add=i*2;
for(j=i*i; j<sz; j+=add)
flag[j]=1;
}
}
}
}
int main()
{
sieve();
long long int i,k,szp,j;
szp=prime.size();
for(i=0; i<sz; i++)
{
if(!flag[i])
for(j=i*i; j<1000000000001; j*=i)
ans.push_back(j);
}
sort(ans.begin(),ans.end());
int tst,count,ansz;
ansz=ans.size();
long long x,y;
scanf("%d",&tst);
while(tst--)
{
count=0;
scanf("%lld %lld",&x,&y);
i=0;
while(ans[i]<x)
i++;
for(; i<ansz && ans[i]<=y; i++)
count++;
printf("%d\n",count);
}
return 0;
}

SPOJ QTREE2 - Query on a tree II

Dist দিলে a,b এর মধ্যে Distance বের করতে হবে

আর kth দিলে a থেকে b যেতে kth তম নোড কোনটা?

DIST a b : ask for the distance between node a and node b
or
KTH a b k : ask for the k-th node on the path from node a to node b

1

6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
DIST 4 6
KTH 4 6 4
DONE

Output:
5
3

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 10005
using namespace std;
struct edge
{
int to,next,w;
} e[N<<1];
int head[N],cnt;
void add(int u,int v,int w)
{
e[++cnt]=(edge)
{
v,head[u],w
};
head[u]=cnt;
}
int n;
int deep[N],dis[N],p[N][30];
void dfs(int x,int fa)
{
deep[x]=deep[fa]+1;
p[x][0]=fa;
for(int i=0; p[x][i]; i++)
p[x][i+1]=p[p[x][i]][i];
for(int i=head[x]; i; i=e[i].next)
{
int to=e[i].to;
if(to==fa)
continue;
dis[to]=dis[x]+e[i].w;
dfs(to,x);
}
}
int lca(int a,int b)
{
if(deep[a]<deep[b])
swap(a,b);
for(int j=14; j>=0; j--)
if(deep[a]-(1<<j)>=deep[b])
a=p[a][j];
if(a==b)
return a;
for(int j=14; j>=0; j--)
if(p[a][j]&&p[a][j]!=p[b][j])
{
a=p[a][j];
b=p[b][j];
}
return p[a][0];
}
int get(int u,int d)
{
for(int j=14; j>=0; j--)
if(deep[u]-(1<<j)>=d)
u=p[u][j];
return u;
}
int main()
{
int t;
cin>>t;
while(t--)
{
memset(head,0,sizeof head);
memset(p,0,sizeof p);
cnt=0;
cin>>n;
for(int i=1; i<n; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dfs(1,0);
char op[100];
while(1)
{
scanf("%s",op);
if(op[1]=='O')
break;
if(op[1]=='I')
{
int u,v;
scanf("%d%d",&u,&v);
printf("%d\n",dis[u]+dis[v]-2*dis[lca(u,v)]);
}
else
{
int u,v,k;
scanf("%d%d%d",&u,&v,&k);
int fa=lca(u,v),d;
if(deep[u]-deep[fa]<k)
{
d=deep[fa]+k-(deep[u]-deep[fa]+1);
u=v;
}
else
d=deep[u]-k+1;
printf("%d\n",get(u,d));
}
}
}
}

Bigmod in iteraive way (1 <= A, B <= 1000000000000000000, 1 < M < 1000000000).

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

long long Power(long long BaSe,long long PoWeR,long long MoD){
//if BaSe zero
BaSe%=MoD;
long long ret=1;
while(PoWeR>0){
if(PoWeR&1) ret=(ret*BaSe)%MoD;
PoWeR>>=1;
BaSe=(BaSe*BaSe)%MoD;
}
if(ret==0) return MoD;
return ret;
}

main(){
int Case;
scanf("%d",&Case);
while(Case--){
long long a,b,m;
scanf("%lld %lld %lld",&a,&b,&m);
printf("%lld\n",Power(a,b,m));
}
return 0;
}

সোমবার, ২০ মে, ২০১৯

Russian Peasunt Theorem

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

///pre-processing
#define gcd(a, b) __gcd(a,b)
#define lcm(a, b) (a * b) / gcd(a, b)
#define loop(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define mem(a, x) memset(a,x,sizeof a)
#define endl '\n'
#define ss second
#define ff first
#define TN typename

///input functions
int Int(){int x;scanf("%d",&x);return x;}
long long Long(){long long x;scanf("%lld",&x);return x;}
double Double(){double x;scanf("%lf",&x);return x;}

///input functions shorting
#define Int Int()
#define Long Long()
#define Double Double()
#define Float Float()
const int N = (int) 1e5 + 5;
unsigned long long peasant(unsigned long long a, unsigned long long b, unsigned long long MOD){
unsigned long long res = 0;
while(b){
if(b & 1){res += (a % MOD), res %= MOD;}
a <<= 1;
a %= MOD;
b >>= 1;
}
return res;
}
unsigned long long bigMod (unsigned long long base, unsigned long long power, unsigned long long MOD){
long long res = 1;
while (power){
if (power & 1){
res = peasant(res, base, MOD) % MOD;
}
base = peasant(base, base, MOD) % MOD;
power = power >> 1;
}
return res;
}
int main()
{
int t, cs = 0;
cin>>t;
while(t--){
/// printf("Case %d: ", ++cs);
unsigned long long a, b, c;
cin >> a >> b >> c;
cout << bigMod(a, b, c) <<endl;
}
return 0;
}

বৃহস্পতিবার, ৯ মে, ২০১৯

print ( a^b ) mod m (a and b both will be integer numbers of at most 10^5 digits.)

There will be multiple test cases in each input file . Each line of the input file will contain three integer numbers a , band m (1 ≤ m ≤ 1.5*109).

a and b both will be integer numbers of at most 105 digits.

For each case, print ( ab ) mod m in a new line.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
ll bigmod(ll b, ll p, ll m)
{
ll res = 1%m, k = b%m;
while(p)
{
if(p&1)
res = (res*k)%m;
k = (k*k)%m;
p = p>>1LL;
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string a,b;
ll m;
while(cin>>a>>b>>m)
{
if(a=="0" && b=="0" && m==0)
break;

ll base = 0;
for(int i=0; i<a.size(); i++)
{
int d = a[i]-'0';
base = ((base*10)+d)%m;
}

ll ans = 1;
for(int i=0; i<b.size(); i++)
{
int d = b[i]-'0';
ans = (bigmod(ans,10,m) * bigmod(base,d,m))%m;
}
cout << ans << endl;
}
return 0;
}

বুধবার, ৮ মে, ২০১৯

UPDATE(L,R,v)
You should add v to all Ai where L ≤ i ≤ R

QUERY(L,R,v)

You should output the frequency of the number v in the range from Lth to Rth index in the array.

INPUT:

OUTPUT:

Case 1:
1
0
2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define vin vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define pq priority_queue
#define all(x) x.begin(),x.end()
#define mod 1000000007
#define cone __builtin_popcount
#define conel __builtin_popcountll
typedef vector<vector<ll> > matrixl;
typedef vector<vector<int> > matrix;
#define N 100009
#define SN 2000
#define L (100000/SN)+2

int a[N],c[L][2*N],lz[L];

void upd(int l,int r,int v)
{
int lc = l/SN;
int rc = r/SN;
if(lc==rc)
{
for(int i=l;i<=r;i++)
{
//cout<<"T "<<i<<endl;
c[lc][a[i]]--;
a[i]+=v;
c[lc][a[i]]++;
}
return;
}
for(int i=l;i<(lc+1)*SN;i++)
{
c[lc][a[i]]--;
a[i]+=v;
c[lc][a[i]]++;
}
for(int i = lc+1;i<rc;i++) lz[i]+=v;
for(int i=rc*SN;i<=r;i++)
{
c[rc][a[i]]--;
a[i]+=v;
c[rc][a[i]]++;
}
}

int qry(int l,int r,int v)
{
int res = 0;
int lc = l/SN;
int rc = r/SN;
if(lc==rc)
{
for(int i=l;i<=r;i++) if(a[i]+lz[lc]==v) res++;
return res;
}
for(int i=l;i<(lc+1)*SN;i++)
{
if(a[i]+lz[lc]==v) res++;
}
for(int i=lc+1;i<rc;i++)
{
res+=c[i][v-lz[i]];
}
for(int i=rc*SN;i<=r;i++)
{
if(a[i]+lz[rc]==v) res++;
}
return res;
}

int main()
{
int n,q,t,tp,x,y,v,test = 0;
scanf("%d",&t);
while(t--)
{
printf("Case %d:\n",++test);
memset(c,0,sizeof(c));
memset(lz,0,sizeof(lz));
scanf("%d%d",&n,&q);
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
c[i/SN][a[i]]++;
}
while(q--)
{
scanf("%d%d%d%d",&tp,&x,&y,&v);
if(tp==1)
{
upd(x-1,y-1,v);
}
else
{
printf("%d\n",qry(x-1,y-1,v));
}
//for(int i=0;i<n;i++) cout<<a[i]<<" ";
//cout<<endl;
}
}
}

শুক্রবার, ৩ মে, ২০১৯

UVA 10099 - The Tourist Guide

#include <climits>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define MAXN 100
#define INF INT_MAX
#define NINF INT_MIN
int d[MAXN][MAXN]; // d[i][j] = distance from i node to j node
int floyd(int n)
{
for(int k=0; k<n; k++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
d[i][j]=max(d[i][j],min(d[i][k],d[k][j]));
}

return 0;
}
int main()
{
int n,e,i,j,u,v,w,cs=0; // n=number of nodes,e=number of edges
while(scanf("%d %d",&n,&e))
{
if(n==0&&e==0)
break;
for(i=0; i<n; i++) //node number begins from 0 to n-1
for(j=0; j<n; j++)
d[i][j]=NINF;
for(i=0; i<e; i++)
{
scanf("%d %d %d",&u,&v,&w);
u--;
v--;
d[u][v]=d[v][u]=w; //if graph is bidirectional
}
floyd(n);
scanf("%d %d %d",&u,&v,&w);
u--;
v--;
printf("Scenario #%d\n",++cs);
//cout<<d[0][6]<<endl;
int trip=ceil((float)w/(d[u][v]-1));
printf("Minimum Number of Trips = %d\n\n",trip);
}
return 0;
}

UVA 10078 - The Art Gallery

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
using namespace std;
bool isConvex(int n,int x[], int y[])
{
int pos=0,neg =0;
for(int i = 0; i < n; i++)
{
int prev = (i + n -1) % n, next = (i + 1) % n;
int pv = (x[next] - x[i]) * (y[prev] - y[i]) - (x[prev] - x[i])*(y[next] - y[i]);

if(pv > 0)
pos++;
else
{
if(pv < 0)
neg++;
}
}
return (pos == 0) || (neg == 0);
}

int main()
{
int N,a,b;
while(cin>>N)
{
if(N==0)
break;
int x[N], y[N];
for(int i = 0; i < N; i++)
{
cin>>a>>b;
x[i] = a;
y[i] = b;
}
if(isConvex(N,x,y))
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
return 0;
}

UVA 465 - Overflow

#include<stdio.h>
int main()
{
double a, b;
int INF = 2147483647;
char op, s[2000];
while(gets(s))
{
printf("%s\n", s);
sscanf(s, "%lf %c %lf", &a, &op, &b);
if(a > INF)
puts("first number too big");
if(b > INF)
puts("second number too big");
if(op == '+' && a+b > INF)
puts("result too big");
if(op == '*' && a*b > INF)
puts("result too big");
}
return 0;
}

UVA 10600 - ACM Contest and Blackout (First Minimum spanning tree AND Second Minimum spanning tree)

First Minimum spanning tree
Second Minimum spanning tree

2
5 8 ///5 holo node 8 holo edge
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

OUTPUT :110 121

9 14 ///9 holo node 14 holo edge
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10

Output 37 37

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define timesave ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
#define sz 103
#define inf 1<<29
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
struct edge
{
int f,t,c;
edge(int a,int b,int co)
{
f=a;
t=b;
c=co;
}
};

vector<edge>vec;
int n,e,ans2,edgetaken[sz],etl;
int comp(edge a,edge b)
{
return a.c<b.c;
}
int par[sz];
int set_find(int a)
{
if(a==par[a])
return a;
return(par[a]=set_find(par[a]));
}
void link(int x,int y)
{
if(x>y)
par[x]=y;
else par[y]=x;
}
int mst(void)
{
int i=0,j,x,y,sum=0,cnt=0;
etl=0;
sort(vec.begin(),vec.end(),comp);
for(i=0; i<e && cnt<n-1; i++)
{
x=set_find(vec[i].f);
y=set_find(vec[i].t);

if(x!=y)
{
link(x,y);
sum+=vec[i].c;
edgetaken[etl++]=i;
cnt++;
}
}
return sum;
}
void ini(void)
{
for(int i=1; i<=n; i++)
par[i]=i;
}

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

int t,i,j,f,c,tst,cs,cnt,ans1,an2,x,y,miin;
scanf("%d",&tst);
for(cs=1; cs<=tst; cs++)
{
scanf("%d %d",&n,&e);
ini();
vec.clear();
memset(edgetaken,0,sizeof edgetaken);
for(j=0; j<e; j++)
{
scanf("%d %d %d",&f,&t,&c);
vec.push_back(edge(f,t,c));
}

ans1=mst();

//2nd mst
miin= inf;
for(i=0; i<etl; i++)
{
ini();
cnt=0;
ans2=0;
for(j=0; j<e && cnt<n-1; j++)
{
// printf("i %d j %d\n",i,j);
if(edgetaken[i]!=j)
{
x=set_find(vec[j].f);
y=set_find(vec[j].t);
// printf("f %d t %d c %d\n",vec[j].f,vec[j].t,vec[j].c);
if(x!=y)
{
cnt++;
link(x,y);
ans2+=vec[j].c;
}
}
}
// printf("ans %d\n",ans2);
if(cnt==n-1 && miin>ans2)
miin=ans2;
}
printf("%d %d\n",ans1,miin);
}
return 0;
}

UVA 10036 - Divisibility

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define timesave ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
long n,k,arr[10000+5];
int dp[100+5][10000+5];
vector<long>v1;
vector<long>v2;
bool func(int sum, int position)
{
bool check=false;
sum=((sum%k)+k)%k;
if(position==n)
{
if(sum==0)
return true;
else
return false;
}
if(dp[sum][position]!=-1)
return dp[sum][position];
check=check | func(sum+arr[position],position+1);
check=check | func(sum-arr[position],position+1);
v1.push_back(sum);
v2.push_back(position);
return dp[sum][position]=check;
}
int main()
{
long tc,i;
cin>>tc;
memset(dp,-1,sizeof(dp));
while(tc--)
{
v1.clear();
v2.clear();
cin>>n>>k;
for(i=0; i<n; i++)
cin>>arr[i];
bool ans=func(arr[0],1);
if(ans)
cout<<"Divisible"<<endl;
else
cout<<"Not divisible"<<endl;
long l=v1.size();
for(i=0; i<l; i++)
dp[v1[i]][v2[i]]=-1;

}
return 0;
}

বুধবার, ১ মে, ২০১৯

UVA 10183 - How Many Fibs?

#include<bits/stdc++.h>
#define pi acos(-1.0)
#define E 2.71828182845904523536
using namespace std;

struct BI
{
char Digits[110];
int LastDigit;
};

void addBI(BI & a, BI & b, BI& c)
{
for (int i=0; i<110; i++) c.Digits[i] = 0;
int carry=0;
c.LastDigit = max(a.LastDigit, b.LastDigit);
for (int i=0; i<=c.LastDigit; i++) { c.Digits[i] = (a.Digits[i] + b.Digits[i] + carry)%10; carry = (a.Digits[i] + b.Digits[i] + carry)/10; } if (carry) c.Digits[++c.LastDigit] = carry; return; } int compBI(BI &a, BI&b) { if (a.LastDigit != b.LastDigit) return a.LastDigit > b.LastDigit;

for (int i=a.LastDigit; i >=0; i--) if (a.Digits[i] != b.Digits[i]) return a.Digits[i] > b.Digits[i];

return -1;
}
int howManyFibs(BI &small, BI &big)
{
BI *a,*b,*c;
a = new BI;
b = new BI;
c = new BI;

for (int i=0; i<110; i++) a->Digits[i] = b->Digits[i] = 0;
a->Digits[0] = 1; b->Digits[0] = 1;
a->LastDigit = 0; b->LastDigit = 0;

int nFibs=0;
bool reached=false;
while(1)
{

if(compBI(*b,small) && compBI(*b, big) < 1)nFibs++; else if (compBI(*b, big) == 1) break; addBI(*a,*b,*c); swap(b,c); swap(a,c); } return nFibs; } int main() { string a,b; BI large, small; while(1) { cin >> a >> b;

if (a == "0" && b == "0") return 0;
small.LastDigit = a.size() - 1;
for (int i=small.LastDigit, j=0; i>=0; i--, j++)small.Digits[i] = a[j] - '0';
large.LastDigit = b.size() - 1;
for (int i=large.LastDigit, j=0; i>=0; i--, j++)large.Digits[i] = b[j] - '0';
cout << howManyFibs(small,large) << endl;

}
return 0;
}