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

1305 - Area of a Parallelogram

সমস্যাটি খুব-ই সোজা মানের । এটি সমাধানের জন্য যে knowledge থাকা লাগবে টা একজন উচ্চমাধ্যমিক শিক্ষার্থীর রয়েছে । আমরা প্রথমে সমস্যাটি সমাধানের জন্য প্রয়োজনীয় concept এর আলোচনা করব এবং পরে সমস্যাটি সমাধানের জন্য প্রয়োজনীয় step অবলম্বন করব ।

Problem Specification :
তোমাকে একটি সামান্তরিক দেয়া হল যার প্রথম তিনটি স্থানাঙ্ক তুমি জান । মনে কর, সেই গুলিহল , Ax,Ay,Bx,By,Cx,Cy . চতুর্থ বাহুর স্থানাঙ্ক হল Dx,Dy .

এখন তোমাকে চতুর্থ বাহুর স্থানাঙ্ক এবং সামান্তরিকটির ক্ষেত্রফল বের করা লাগবে ।

Theory of Solution :

সামান্তরিকের তিনটি বাহুর স্থানাঙ্ক জানা থাকলে চতুর্থ বাহুর স্থানাঙ্ক খুব সহজেই নিচের ফর্মুলা অনুসারে বের করা যায় ।

Dx = Ax + Cx-Bx
Dy = Ay+Cy - By

Area নির্ণয় করার কোন সুত্র উচ্চমাধ্যমিক পর্যায়ে পরে এসেছ ? ঠিকই ধরতে পেরেছ । Area নির্ণয় এর ফর্মুলা হবেঃ

q=((Ax*By)+(Bx*Cy)+(Cx*Dy)+(Dx*Ay))-((Ay*Bx)+(By*Cx)+(Cy*Dx)+(Dy*Ax));
area=0.5*q;

সতর্কতাঃ
Co-ordinate এর অবস্থানের কারণে Area এর মান negative আসতে পারে । কাজেই Check করে নাও ।
Program Outline:

#include<stdio.h>
int main()
{
int a,ax,ay,bx,by,cx,cy,dx,dy,area,i,q;
scanf("%d",&a);
for(i=0;i<a;i++){
scanf("%d%d%d%d%d%d",&ax,&ay,&bx,&by,&cx,&cy);
dx=cx+ax-bx;
dy=cy+ay-by;
q=((ax*by)+(bx*cy)+(cx*dy)+(dx*ay))-((ay*bx)+(by*cx)+(cy*dx)+(dy*ax));
if(q<0)
q*=-1;
area=0.5*q;
printf("Case %d: %d %d %d\n",i+1,dx,dy,area);
}
}

শনিবার, ২ মার্চ, ২০১৩

Solution Of Light Online Judge 1236 - 1236 - Pairs Forming LCM

Problem Statement :

The meaning of the questions: given n, now requires the least common multiple of the logarithm of n.

Solution Idea :
1. factorize n,

2. n can be written as in the form of ^ (K1) * P2 ^ (K2) ........ PM * (km)

3. Then the answer is ((2k1 +1) * (2k2 +1) * ....... (2km +1) +1) / 2.

4. Its principle is separately for each factor to see 2 * k +1, and then for each factor.

5. Multiplying all factors, so that the last draw answers, each pair calculated twice (addition <n,n> the),

6. the final answer (ANS +1) / 2;

মঙ্গলবার, ২৬ ফেব্রুয়ারী, ২০১৩

Solution of Light OJ - 1102 - Problem Makes Problem

Problem Statement :

As I am fond of making easier problems, I discovered a problem. Actually, the problem is 'how can you make n by adding k non-negative integers?' I think a small example will make things clear. Suppose n=4 and k=3. There are 15 solutions. They are

1. 0 0 4

2. 0 1 3

3. 0 2 2

4. 0 3 1

5. 0 4 0

6. 1 0 3

7. 1 1 2

8. 1 2 1

9. 1 3 0

10. 2 0 2

11. 2 1 1

12. 2 2 0

13. 3 0 1

14. 3 1 0

15. 4 0 0

As I have already told you that I use to make problems easier, so, you don't have to find the actual result. You should report the result modulo 1000,000,007.

Problem Logic :

