Translate

Sunday 18 January 2015

ANARC08E spoj solution 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
HII GUYS
this is easy problem.......
LOGIC::
   when you want to arrange n different thing at n places so total number of ways=n!
 
   but when things are not different i.e let x+y=n
  it means x things are of one type and y things are of another type
  then total no ways to arrange this things at n places is=(x+y)!/(x! * y!)

  IN this problem total number of possibility also equal to (x+y)!/(x! * y!)

  m-1 you can direct do this

 MY AC PYTHON SOLUTION IS: if you have any problem plz comment me below

import sys
while(1):
    x,y=map(int,sys.stdin.readline().split())
    if(x==-1 and y==-1):
        break
    fact1=1
    fact2=1
    fact3=1
    for i in range(x):
        fact1=fact1*(i+1)
    for i in range(y):
        fact2=fact2*(i+1)
    for i in range(x+y):
        fact3=fact3*(i+1)
    ans=fact3/(fact1*fact2)
    if(ans==(x+y)):
        print "%d+%d=%d"%(x,y,(x+y))
    else:
        print "%d+%d!=%d"%(x,y,(x+y))






m-2 you can this do by DP also

there is one formula for binomial coefficient
c(n,r)=c(n-1,r)+c(n-1,r-1)
c(n,r)=c(n-r,r)
here n=x+y
so
from 1st formula
c(X+Y,X)=c(X+Y-1,X)+c(X+Y-1,X-1)

now by using 2nd formula

c(X+Y,X)=c(Y-1,X)+c(Y,X-1)

my AC DP C++ solution is::if you have any problem plz comment me below......




#include<bits/stdc++.h>
using namespace std;
long long ans[11][11];
void pre()
{
 long long i,j;
  for(i=0;i<11;i++)
  {
   for(j=0;j<11;j++)
   {
     if(i==0 || j==0)
     ans[i][j]=1;
     else
     ans[i][j]=ans[i-1][j]+ans[i][j-1];
   }
  }
}
int main()
{
 int a,b;
 pre();
 while(1)
 {
  cin>>a>>b;
  if(a==-1 && b==-1)
  break;
  if((a+b)==ans[a][b])
  printf("%d+%d=%d\n",a,b,a+b);
  else
  printf("%d+%d!=%d\n",a,b,a+b);
 }
 return 0;
}
at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Working With Java Collections