uva 10405-Longest common subsequence-solution hints

https://uva.onlinejudge.org/external/104/10405.pdf


Nothing to say about this programme .

Just learn the LCS(longest common subsequence) algorithm and follow the steps it will be solved .

for more information about LCS just visit the site given below :

http://www.thecrazyprogrammer.com/2015/05/c-program-for-longest-common-subsequence-problem.html

An accepted code is given below for better understand :

#include<iostream>
#include<string>
#include<stdio.h>
#define s 1002
using namespace std;

long long int c[s][s];

int maxi(int x , int y)
{
    if(x>=y)
    {
        return x;
    }
    else
    {
        return y;
    }
}

void lcs(string a , string b)
{
    int m,n;

    m=a.length();
    n=b.length();

    for(int i=0;i<=m;i++)
    {
        c[i][0]=0;
    }

    for(int i=0;i<=n;i++)
    {
        c[0][i]=0;
    }

    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i-1]==b[j-1])
            {
                c[i][j]=c[i-1][j-1]+1;
            }
            else if(a[i-1]!=b[j-1])
            {
                c[i][j]=maxi(c[i-1][j],c[i][j-1]);
            }
        }
    }

    printf("%d\n",c[m][n]);
}

int main()
{
    string a,b;

    while(getline(cin,a))
    {
        getline(cin,b);

        lcs(a,b);
    }

    return 0;
}

End-Of-File online judge (EOF)

যারা একেবারে নতুন অনলাইন জাজ এ প্রবলেম সল্ভ করছেন তাদের এই এন্ড অফ ফাইল জিনিসটা নিয়ে বড় আপত্তি । সবার প্রথম অনুভুতি থাকে এই চিজটা আবার কি করে খাই না পরে । আমিও যখন প্রথম swapnil ভাই এর কাছে এই শব্দটা প্রথম শুনেছিলাম বড়ই আজব লেগেছিল ।

আসলে বিষয়টা তেমন কিছুই না । যাদের হোয়াইল লুপ সম্পরকে ভাল ধারনা আছে তাদের জন্য এইটা হল পানি না পানি বললে ভুল হবে পানির চাইতেও সহজ হা কেরোসিন বলা যাইতে পারে ।

আচ্ছা মেইন বিষয়ে আশি । আমরা যেসব অনলাইনে প্রবলেম সল্ভ করি সেগুলা আসলে আপনার জন্য ইনপুট নিয়ে বশে থাকেনা । তারা একটা ইনপুট ফাইল আর আরেকটা আউটপুট ফাইল তৈরি করে রাখছে আর কি যে একটা সিস্টেম বানাই রাখছে আপনি আপনার প্রোগ্রাম সাবমিট করার সাথে সাথেই ওই বানিয়ে রাখা ফাইল থেকে ইনপুট এসে আপনার প্রোগ্রাম এর আউটপুট নিয়ে উনাদের সঠিক আউটপুট এর সাথে মিলাবেন । যদি মিলে তবে আপনি পাবেন Accepted মার্কা নয়ত পাবেন বিশ্ব বিখ্যাত wrong answer ট্যাগ ।

আচ্ছা তাহলে তো বুঝতেই পারছেন আপনার জন্য অনেক বড় একটা ইনপুট ফাইল অপেক্ষা করছে সেটা যে কত বড় কেউ জানেনা । তাই আপনাকে এমনভাবে ইনপুট নেয়ার সিস্টেম করতে হবে আপনার প্রোগ্রাম এ যাতে উনাদের ইনপুট ফাইল্টা শেষ না হওয়া পর্যন্ত আপনার প্রোগ্রাম ইনপুট নিতে থাকে এবং সে অনুযায়ি আউটপুট ওঁ দিতে থাকে এবং ফাইল শেষ হয়ে গেলে আপনার ইনপুট নেয়া ওঁ শেষ হয়ে যাই ।

আচ্ছা যেটা বলছিলাম আপনি কি আমার লেখাগুলা পরে কোন হিন্ট পাইছেন ? না পাইলেও প্রবলেম নাই আমি হিন্ট বলে দিচ্ছি । আমি বলেছি "ফাইল শেষ না হওয়া পর্যন্ত ইনপুট নিবে" । while loop এর গন্ধ কি পাচ্ছেন ? "শেষ না হওয়া পর্যন্ত" ।

মেইন বিষয়টা হইল যে প্রবলেম এ বলবে  EOF(End Of File) পর্যন্ত ইনপুট নিতে আপনি চোখ বন্ধ করে  while loop এর মদ্ধে আপনাকে যে ইনপুট নিতে বলা হইসে নিয়ে নিবেন ।

যেমন ,