1. Note that a similar classic problem is the following:


 2.  How many ways can 10 pieces of candy be divided among 4 children?

3. For this case we need to find the number of solutions to the equation

                                i+j+k+l = 10

                                where i, j, k, and l are non-negative integers. 

 4. We can find the answer using a technique popularly known as "stars and bars".  

5. The idea behind this method is the following:

                (*) We represent the objects to be divided by "stars": ****
                (*) To indicate dividing the object into groups, we use bars as "divider" symbols:  |||

6.For our problem, we have ten pieces of candy:

                          **********

7. To divide these ten objects into four groups, we need three dividers:

                          **********|||

8. The particular arrangement of the "stars and bars" shown above 
specifically represents the case where the first child gets all ten 
pieces of candy.

9.  Each different arrangement of these stars and bars represents a distinct distribution of the ten pieces of candy among the four children.

10. For example, the arrangement represents the case where the first child gets 3 pieces,


                                             ***|*|**|****

 the second child 1, the third child 2, and the fourth child 4.

11. So the number of different ways of distributing 10 pieces of candy 
among 4 children is the number of distinct arrangements of the stars 
and bars.

12. With 10 stars and 3 bars, this number is, as you probably 
know,

                            (10+3)!                                 13*12*11
                          --------- = "13 choose 3" = -------- = 13*2*11 = 286
                           (10!)(3!)                                   3*2*1

13. So the number of terms in the expansion of (a+b+c+d)^10 is 286.

14. If we are raising an expression with "m" terms to the "n"th power, 
then we have n "stars" and (m-1) "bars"; the number of terms in the 
expansion is then

  (n+(m-1))!
  ---------- = "(n+m-1) choose (m-1)"
  (n!)(m-1)!


15. Note this agrees with what you noted about the number of terms in the 
expansion of (a+b)^n.  Here the number of terms, "m", is 2; so the 
number of terms in the expansion of (a+b)^n is

  "(n+m-1) choose (m-1)" = "n+1 choose 1" = n+1

বুধবার, ২০ ফেব্রুয়ারী, ২০১৩

Solution of Light OJ 1140 - How Many Zeroes?

সবাইকে বসন্তের বাতাসে ভেসে ভেড়ান ফুলের কলির শুভেচ্ছা দিয়ে আমরা এক নতুন সমস্যার সমাধান করতে যাচ্ছি ।
Problem Statement :
Jimmy writes down the decimal representations of all natural numbers between and including a and b, (a ≤ b). How many zeroes will he write down?

Example :
Suppopse Jimmy write 10 and 15 as in following order .

10 11 12 13 14 15

In the above number there are total 1 zeroes . So you have to output 1 .

Solution Idea :

1. Notation: $\overline{a_n a_{n-1} \dots a_0}$ denotes an integer $a = a_n 10^n + a_{n-1} 10^{n-1} + \cdots + a_0$ . That is $a_n,\ a_{n-1},\ \dots,\ a_0$ are the decimal digits of

a

, from left to right.

2. Let's solve an easier problem.
-------- How many 0's are there in numbers between 0 and

b

inclusive?

3. If we denote this number by

f (b)

then the answer to our original problem is just

f (n) - f (m - 1)

.

4. Let $b = \overline{b_n b_{n-1} \dots b_0}$ .

5. Let's find for each position $0 \le k < n$ how many times a zero appears there as we are counting from 0 to

b

.

6. If

b k > 0

, then by setting

a k = 0

, and choosing the other digits according to the constraints: $1 \le \overline{a_n \dots a_{k+1}} \le \overline{b_n \dots b_{k+1}}$ , and $0 \le \overline{a_{k-1} \dots a_0} < 10^k$ ,

7. we will have a positive integer $a = \overline{a_n \dots a_0}$ , which is not greater than

b

, and the

k

-th digit of which exists and is equal to zero.

8. There are $10^k \cdot \overline{b_n \dots b_{k+1}}$ such integers.

9. If

b k = 0

, same analysis as above applies, except that when $\overline{a_n \dots a_{k+1}} = \overline{b_n \dots b_{k+1}}$ there are only $1 + \overline{b_{k-1} \dots b_0}$ ways to choose the digits to the right of

a k

.

