Subhashis_Mollick's Blog

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

শনিবার, ৩০ ডিসেম্বর, ২০১৭

All programming resource & link

শাফায়েত আশরাফ স্যারের ব্লগ + শান্ত স্যারের বই পড়ার পাশাপাশি https://github.com/me-shaon/bangla-programming-resources গিটহাবের এই রিপোতে চোখ রাখতে পারো। বাংলা ভাষার অনেক রিসোর্স এখানে আছে।

পাশাপাশি, আরো কিছু :
১। https://robiulawal.wordpress.com
২। https://imranshabijabi.wordpress.com
৩। http://hellohasan.com
৪। http://tushar-roy.blogspot.com
৫। http://www.howtocode.com.bd
৬। https://returnzerooo.wordpress.com
৭। http://www.acmsolver.org/bangla/index.html
৮। http://subeen.com
৯। http://programabad.com
১০। http://jotajotavm.com/bn/Java-Basics-01-Introduction-bn.html
১১। http://shuzasjava.blogspot.com
১২। http://shawonruet.blogspot.com
১৩। https://soaibscosmos.wordpress.com
১৪। http://binaryrongo.anindyaspaul.com
১৫। http://psshidhu.blogspot.com
১৬। http://www.progkriya.org
১৭। http://hukush-pakush.com
১৮।http://shudhuipython.blogspot.com/.../learn-python-in...
১৯। http://pythonbangla.blogspot.com
২০। http://juborajbanglablog.blogspot.com/2015/09/blog-post.html
২১। https://python.maateen.me
২২। https://bn.maateen.me
২৩। http://icchecode.com
২৪। http://jakir.me
২৫। http://shikkhok.com/
২৬। http://shoshikkha.com
২৭। http://tunerpage.com
২৮। http://www.ictshikkha.org/?page_id=479
২৯। https://programmingzone24.wordpress.com
৩০। http://www.projuktiteam.com
৩১। http://epathbd.com
৩২। http://tmlalgo.1free-host.com/
৩৩। http://www.engineer4free.com/
৩৪। http://zobayer.blogspot.com/
৩৫। https://tanvir002700.wordpress.com/
৩৬। https://albatrossmohoshi.blogspot.com/...
৩৭। http://www.iamrabiul.info/
৩৮। http://shawonruet.blogspot.com/
৩৯। https://soaibscosmos.wordpress.com35/...
৪০। http://shakilcompetitiveprogramming.blogspot.com/...
৪১। http://www.sanfoundry.com/
৪২। https://mathblag.wordpress.com/
৪৩। http://nstu-coding-planet.blogspot.com/...
৪৪। http://munirhasan.com
৪৫। http://rizoantoufiq.blogspot.com/
৪৬। https://sifatshishir.wordpress.com
৪৭। http://kirhobe.blogspot.com
৪৮। http://forthright48.blogspot.com
৪৯। http://smollick.blogspot.com
৫০। https://wordpresscom77092.wordpress.com

শুক্রবার, ২৪ নভেম্বর, ২০১৭

Minimum cost of a friend circle by using UNION FIND

এইটা Union Find টপিকস রিলেটেড

প্রবলেম লিঙ্কঃ http://codeforces.com/contest/893/problem/C

পুরো কোড সবার নিচে

দেখা যাবে দেওয়া থাকলো ৫ টা মান

ইনপুটঃ-

৫ ২ //৫ হল ৫ টা মান আর ২ হল ২ টা বন্ধুর লিস্ট

৮ ৫ ৩ ৪ ২ // এইগুলো হল পজিশন অনুযায়ী এদের ওয়েট যেমন ১ এর ৮,২ এর ৫ ,৩ এর ৩ ,৪ এর ৪ ,৫ এর ২

১ ৪ // ৪ ও ১ বন্ধু

৪ ৫ // ৪ ও ৫ বন্ধু

আউটপুটঃ-১০

এখন ১ ৪ ৫ একটা দল ,২ একটা দল,৩ একটা দল