১ । মনে করেন প্রবলেম নাম্বার ১০০৫৫ এর কথাই বলি আই মিন হাশ্মত আর তার সেনাবাহিনীর কথা । ওইখানে আপনাকে বলেছে প্রতিবার এ দুইটা করে ইনপুট নিতে হবে এবং অবশ্যই  এন্ড অফ ফাইল পর্যন্ত । মনে করেন এইটা অনলাইন জাজ এর  একটা ইনপূট ফাইল ।


                                         | 10  12    |
                                         | 10  100  |
                                         | 100 200 |
                                         |200 400  |
                                         | 300 500 |



তো আপনি যদি C++ ইউজ করেন তাইলে লিখবেন ,

                                                               while (cin>>a>>b)
                                                                    {
                                                                       
                                                          ............. Your programme...........

                                                                           }

এইটার মানে হচ্ছে আপনার প্রোগ্রাম প্রতিবারে a আর b এর দুইটা করে মান ইনপুট নিবে আর ফাইল শেষ হয়ে গেলে আপনার প্রোগ্রাম ওঁ শেষ । শেষ বলতে আপনার প্রোগ্রাম মারা যাবেনা ভয় পাইয়েন না । আপনার প্রোগ্রাম ইনপুট নেয়া বন্ধ করে দিবে ।


আর আপনি যদি সি তে প্রোগ্রাম লিখেন তাইলে আপনাকে লিখতে হবে ,

                                                   while(scanf(%d%d,&a,&b)==2)
                                                                   {

                                                                   ............. Your programme...........

                                                                     }


নিশ্চয় ভয় পাইছেন এখানে  (==২) কেন দিছি । সি তে লিখলে এইটা দিতে হবে এইটা বুঝাবে আপনার প্রোগ্রাম যতক্ষণ ২ তা করে ইনপুট পাবে ততক্ষণ ইনপুট নিবে বা চলবে নইতো ইনপুট নেয়া বন্ধ করে দিবে ।

আচ্ছা এতক্ষন বললাম ইনপুট ফাইল থেকে ইনপুট নেয়ার কথা কিন্তু আপনার কনসোল তো আর ইনপুট ফাইল না সো এইখানে আপনাকে নিজে ইনপুট দিতে হবে এবং ইনপুট প্রোগ্রাম টারমিনেট করতে চাইলে Ctrl+Z বাটন চেপে ইন্টার মারুন টারমিনেট হয়ে যাবে ।

আপনাকে ধন্যবাদ এতক্ষন আমাকে বরদাস্ত করার জন্য ।

uva 575 - Skew Binary - Solution hints

https://uva.onlinejudge.org/external/5/575.pdf

This problem is really confusing  . But it's easy just find the pattern . Here's you have been asked to find the decimal equivalent of a skew binary system . Follow the following steps :

1 . 1st of all you have to gain knowledge about skew binary system it' s like binary system but a little bit change is needed .

2 . We know that in binary to decimal conversion the i-th positioned number is multiplied by 2^i then one by one summing all the i-th positioned digit by multiplying 2^i we get the desired decimal system but for skew binary it's different . You have to find i-th position number by modding the whole number by 10 then you need to multiply the i-th positioned number by (2^i+1-1)  . that's the difference .

3 . After multiplying all the i-th positioned number by  (2^i+1-1) just add all the result together .

4 . The process mentioned above is for only short integers but here the input maybe bigger than 10^18 so you have to take input as string and implement your code according to that .

for more information about Skew binary system have a look to :

Skew Binary system-Wikipedia

An accepted code is given below for better understand .

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

int main()
{
    long long int i,r,sum,l,n;
    string num;

    while(cin>>num && num!="0")
    {
        sum=0;
        i=0;
        l=num.length();

        while(num[i])
        {
            n=num[i]-48;
            sum+=n*(pow(2,(l-i))-1);
            i++;

        }

        printf("%lld\n",sum);

    }

    return 0;
}

Increment-Decreament

Collected from Mujtaba Asif's Facebook wall . Carry on bro . Best of luck .

https://www.facebook.com/mjtbasif?fref=ts

x এর মান 0 ধরলে,

x++ এর ক্ষেত্রে প্রথমে x=0 নিয়ে কাজ করবে এবং তারপর x=0+1=1 এবং

তারপর x=1+1=2 হবে এভাবেই এক করে মান বাড়তে থাকবে।

x-- এর ক্ষেত্রে প্রথমে x=0 নিয়ে কাজ করবে এবং তারপর x=0-1=-1 এবং

তারপর x=-1-1=-2 নিয়ে কাজ করবে। এভাবেই এক করে মান কমতে থাকবে।

আবার, ++x এর অর্থ হল, প্রথমে x=1+0=1 নিয়ে কাজ করবে।

তারপর x=1+1=2 নিয়ে কাজ করবে। এভাবেই এক করে বাড়বে।

