Selection Sort

সিলেকশন সর্ট-এ একটা (1 to n) লুপের মাধ্যমেই সর্ট কর যায় । এর জন্য, লুপের
1. প্রথম ধাপে, সবগুলা (1 to n) element এর ভেতর সবথেকে ছোট element-কে প্রথম element-এর সাথে interchange করতে হবে ।   [প্রথম element fixed]
2. দ্বিতীয় ধাপে, প্রথম element বাদে সবগুলা (2 to n) element এর ভেতর সবথেকে ছোট element-কে দ্বিতীয় element-এর সাথে interchange করতে হবে । [প্রথম দুইটা element fixed]
3. তৃতীয় ধাপে, প্রথম দুইটা element বাদে সবগুলা (3 to n) element এর ভেতর সবথেকে ছোট element-কে তৃতীয় element-এর সাথে interchange করতে হবে ।   [প্রথম তিনটা element fixed]
এভাবে (n-1)-তম element পর্যান্ত চলতে থাকবে । [n-তম element auto সর্টেড হয়ে যাবে]
এখন code দেখলে খুব সহজে বোঝা যাবে ……

Solution of UVa 10252-Common Permutation

See the problem 10252-Common Problem

1. #include<bits/stdc++.h>
2. using namespace std;
3. int main()
4. {
5.     string s, ss;
6.     int i, j, n, m;
7.     while(getline(cin, s)){
8.        getline(cin, ss);
9.        int ar[1000]={0}, arr[10000]={0};
10.         n=s.size();
11.         m=ss.size();
12.         for(i=0; i<n; i++) ar[(int)s[i]]++;
13.        for(i=0; i<m; i++) arr[i]=(int)ss[i];
14.        sort(arr, arr+m);
15.        for(i=0; i<m; i++){
16.            if(ar[arr[i]]){cout<<(char)arr[i]; ar[arr[i]]--;}
17.        }
18.        cout<<endl;
19.        s.clear(), ss.clear();
20.    }
21.    return 0;

Solution of UVA 11152 - Colourful Flowers

View the problem UVa-11152

#include<bits/stdc++.h>
#define pi acos(-1)
using namespace std;
int main()
{
    int a, b, c;
    while(scanf("%d%d%d", &a,&b,&c)!=EOF){
        double r, R, area_tri, area_cir, s, ans1, ans2, ans3;
        s=(a+b+c)/2.0;
        area_tri=sqrt(s*(s-a)*(s-b)*(s-c));
        R=(a*b*c)/(4*area_tri);
        area_cir=pi*R*R;
        ans1=area_cir-area_tri;
        r=area_tri/s;
        ans3=pi*r*r;
        ans2=area_tri-ans3;
        printf("%.4lf %.4lf %.4lf\n", ans1,ans2,ans3);
    }
    return 0;
}

Solution of LightOJ 1202 - Bishops

View the problem LightOJ 1202 - Bishops   #include<bits/stdc++.h> using namespace std; int main() { int n, i=1, a, b, c, d, x, y; scanf("%d", &n); while(n--){ scanf("%d%d%d%d", &a, &b, &c, &d); printf("Case %d: ", i++); x=abs(a-c); y=abs(b-d); if(x%2==y%2){ if(x==y) printf("1\n"); else printf("2\n"); } else printf("impossible\n"); } return 0; }

Solution of Uva 459 - Graph Connectivity

Solution of  UVa 459 - Graph Connectivity   #include<bits/stdc++.h> using namespace std; int p[100]; int prt(int z){ if(p[z]==z) return z; else return p[z]=prt(p[z]); } int main() { int i, t; scanf("%d\n", &t); while(t--){ int x, m[50]={0}, mx=0, y, n, z; string s, a; set<int>ss; scanf("\n"); getline(cin, a); n=(int)a[0]-64; for(i=1; i<=n; i++) p[i]=i; while(getline(cin, s)){ if(s.size()==0) break; else{ x=(int)s[0]-64; y=(int)s[1]-64; p[prt(y)]=prt(x); } } for(i=1; i<=n; i++) { p[i]=prt(i); ss.insert(p[i]); } cout<<ss.size()<<endl; if(t)cout<<endl; } return 0; }

Modular and Big Modular

মডুলার সম্পর্কে আমরা সবাই কম-বেশি জানি তবে মোটে না জানলেও সমস্যা নেই এটা খুব সহজ একটা বিষয় ।

modular

5%2=1

6%4=2

13%5=3

কিছু কি বোঝা যায় ? আসলে বিষয় হল, শেষ উদাহরণের জন্য বলি, 13 থেকে ছোট 5 এর সর্বচ্চ multiple হল 10 সুতরাং   13 mod 5 = (13-10) = 3. এখন তোমার (c/c++) compiler-এ 13%5 এবং -13%5 বের কর, দেখবে 3 এবং -3 উত্তর আসছে ।  প্রথম উত্তরটা ঠিক থাকলেও দ্বিতীয়টা ভুল, আসলে এখানে reminder বের করা হয়ছে ।

এখন দেখা যাক -13%5=? 

-13 এর থেকে ছোট 5 এর সর্বচ্চ multiple হল -15, সুতরাং -13%5 = (-13-(-15)) = -13+15 = 2 .

online judge এ মডুলো বের করার কোন সমস্যা সমাধানের সময় এই case টা মাথায় রাখা খুব জরুরী । তাহলে কিভাবে এই code টা করা যেতে পারে ? যে সংখ্যা দ্বারা mod করা হচ্ছে সেই সংখ্যার সাথে negative উত্তরটা যোগ করে দাও, হয়ে গেল ! না বুঝলে code টা দেখ, এটা negative, positive সব সংখ্যার জন্য ।

#include<bits/stdc++.h> using namespace std; int main() { long long m, n, r; while(cin>>m>>n){ r=m%n; if(r<0) r=r+n; cout<<r<<endl; } return 0; }

     100! %103=? এইটা পারবে ?

যদি 100! বের করে 103 দ্বারা মডুলো করতে চাও সেটা অসম্ভব । 100! এর কথা একটু চিন্তা করে দেখ ।

তবে আমরা জানি,       100!=(100*99*98*.......................3*2*1) 

দুইটা সুত্র দেখ 

                            1.  (a+b)%m = ((a%m)+(b%m))%m

                            2. (a*b)%m = ((a%m)*(b%m))%m

এখন দ্বিতীয় সুত্রটা ব্যবহার করে সমাধান করতে পারবে ।

আমাকে যদি বলে 12345678912345678912345678912 % 7 = ?

লক্ষ্য কর এখানে সংখ্যাটা 30 digit-এর । সাধারণত long long এ 19 digit পর্যান্ত নেয় unsigned long long নিলে সেখনে 20 digit পর্যান্ত calculate করবে । তাহলে কিভাবে 30-40 digit বা তার থেকে বেশি digit এর সংখ্যার মডুলো বের করতে পারি ?

 এখানে আমাদের string এর সাহায্য নিতে হবে কেননা string-এ 30-40 digit একটা মামুলি ব্যাপার। তবে এক্ষেত্রে দুইটা বিষয়ে ধারণা থাকতে হবে 

1.  321 = (((3*10)+2)*10)+1

            = ((30+2)*10)+1

            = (32*10)+1

            = 320+1

            =321

2. কোন digit এর character মান থেকে  integer মানে নিয়ে আসতে 48 বিয়োগ করতে হয় ।

এখন নিচের code-টা দেখ 

#include<bits/stdc++.h> using namespace std; int main() { int s=0, n, m, x, i; string a; cin>>a; cin>>m; n=a.size(); for(i=0; i<n; i++){ x=a[i]-48; s=(s*10+x)%m; } cout<<s<<endl; return 0; }

Modulo of Big Number

#include<bits/stdc++.h> using namespace std; int main() { int s=0, n, m, x, i; string a; cin>>a; cin>>m; n=a.size(); for(i=0; i<n; i++){ x=a[i]-48; s=(s*10+x)%m; } cout<<s<<endl; return 0; }