এদের মধ্যে সব গুলো দলের মিনিমাম ওয়েট এর যোগফল কত?

উত্তর=১০

কারণ ১,৪,৫ এই দলের মিনিমাম ২+২ এর দলের ৫+৩ এর দলের ৩=১০

একটা কোড যদি করা থাকে সবার প্যারেন্ট কে এইবার মিনিমাম ওয়েট কিভাবে পাবো?

সেইটার কোডঃ

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

{

par[i]=Find(i);

st.insert(par[i]);

mn[par[i]]=min(mn[par[i]],ar[i]);

cout<<mn[par[i]]<<endl;

}

set<long long >::iterator it;

for(it=st.begin(); it!=st.end(); it++)

{

ans+=mn[*it];

}

cout<<ans<<endl;

পুরো কোডঃ-

#include <bits/stdc++.h>

using namespace std;

//long long vis[100010],ar[100010];

//vector<long long>vec[100010];

long long n,k;

long long par[100010],ar[100010],mn[100005];

long long Find(long long xx)

{

if(par[xx]==xx)

return xx;

return par[xx]=Find(par[xx]);

}

void make_union(long long x,long long y)

{

par[Find(y)]=Find(x);

}

set<long long>st;

main()

{

//long k;

cin>>n>>k;

{

long long i,u1,v1,ans=0;

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

{

cin>>ar[i];

mn[i]=ar[i];

par[i]=i;

}

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

{

cin>>u1>>v1;

make_union(u1,v1);

}

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

{

par[i]=Find(i);

st.insert(par[i]);

mn[par[i]]=min(mn[par[i]],ar[i]);

cout<<mn[par[i]]<<endl;

}

set<long long >::iterator it;

for(it=st.begin(); it!=st.end(); it++)

{

ans+=mn[*it];

}

cout<<ans<<endl;

}

মঙ্গলবার, ২১ নভেম্বর, ২০১৭

Print 1 to 100 without for loop

#include<bits/stdc++.h>
using namespace std;
int i=1;
class A
{
//int i=1;
public:
A()
{
printf("%d\n",i++);
}
};
//int A:: i=1;
main()
{
A obj[100];
}

শুক্রবার, ১৭ নভেম্বর, ২০১৭

UVA 443 - Humble Numbers

#include<bits/stdc++.h>
using namespace std;
vector<long long>vec;
void calc()
{
long i,i1,i2,i3;
for(i=0;i<31;i++)
{
for(i1=0;i1<20;i1++)
{
for(i2=0;i2<14;i2++)
{
for(i3=0;i3<12;i3++)
{
long long ans=pow(2,i)*pow(3,i1)*pow(5,i2)*pow(7,i3);
if(ans>0)
vec.push_back(ans);
}
}
}
}
sort(vec.begin(),vec.end());
}
main()
{
calc();
long n;
while(cin>>n)
{
if(n==0)
break;
printf("The %d", n);
if(n%10 == 1 && n%100 != 11)
printf("st");
else if(n%10 == 2 && n%100 != 12)
printf("nd");
else if(n%10 == 3 && n%100 != 13)
printf("rd");
else
printf("th");
printf(" humble number is %d.\n",vec[n-1]);
}
}

শনিবার, ৪ নভেম্বর, ২০১৭

UVA 12582 - Wedding of Sultan

#include<bits/stdc++.h>
using namespace std;
main()
{
long ts,cs=1;
cin>>ts;
while(ts--)
{
string s;
long i,x;
stack<char>st;
cin>>s;
st.push(s[0]);
st.push(s[1]);
long sz=s.size(),ar[100]={0};
printf("Case %ld\n",cs++);
for(i=2;i<sz-1;i++)
{
if(s[i]==st.top())
{
x=s[i]-'A';
ar[x]++;
st.pop();
x=st.top()-'A';
ar[x]++;
}
else
st.push(s[i]);
}
for(i=0;i<26;i++)
{
if(ar[i]!=0)
cout<<(char)(i+65)<<" = "<<ar[i]<<endl;
}
}
}

UVA 12583 - Memory Overflow

#include<bits/stdc++.h>
using namespace std;
main()
{
long ts,cs=1;
cin>>ts;
while(ts--)
{
long n,sz,i,cnt=0;
char ch;
string s;
map<char,long>mp;
queue<char>q;
cin>>n>>sz>>s;
for(i=0;i<sz;i++)
{
q.push(s[i]);
if(mp[s[i]]!=0)
cnt++;
mp[s[i]]++;
}
for(i=sz;i<n;i++)
{
ch=q.front();
if(mp[s[i]]!=0)
{
cnt++;
}
mp[ch]--;
mp[s[i]]++;
q.pop();
q.push(s[i]);
}
printf("Case %ld: %ld\n",cs++,cnt);
}
}

UVA 12898 - And Or

Explaintion:
Step 1: Count bit length of a and b
step 2: if lenb>lena then OR = 2^lenb - 1 and And = 0*/
step 3: find/count not change bits between a and b, from MSB to LSB
Or = b | R
And = b | ~R where R contain's 1 (total 1 = count)

Example:
[1]a = 7 b = 8

lena = 3 , Lenb = 4

so Or = 2^lenb - 1 = 16 - 1 = 15

And = 0

[2] Let a = 12 , b =15

lena = 4, len b = 4
a = 1100 , b = 1111

start j = 3 and break when j = 1

R = 1LL<<(j+1) - 1 = (11)2
unchanged first 2 bits
Or = b | R = (1111) = 15
And = b & ~R = (1100) = 12

Source Code:
#include<bits/stdc++.h>
using namespace std;
#define maxlen 61
typedef long long ll;
int main()
{
int n,c,i,lena,lenb,j;
int a1[maxlen],b1[maxlen];
ll Or,And,x,a,b,R;
const ll one = 1;
scanf("%d",&n);
for(i = 1; i <= n; i++)
{
scanf("%lld %lld",&a,&b);
/*Step 1: Count bit length of a and b*/
c = 0;
x = a;
while(x)
{
a1[c] = x&1;
x >>= 1;
c++;
}
lena = c;
c = 0;
x = b;
while(x)
{
b1[c] = x&1;
x >>= 1;
c++;
}
lenb = c;
/*step 2: if lenb>lena then OR = 2^lenb - 1 and And = 0*/
/*step 3: find/count not change bits between a and b, from LSB to MSB
Or = b | R and And = b | ~R where R contain's 1 (total 1 = count)
*/
if(lenb>lena)
{
Or =(one<<lenb)-1;
And = 0;
}
else
{
for( j = lenb-1; j >= 0; j--)
{
if(a1[j]!=b1[j]) break;
}
R = (one<<(j+1))-1;
Or = b|R;
And = b&~R;
}
printf("Case %d: %lld %lld\n",i,Or,And);
}
return 0;
}

শুক্রবার, ৩ নভেম্বর, ২০১৭

UVA 1726 - Automatic Cheater Detection

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
#define nl printf("\n")
#define case(a,b) printf("Case %lld: %lld\n",a,b)
#define P(a) printf("%lld\n",a)
#define SP(a) printf("%lld ",a)
#define G(a) scanf("%lld",&a)
#define GG(a,b) scanf("%lld %lld",&a,&b)
#define pb push_back
#define DB printf("I WAS HERE\n")
#define SPP(a,b) printf("%lld %lld\n",a,b)
#define LL long long
int main()
{
long long t;
G(t);
while(t--)
{
LL n;
G(n);
long long ar[12]={0},ar2[12]={0};
char r[10];
long long i,j,d,s,cnt=0;
for(i=1;i<=n;i++)
{
scanf("%lld %lld %s",&d,&s,r);
if(s==0 && r[0]=='i')
{
ar[d]++;
}
else if(s==1 && r[0]=='c')
{
ar2[d]++;
}
}
cnt=0;
for(i=1;i<=9;i++)
{
for(j=i+1;j<=10;j++)
{
LL x=ar[i]*ar2[j];
cnt+=x;
}
}
P(cnt);
}

return 0;
}

UVA 1729 - Owllen

#include<bits/stdc++.h>
using namespace std;
int main()
{
long ts,cs=1;
cin>>ts;
while(ts--)
{
string s;
cin>>s;
long mp[100]={0},i,mn=100000000;
for(i=0;i<s.size();i++)
{
mp[s[i]-97]++;
}
for(i=0;i<26;i++)
{
mn=min(mp[i],mn);
}
printf("Case %ld: ",cs++);
cout<<mn<<endl;
}
}

UVA 1727 - Counting Weekend Days

#include<bits/stdc++.h>
using namespace std;
int main()
{
long ts;
cin>>ts;
while(ts--)
{
string s,s1;
cin>>s>>s1;
map<string,long>mp;
mp["SUN"]=1;
mp["MON"]=2;
mp["TUE"]=3;
mp["WED"]=4;
mp["THU"]=5;
mp["FRI"]=6;
mp["SAT"]=0;
int i,tot;
if(s=="JAN"||s=="MAR"||s=="MAY"||s=="JUL"||s=="AUG"||s=="OCT"||s=="DEC")
{
tot=31;
}
else if(s=="FEB")
tot=28;
else tot=30;
int x=mp[s1],x1,ans=0;
x1=x;
for(i=1;i<=tot;i++)
{
if(x%7==0||x%7==6)
ans++;
x++;
}
cout<<ans<<endl;
}
}

UVA 1180 - Perfect Numbers

#include<bits/stdc++.h>
using namespace std;
int main()
{
long n;
while(cin>>n)
{
string s;
cin>>s;
s+=',';
long i,p=0;
for(i=0; i<s.size(); i++)
{
if(s[i]==',')
{
if( p == 2 || p == 3 || p == 5 || p == 7 || p == 13 || p == 17 || p == 19 )
printf("Yes\n") ;
else printf("No\n");
p=0;
}
else
{
p=p*10+s[i]-48;
}
}
}
}

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

UVA 10140 - Prime Distance

#include <bits/stdc++.h>
using namespace std;
#define mx 48000
long long vis[48000]= {0},ar[48000]= {0},i,j,k=0;
vector<long long >vec;
void sieve()
{
for(i=4; i<=mx; i+=2)
vis[i]=1;
for(i=3; i<=sqrt(mx); i+=2)
{
if(vis[i]==0)
{
for(j=2*i; j<=mx; j+=i)
{
vis[j]=1;
}
}
}
vis[1]=1,vis[0]=1;
for(i=1; i<=mx; i++)
{
if(vis[i]==0)
{
ar[k++]=i;
}
}
}
bool chk(long long nm)
{
if(nm>=k)
{
for(long long i1=0; i1<k&&ar[i1]<=sqrt(nm); i1++)
{
if(nm%ar[i1]==0)
{
return 0;
}
}
return 1;
}
else
{
if(vis[i]==0)
return 1;
else
return 0;
}
}
main()
{
sieve();
long long l,u;
while(cin>>l>>u)
{
for(i=l; i<=u; i++)
{
if(chk(i))
{
vec.push_back(i);
}
}
long long ll=vec.size(),dif=0,dif2,dif1,f=0,f1=0;
if(ll<2)
printf("There are no adjacent primes.\n");
else
{
for(i=1; i<ll; i++)
{
if(i==1)
{
dif=vec[i]-vec[i-1];
dif1=vec[i]-vec[i-1];
f=f1=i;
}
else
{
dif2=vec[i]-vec[i-1];
if(dif2<dif)
{
f=i;
dif=dif2;
}
if(dif2>dif1)
{
dif1=dif2;
f1=i;
}
}
}
printf("%lld,%lld are closest, %lld,%lld are most distant.\n",vec[f-1],vec[f],vec[f1-1],vec[f1]);
}
vec.clear();
}
}

UVA 10751 - Chessboard

#include <cstdio>

#include <cmath>

using namespace std;

int main()

{

int tc, n;

scanf("%d", &tc);

while (tc--)

{

scanf("%d", &n);

if (n > 1)

printf("%.3lf\n", (4 * n - 4) + sqrt(2) * (n - 2) * (n - 2));

else

printf("0.000\n");

}

return 0;

}

UVA 10137 - The Trip

#include<bits/stdc++.h>
using namespace std;
main()
{
long n;
while(cin>>n)
{
if(n==0)
break;
long i;
double ar[10010]= {0.0},sum=0.0,avg=0;
for(i=0; i<n; i++)
{
cin>>ar[i];
sum+=ar[i];
}
avg=sum/n;
sum=0.0;
double sum1=0.0,baki;
long ans=0;
for(i=0; i<n; i++)
{
baki=avg-ar[i];
if(baki>0)
{
ans=(baki*100);
sum=sum+ans;
}
else
{
baki=baki*-1;
ans=(baki*100);
sum1=sum1+ans;
}
}
if(sum>sum1)
printf("$%.2lf\n",sum/100.0);
else
printf("$%.2lf\n",sum1/100.0);
}
}

UVA 12160 - Unlock the Lock

#include<bits/stdc++.h>
using namespace std;
long vis[10005],dist[10005],i,l,u,r,ar[15];
void bfs(long src)
{
queue<long>q;
q.push(src);
vis[src]=0;
dist[src]=0;
while(!q.empty())
{
long u1=q.front();
q.pop();
for(i=0;i<r;i++)
{
long v=(u1+ar[i])%10000;
if(vis[v]==0)
{
vis[v]=1;
dist[v]=dist[u1]+1;
q.push(v);
}
}
}
}
main()
{
long cs=1;
while(cin>>l>>u>>r)
{
if(l==0&&u==0&&r==0)
break;
for(i=0;i<r;i++)
{
cin>>ar[i];
}
bfs(l);
printf("Case %ld: ",cs++);
if(dist[u]==0)
printf("Permanently Locked\n");
else
cout<<dist[u]<<endl;
for(i=0;i<10005;i++)
{
vis[i]=0;
dist[i]=0;
}
}
}

UVA 12917 - Prop hunt!

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

int main()
{
int a,b,c;
while(cin>>a>>b>>c)
{
if((a+b)>c)
cout<<"Hunters win!"<<endl;
else
cout<<"Props win!"<<endl;
}
}

বুধবার, ১ নভেম্বর, ২০১৭

UVA 1112 - Mice and Maze

#include<bits/stdc++.h>
using namespace std;
vector<long>vec[105],cost[105];
long sorc,desti;
long dist[105];
struct node
{
long u,w;
node(long a,long b)
{
u=a;
w=b;
}
bool operator < ( const node& p ) const
{
return w > p.w;
}
};
void dijkstra(long s)
{

priority_queue<node>pq;
dist[s]=0;
pq.push(node(s,0));
while(!pq.empty())
{
node top=pq.top();
pq.pop();
long u=top.u;
for(long i=0;i<(long)vec[u].size();i++)
{
long v=vec[u][i];
if(dist[u]+cost[u][i]<dist[v])
{
dist[v]=dist[u]+cost[u][i];
pq.push(node(v,dist[v]));
}
}
}
}
main()
{
long ts,cs=1;
cin>>ts;
while(ts--)
{
if(cs>1)
cout<<endl;
long i,n,e;
cin>>n>>desti>>sorc>>e;
for(long i=1; i<=n; i++)
dist[i]=100000000;
for(i=0;i<e;i++)
{
long u,v,w;
cin>>u>>v>>w;
vec[u].push_back(v);
vec[v].push_back(u);
cost[u].push_back(w);
cost[v].push_back(w);
}
long cnt=0;
dijkstra(desti);
for(i=1;i<=n;i++)
{
if(dist[i]<=sorc)
cnt++;
}
cs++;
cout<<cnt<<endl;
for(i=1;i<=n;i++)
{
cost[i].clear();
vec[i].clear();
}
}
}

UVA 10986 - Sending email

#include<bits/stdc++.h>
using namespace std;
vector<long>vec[200002],cost[200002];
long sorc,desti;
long dist[200002];
struct node
{
long u,w;
node(long a,long b)
{
u=a;
w=b;
}
bool operator < ( const node& p ) const
{
return w > p.w;
}
};
long dijkstra(long n)
{
for(long i=0; i<=n; i++)
dist[i]=10000000;
priority_queue<node>pq;
dist[sorc]=0;
pq.push(node(sorc,0));
while(!pq.empty())
{
node top=pq.top();
pq.pop();
long u=top.u;
if(u==desti)
{
return dist[desti];
}
for(long i=0;i<(long)vec[u].size();i++)
{
long v=vec[u][i];
if(dist[u]+cost[u][i]<dist[v])
{
dist[v]=dist[u]+cost[u][i];
pq.push(node(v,dist[v]));
}
}
}
return -1;
}
main()
{
long ts,cs=1;
cin>>ts;
while(ts--)
{
long i,n,e;
cin>>n>>e>>sorc>>desti;
for(i=0;i<e;i++)
{
long u,v,w;
cin>>u>>v>>w;
vec[u].push_back(v);
vec[v].push_back(u);
cost[u].push_back(w);
cost[v].push_back(w);
}
long ans=dijkstra(n);
if(ans==-1)
printf("Case #%ld: unreachable\n",cs++);
else
printf("Case #%ld: %ld\n",cs++,ans);
for(i=0;i<n;i++)
{
cost[i].clear();
vec[i].clear();
}
}
}

UVA 429 - Word Transformation

#include<bits/stdc++.h>
#define fr(i1,m) for(int i1=0;i1<m;i1++)
using namespace std;
vector<int>vc[10000];
int bfs(int n,int m)
{
queue<int>q;
q.push(n);
int t[100000]= {0},d[100000]= {0};
t[n]=1;
d[n]=0;
while(!q.empty())
{
int u=q.front();
if(u==m)
return d[u];
for(int i=0; i<vc[u].size(); i++)
{
int v=vc[u][i];
if(!t[v])
{
d[v]=d[u]+1;
t[v]=1;
q.push(v);
}
}
q.pop();
}
}

int main()
{
long n;
scanf("%ld",&n);
fr(ii,n)
{
if(ii>0)
cout<<"\n";
long p=0,l=1,hh,j,c;
char ch[100000];
string s[10000],s1,ff,f,kk,rr;
map<string,int>mp;
while(cin>>s1)
{
if(s1=="*")
break;
s[p]=s1;
mp[s1]=l++;
p++;

}
fr(i,p)
{
for(j=i+1; j<p; j++)
{
if(s[i].size()==s[j].size())
{
hh=0;
kk=s[j];
rr=s[i];

fr(k,s[i].size())
{
if(rr[k]!=kk[k])
{
hh++;
if(hh>1)
break;
}
if(hh>1)
break;
}
if(hh==1)
{
vc[mp[rr]].push_back(mp[kk]);
vc[mp[kk]].push_back(mp[rr]);
}
}
}
}
getchar();
// scanf("\n");
while(gets(ch))
{
if(ch[0]=='\0')
break;
f="";
ff="";
c=0;
fr(i,strlen(ch))
{
if(ch[i]==' ')
c=1;
else if(c==0)
f+=ch[i];
else
ff+=ch[i];

}
cout<<f<<" "<<ff<<" "<<bfs(mp[f],mp[ff])<<"\n";
}
fr(i,l+4)
vc[i].clear();

}
return 0;
}

সোমবার, ৩০ অক্টোবর, ২০১৭

UVA 558 - Wormholes

#include"bits/stdc++.h"
using namespace std;
long i,flag;
#define inf (1<<29)
long dis[1005];
struct node
{
long u,v;
long w;
};
vector<node>vec;
void bellman_ford(long n,long m)
{
for(i=0;i<n;i++)
dis[i]=inf;
dis[0]=0;//source a 0 rakhlam
long j;
for(i=0;i<n-1;i++)
{
for(j=0;j<m;j++)
{
if((dis[vec[j].u]+vec[j].w<dis[vec[j].v])&&(dis[vec[j].u]!=inf))
{
dis[vec[j].v]=dis[vec[j].u]+vec[j].w;
}
}
}
for(j=0;j<m;j++)
{
if(dis[vec[j].u]+vec[j].w<dis[vec[j].v])
{
flag=1;
}
}
}
int main()
{
//cout<<inf<<endl;
long ts;
cin>>ts;
while(ts--)
{
long n,m,a,b,c;
cin>>n>>m;
node edge;
for(i=0;i<m;i++)
{
cin>>a>>b>>c;
edge.u=a;
edge.v=b;
edge.w=c;
vec.push_back(edge);
}
flag=0;
bellman_ford(n,m);
if(flag==0)
{
printf("not possible\n");
}
else
printf("possible\n");
for(i=0;i<n+2;i++)
{
dis[i]=0;
}
vec.clear();
}
return 0;
}

শনিবার, ২৮ অক্টোবর, ২০১৭

UVA 924 Spreading the News

#include<bits/stdc++.h>
using namespace std;
vector<long>vec[2505];
long dist[2505];
long bfs(long s)
{
memset(dist,-1,sizeof(dist));
queue<long>q;
q.push(s);
dist[s]=0;
long u,v,i1;
while(!q.empty())
{
u=q.front();
q.pop();
for(i1=0;i1<vec[u].size();i1++)
{
v=vec[u][i1];
if(dist[v]==-1)
{
dist[v]=dist[u]+1;
q.push(v);
}
}
}
}
main()
{
long n;
while(cin>>n)
{
long i,a,j,b;
for(i=0;i<n;i++)
{
cin>>a;
for(j=1;j<=a;j++)
{
cin>>b;
vec[i].push_back(b);
}
}
long ts,x;
cin>>ts;
while(ts--)
{
cin>>x;
bfs(x);
sort(dist,dist+n);
long day,mx,cs;
day=mx=i=0;
for(i=0; i<n; i++)
{
j=i;
cs=0;
while(dist[i]==dist[j])
{
if(dist[j]>0)
cs++;
j++;
}
if(cs>mx)
{
mx=cs;
day=dist[i];
}
i=j-1;
}
if(dist[n-1]==0)
cout<<0<<endl;
else
cout<<mx<<" "<<day<<endl;
}
for(i=0;i<n;i++)
vec[i].clear();
}
}

শুক্রবার, ২৭ অক্টোবর, ২০১৭

UVA 10653 - Bombs! NO they are Mines!!

#include<bits/stdc++.h>
using namespace std;
long dx[]={1,0,-1,0};
long dy[]={0,1,0,-1};
long row,col;
char s[1010][1010];
long dis[1010][1010]={0},vis[1010][1010]={0};
long bfs(long x,long y)
{
queue< pair<long,long> >q;
pair<long,long>pr;
long x1,y1,i1;
dis[x][y]=0;
vis[x][y]=1;
q.push(make_pair(x,y));
while(!q.empty())
{
pr=q.front();
x1=pr.first;
y1=pr.second;
for(i1=0;i1<4;i1++)
{
x1=pr.first+dx[i1];
y1=pr.second+dy[i1];
if((x1>=0&&x1<row)&&(y1>=0&&y1<col)&&(vis[x1][y1]==0)&&(s[x1][y1]!='#'))
{
dis[x1][y1]=dis[pr.first][pr.second]+1;
q.push(make_pair(x1,y1));
vis[x1][y1]=1;
if(s[x1][y1]=='h')
{
return dis[x1][y1];
}
}
}
q.pop();
}
}
int main()
{
while(cin>>row>>col)
{
if(row==0&&col==0)
break;
long n,i,j,rnumbr,pos,a;
cin>>n;
for(i=0;i<row;i++)
{
for(j=0;j<col;j++)
{
s[i][j]='*';
dis[i][j]=0;
vis[i][j]=0;
}
}
for(i=1;i<=n;i++)
{
cin>>rnumbr;
cin>>a;
for(j=1;j<=a;j++)
{
cin>>pos;
s[rnumbr][pos]='#';
}
}
long sx,sy,ddx,ddy;
cin>>sx>>sy>>ddx>>ddy;
s[ddx][ddy]='h';
cout<<bfs(sx,sy)<<endl;
}
return 0;
}

বুধবার, ২৫ অক্টোবর, ২০১৭

UVA 562 - Dividing coins

#include <bits/stdc++.h>
using namespace std;
long n,dp[110][110*500];
long coin[110],x;
long call(long i1,long wt)
{
if(i1==n)
return 0;
if(dp[i1][wt]!=-1)
return dp[i1][wt];
long prof1=0,prof2=0;
if((wt+coin[i1])<=x)
{
prof1=coin[i1]+call(i1+1,wt+coin[i1]);
}
else
prof1=0;
prof2=call(i1+1,wt);
dp[i1][wt]=max(prof1,prof2);
return dp[i1][wt];
}
main()
{
long ts;
cin>>ts;
while(ts--)
{
long m,i,sum=0;
cin>>n;
for(i=0;i<n;i++)
{
cin>>coin[i];
sum+=coin[i];
}
x=sum/2;
memset(dp,-1,sizeof(dp));
long ans=call(0,0);
ans=sum-(ans*2);
printf("%ld\n",ans);
}
}

বুধবার, ১৮ অক্টোবর, ২০১৭

UVA 10912 - Simple Minded Hashing

#include<bits/stdc++.h>
#define sf2(a,b) scanf("%lld%lld",&a,&b)
using namespace std;
bool vis[28][28][355];
long long dp[28][28][355];
long long l,s;
long long callkorlam(long long pos,long long len,long long tot)
{
if(l==len)
{
if(tot==0)
return 1;
else
return 0;
}
if(tot==0)
{
if(l==len)
return 1;
else
return 0;
}
if(pos>26)
{
if(len==l&&tot==0)
{
return 1;
}
else
return 0;
}
long long fst=0,scnd=0;
if(vis[pos][len][tot]!=false)
{
return dp[pos][len][tot];
}
if(tot-pos>=0)
{
fst=callkorlam(pos+1,len+1,tot-pos);
}
scnd=callkorlam(pos+1,len,tot);
vis[pos][len][tot]=true;
return dp[pos][len][tot]=fst+scnd;
}
main()
{
long long cs=1;
while(cin>>l>>s)
{
long long rs=0;
if(l==0&&s==0)
break;
memset(vis,false,sizeof(vis));
if(l>26 || s>351)
{
rs=0;
}
else
{
rs=callkorlam(1,0,s);
}
printf("Case %lld: %lld\n",cs++,rs);
}
}

UVA 10006 - Carmichael Numbers

#include<bits/stdc++.h>
#define sz 65100
using namespace std;
long status[65100];
void sieve()
{
long long i,j;
status[1]=1,status[0]=1;
for(i=3;i<=sz;i++)
{
if(status[i]==0)
{
for(j=i*i;j<=sz;j+=i)
{
status[j]=1;
}
}
}
}
long long bigmod(long long base,long long power,long long mod)
{
long long ret=1;
while(power)
{
if(power & 1)
ret=(ret*base)%mod;
base = (base*base)%mod;
power=power>>1;
}
return ret;
}
main()
{
sieve();
long long n;
while(cin>>n)
{
long long i1,xx,f=0;
if(n==0)
break;
else
{
if(status[n]==0)
{
printf("%lld is normal.\n",n);
}
else
{
for(i1=2;i1<n;i1++)
{
xx=bigmod(i1,n,n);
if(xx!=i1)
{
f=1;
break;
}
}
// cout<<f<<endl;
if(f==0)
{
printf("The number %lld is a Carmichael number.\n",n);
}
else
{
printf("%lld is normal.\n",n);
}
}
}
}
}

UVA