--x এর অর্থ হল প্রথমেই x=-1+0=-1 নিয়ে কাজ করবে। তারপর

x=-1-1=-2 নিয়ে কাজ করবে। এভাবেই এক করে কমতে থাকবে।

কিন্তু কাজ করার বেলায় যদি এমন হয় যে, x++ ও আছে আবার

x-- ও আছে তখন আগে x++ এর কাজ হবে এবং তারপর x--।

যদি এখানে x++, x-- এবং x থাকে তাহলেও আগে x++ তারপর x-- এবং

তারপর x এর কাজ হবে। ++x, --x এর বেলায়ও একই রকম। আগে

++x এবং তারপর --x এর কাজ হবে।

কিন্তু যখন ++x এবং x++ অথবা, --x এবং x-- অথবা --x এবং x++ থাকে

তখন যেটা ডান দিকে থাকে সেটা আগে কাজ করে।

উদাহরন স্বরূপ, printf("%d %d",x++,++x); এর আউটপুট হবে, 1 2।

কারন প্রথমে ডান দিকে আছে ++x অর্থাৎ, x=0+1=1।

x এর মান 1 নিয়ে যাবে এখন x++ এর কাছে। যার ফলে x=1 প্রিন্ট হবে।

এখন x=1+1=2 মান নিয়ে ++x এ যাবে ফলে 2 প্রিন্ট হবে।

এবং printf("%d %d",++x,x++); এর আউটপুট হবে, 2 0 ।

এখানে ডান দিকে আছে x++। ফলে x=0 প্রিন্ট করে, x=0+1=1

নিয়ে ++x এর কাছে যাবে। ফলে ++x এর মান হবে x=1+1=2।

কিন্তু এবার আর x++ এর কাছে ফিরে যাবে না। ফলে x++ এর মান 0-ই থাকবে।

একই ভাবে, printf("%d %d",x--,--x); এর আউটপুট হবে, -1 -2

printf("%d %d",--x,x--); এর আউটপুট হবে -2 0

printf("%d %d",x++,--x); এর আউটপুট হবে -1 0

printf("%d %d",--x,x++); এর আউটপুট হবে 0 0

বিঃদ্রঃ বিভ্রান্তিমুলক তথ্য উপস্থাপন করে থাকলে সঠিক তথ্য দিয়ে সাহায্য করুন। :)

UVA Most Easy Problems

Here i have mentioned some most easy problems for the most beginners . A list is given below . Just click on the name to go to the problem :

1 . 10055 - Hashmat the Brave Warrior

2 . 10079 - Pizza Cutting

3 . 10783 - Odd Sum

4 . 11172 - Relational Operator

5 . 10071 - Back to High School Physics

6 . 11727 - Cost Cutting

7 . 11805 - Bafana Bafana

8 . 12577 - Hajj-e-Akbar

9 . 382 - Perfection

10 . 12578 - 10:6:2

11 . 10945 - Mother bear

12 . 10696 - f91

13 . 10931 - Parity

14 . 12626 I Love Pizza

16 . 11854 - Egypt

17 . 11417-GCD

18 . 11461-Square Numbers

19 . 579-Clock Hands

20 . 573-The Snail

21 . 272 - TEX Quotes

22 . 12502-Three Families

23 . 13026 - Search the Khoj

24 . 10041 - Vito's Family

25 . 458 - The Decoder

26 . 10432 - Polygon Inside A Circle

27 . 11936 - The Lazy Lumberjacks

28 . 11044 - Searching for Nessy

29. 12279 - Emoogle Balance

................................................TO BE CONTINUED....................................

13026-Search the Khoj-solution hints

https://uva.onlinejudge.org/external/130/13026.pdf

After all it's an easy ad-hoc problem . Just think deeply then i guess you can solve it easily .

I have here solve this problem using string but you can complete using other means . Here's nothing but only one logic which is ,

1. It is said that jalil can mistake just one letter that means if any string matches (length-1) times with the mummy's phone number then that is answer  . Similar all the numbers will be the answer .

My accepted code is given below :

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

int main()
{
    int t,i=1,num,l,s;
    string n[1002];

    scanf("%d",&t);

    while(t>=i)
    {

        scanf("%d",&num);

        for(int j=1;j<=num+1;j++)
        {
            cin>>n[j];
        }

        l=n[num+1].length();

        printf("Case %d:\n",i);

        for(int j=1;j<=num;j++)
        {
            s=0;

            for(int k=0;k<l;k++)
            {
                if(n[num+1][k]==n[j][k])
                {
                    s++;
                }
            }

            if((s+1)==l || s==l)
            {
                cout<<n[j]<<endl;
            }

        }

        i++;
    }

    return 0;

}