10. So in this case there are $(10^k) \cdot (\overline{b_n \dots b_{k+1}} - 1) + 1 + \overline{b_{k-1} \dots b_0}$ integers between 0 and

b

, in which the

k

-th digit is zero.

11. The total number of zeroes is the sum of the number of times a zero occurs in each position, plus 1 for the integer "0".

Solution Code :

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

long long int count_zeroes(long long int b)
{
if (b < 0) return 0;

// Compute decimal representation of b
char s[20];
sprintf(s, "%lld", b);
int n = strlen(s);

// Compute powers of 10
long long ten[20] = { 1 };
for (int n = 1; n < 20; n++)
ten[n] = ten[n-1] * 10;

// Compute suffixes of b.suf[k] = atoll(s+k).
long long suf[20];
suf[n] = 0;
for (int i = n-1; i >= 0; i--)
suf[i] = suf[i+1] + (s[i] - '0') * ten[n-i-1];

long long res = 1, pref = 0;
for (int k = 1; k < n; k++) {
pref = pref * 10 + (s[k-1] - '0');
// pref is equal to integer, formed by first k digits of b.

if (s[k] != '0')
res += pref * ten[n-k-1];
else
res += (pref - 1) * ten[n-k-1] + suf[k+1] + 1;
}
return res;
}

int main()
{
int i,test;
long long m,n;
cin>>test;
for(int i=1;i<=test;i++)
{
cin>>m>>n;
printf("Case %d: %lld\n",i,count_zeroes(max(m,n))-count_zeroes(min(m,n)-1));
}
return 0;
}

মঙ্গলবার, ১২ ফেব্রুয়ারী, ২০১৩

Solution of Light OJ - 1077 - How Many Points?

Problem Statement :
Given two points A and B on the X-Y plane, output the number of the lattice points on the segment AB. Note that A and B are also lattice point. Those who are confused with the definition of lattice point, lattice points are those points which have both x and y co-ordinate as integer.

For example, for A (3, 3) and B (-1, -1) the output is 5. The points are: (-1, -1), (0, 0), (1, 1), (2, 2) and (3, 3).

Problem Solution :

Let one of the points be

⟨a,b⟩ and the other

⟨c,d⟩; then the number of lattice points on the line segment joining them is the same as the number on the line segment joining

⟨0,0⟩ to

⟨c−a,d−b⟩. Thus, you might as well focus on counting the number of lattice points on the segment joining the origin to

⟨m,n⟩ for integers

m and

n. Look at the equation of the line containing this segment: it’s

y = n m x .

Suppose that when you reduce

nm to lowest terms, you get

ab. Then your equation is

y = a b x,

and

y is an integer if and only if

b∣x.

Suppose that the points are

⟨−2,55⟩ and

⟨1011,1055⟩. I’d look at the segment from the origin to

⟨1011−(−2),1055−55⟩=⟨1013,1000⟩. It lies on the line

y = 1000 1013 x .

Any lattice point on that line must have both

x and

y integers, so suppose that

x is an integer. When is

10001013x an integer? The fraction is in lowest terms, so this occurs only when

x is a multiple of

1013. On the other hand, we’re looking only at the segment between

⟨0,0 and

⟨1013,1000⟩, so clearly we must have

0≤x≤1013. How many multiples of

1013 are there in this range? Just two,

0 and

1013. Thus, the endpoints are the only lattice points on that segment. Translating it parallel to itself up and to the left by adding

⟨2,−55⟩ to restore the original endpoints doesn’t change the number of lattice points, so

⟨−2,55⟩ and

⟨1011,1055⟩ are the only lattice points on the original segment.

Solution Code :

#include <stdio.h>

long long Ax, Ay, Bx, By, dx, dy;
long long ABS (long long n)
{
return n> 0? n:-n;
}

long Gcd(long long a,long long b)
{
if(b==0)
return a;
else
return Gcd(b, a%b);
}

int main()
{
int i, T;
scanf ("%d",&T);
for (i = 1; i <= T; i++)
{
scanf ("%lld %lld %lld %lld",&Ax,&Ay,&Bx,&By);
printf ("Case %d: %lld\n", i, Gcd(ABS(Ax-Bx),ABS(Ay-By))+1);
}
return 0;
}