Math – Page 7 – Live with passion

10023

Asif NaeemJuly 24, 2014

[highlight]Solution[/highlight]

/*
import java.math.BigInteger;
import java.util.Scanner;
public class Main {public static void main(String[] args) {
Scanner scanf = new Scanner(System.in);
int time;
time = scanf.nextInt();
System.out.println("");

for(int i = 0; i<time; i++){
BigInteger input = scanf.nextBigInteger();
if(i > 0)
System.out.println("");
BigInteger previous = input;
BigInteger distance, post, Two = BigInteger.valueOf(2), Negative = BigInteger.valueOf(-1);
if(input.equals(BigInteger.ZERO)){
System.out.println("0");
continue;
}
while(true){
post = input.divide(previous);
post = post.add(previous);
post = post.divide(Two);
distance = post.subtract(previous);
if(distance.equals(BigInteger.ONE)){

System.out.println(previous);
break;
}
int d = distance.compareTo(BigInteger.ZERO);
if(d < 0)
distance = distance.multiply(Negative);
else if(distance.equals(BigInteger.ZERO)){

System.out.println(post);
break;
}
previous = post;
}
}

}

}

*/

import java.util.*;
import java.math.*;
import java.math.BigInteger;
import java.util.Scanner;

public class Main{

static boolean didWork ;
public static BigInteger sqrt(BigInteger A)
{
BigInteger temp = A.shiftRight(BigInteger.valueOf(A.bitLength()).shiftRight(1).intValue()), result = null;
while (true)
{
result = temp.add(A.divide(temp)).shiftRight(1);
if (!temp.equals(result))
temp = result;
else
break ;
}
didWork = false ;
if (result.multiply(result).equals(A))
didWork = true ;

return result;
}

public static void main(String []args)
{
Scanner scanf = new Scanner(System.in);
int t= scanf.nextInt();
for(int i=0;i<t;i++)
{
BigInteger input = scanf.nextBigInteger();
if(i!=0)
{
System.out.println("");
}
System.out.println(sqrt(input));
}
}
};

import java.math.BigInteger;

import java.util.Scanner;

public class Main {public static void main(String[] args) {

Scanner scanf = new Scanner(System.in);

int time;

time = scanf.nextInt();

System.out.println("");

for(int i = 0; i<time; i++){

BigInteger input = scanf.nextBigInteger();

if(i > 0)

System.out.println("");

BigInteger previous = input;

BigInteger distance, post, Two = BigInteger.valueOf(2), Negative = BigInteger.valueOf(-1);

if(input.equals(BigInteger.ZERO)){

System.out.println("0");

continue;

}

while(true){

post = input.divide(previous);

post = post.add(previous);

post = post.divide(Two);

distance = post.subtract(previous);

if(distance.equals(BigInteger.ONE)){

System.out.println(previous);

break;

}

int d = distance.compareTo(BigInteger.ZERO);

if(d < 0)

distance = distance.multiply(Negative);

else if(distance.equals(BigInteger.ZERO)){

System.out.println(post);

break;

}

previous = post;

}

import java.util.*;

import java.math.*;

import java.math.BigInteger;

import java.util.Scanner;

public class Main{

static boolean didWork ;

public static BigInteger sqrt(BigInteger A)

{

BigInteger temp = A.shiftRight(BigInteger.valueOf(A.bitLength()).shiftRight(1).intValue()), result = null;

while (true)

{

result = temp.add(A.divide(temp)).shiftRight(1);

if (!temp.equals(result))

temp = result;

else

break ;

}

didWork = false ;

if (result.multiply(result).equals(A))

didWork = true ;

return result;

}

public static void main(String []args)

{

Scanner scanf = new Scanner(System.in);

int t= scanf.nextInt();

for(int i=0;i<t;i++)

{

BigInteger input = scanf.nextBigInteger();

if(i!=0)

{

System.out.println("");

}

System.out.println(sqrt(input));

}

};

Modular Problem: Mod of a negative number ..llike -16%3 = 2 It is DP problem. such input of data is in p[]; divident is k; let , s=a[0]%k; and s=-a[0]%k; if any of s <0 then s =s+k [see mod of a negative number] keep track in 2D array in a[0][s]=1. s=s+p[1]%k, for each s check

Continue Reading “10036” →

10078

Asif NaeemJuly 20, 2014

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point{
int x;
int y;
}P;
vector<Point> vb,vb1;
int used[100];

bool cmp(Point a,Point b)
{
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}

int ccw(Point a,Point b,Point c)
{
int p = a.x*b.y - a.x*c.y - a.y*b.x + a.y*c.x + b.x*c.y - c.x * b.y;
if(p>0)
return 1;
else
return 0;
}

int main()
{
int N,a,b;

while(cin>>N)
{
if(N==0)
break;
vb.clear();
for(int i=0;i<N;i++)
{
cin>>a>>b;
P.x=a;
P.y=b;
used[i]=0;
vb.push_back(P);
}

fill(used,used+N,0);
if(N<=3)
{
cout<<"No\n";
continue;
}
sort(vb.begin(),vb.end(),cmp);

vb1.clear();

vb1.push_back(vb[0]);
used[0]=1;

for(int i=0;i<(N-1);i++)
{
int next;
for(int j=1;j<N;j++)
{
if(used[j]==0)
{
next=j;
break;
}
}

for(int j=1;j<N;j++)
{
if(used[j]==0 && ccw(vb1[i],vb[next],vb[j])==0)
next = j;
}
vb1.push_back(vb[next]);
used[next]=1;
}

vb1.push_back(vb1[0]);
vb1.push_back(vb1[1]);

int f=0;
for(int i=0;i+2<vb1.size();i++)
{
if(ccw(vb1[i],vb1[i+1],vb1[i+2])==0)
{
cout<<"Yes\n";
f=1;
break;
}
}
if(f==0)cout<<"No\n";
}

return 0;
}

100

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct Point{

int x;

int y;

}P;

vector<Point> vb,vb1;

int used[100];

bool cmp(Point a,Point b)

{

if(a.x!=b.x)

return a.x<b.x;

else

return a.y<b.y;

}

int ccw(Point a,Point b,Point c)

{

int p = a.x*b.y - a.x*c.y - a.y*b.x + a.y*c.x + b.x*c.y - c.x * b.y;

if(p>0)

return 1;

else

return 0;

}

int main()

{

int N,a,b;

while(cin>>N)

{

if(N==0)

break;

vb.clear();

for(int i=0;i<N;i++)

{

cin>>a>>b;

P.x=a;

P.y=b;

used[i]=0;

vb.push_back(P);

}

fill(used,used+N,0);

if(N<=3)

{

cout<<"No\n";

continue;

}

sort(vb.begin(),vb.end(),cmp);

vb1.clear();

vb1.push_back(vb[0]);

used[0]=1;

for(int i=0;i<(N-1);i++)

{

int next;

for(int j=1;j<N;j++)

{

if(used[j]==0)

{

next=j;

break;

}

for(int j=1;j<N;j++)

{

if(used[j]==0 && ccw(vb1[i],vb[next],vb[j])==0)

next = j;

}

vb1.push_back(vb[next]);

used[next]=1;

}

vb1.push_back(vb1[0]);

vb1.push_back(vb1[1]);

int f=0;

for(int i=0;i+2<vb1.size();i++)

{

if(ccw(vb1[i],vb1[i+1],vb1[i+2])==0)

{

cout<<"Yes\n";

f=1;

break;

}

if(f==0)cout<<"No\n";

}

return 0;

}

10025

Asif NaeemJuly 15, 2014

#include <iostream>

using namespace std;

unsigned long long int T[60001];

int main()
{
int t,n,c=0;
int r,pos;
T[1]=1;
for(int i=2;i<60001;i++)
T[i]=T[i-1]+i;

//cout<<T[60000]<<"\n";
cin>>t;
c=t;
int k=0;
while(t--)
{
cin>>n;

if(k!=c &&k!=0)
cout<<"\n";
k++;
if(n==0)
{
cout<<3<<"\n";
continue;
}
if(n==1)
{
cout<<2<<"\n";
continue;
}
if(n<0)
n*=-1;
for(int i=1;i<60001;i++)
{
if(T[i]>=n)
{
r= T[i];
pos=i;
break;
}
}

int d=r-n;

if(d==0 || d%2==0)
{
cout<<pos<<"\n";
continue;
}
while((T[pos]-n)%2==1)
{
pos++;
}

cout<<pos<<"\n";

}

return 0;
}

#include <iostream>

using namespace std;

unsigned long long int T[60001];

int main()

{

int t,n,c=0;

int r,pos;

T[1]=1;

for(int i=2;i<60001;i++)

T[i]=T[i-1]+i;

//cout<<T[60000]<<"\n";

cin>>t;

c=t;

int k=0;

while(t--)

{

cin>>n;

if(k!=c &&k!=0)

cout<<"\n";

k++;

if(n==0)

{

cout<<3<<"\n";

continue;

}

if(n==1)

{

cout<<2<<"\n";

continue;

}

if(n<0)

n*=-1;

for(int i=1;i<60001;i++)

{

if(T[i]>=n)

{

r= T[i];

pos=i;

break;

}

int d=r-n;

if(d==0 || d%2==0)

{

cout<<pos<<"\n";

continue;

}

while((T[pos]-n)%2==1)

{

pos++;

}

cout<<pos<<"\n";

}

return 0;

}

10061

Asif NaeemJuly 14, 2014

[highlight]Solution[/highlight] /* Now we can break the Base B as a product of primes : B = a^p1 * b^p2 * c^p3 * … Then the number of trailing zeroes in N factorial in Base B is given by the formulae min{1/p1(n/a + n/(a*a) + ….), 1/p2(n/b + n/(b*b) + ..), ….}. And the number

Continue Reading “10061” →

993

Asif NaeemJune 1, 2014

Solution:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
int t,c;
long long int n;
vector<long long int> v;

cin>>t;
while(t--)
{
cin>>n;
if(n<=9)
{
cout<<n<<"\n";
continue;
}
while(n>=10)
{
v.clear();
c=0;
for(long long int i=9;i>=2;i--)
{
if(n%i==0)
{
c=1;
n/=i;
v.push_back(i);
break;
}
}
if(n<10)
{
v.push_back(n);
break;
}
if(c==0)
{
v.clear();
cout<<"-1\n";
break;
}
}
if(v.size()==0)
continue;
for(int i=v.size()-1;i>=0;i--)
cout<<v[i];
cout<<"\n";
}

return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int t,c;

long long int n;

vector<long long int> v;

cin>>t;

while(t--)

{

cin>>n;

if(n<=9)

{

cout<<n<<"\n";

continue;

}

while(n>=10)

{

v.clear();

c=0;

for(long long int i=9;i>=2;i--)

{

if(n%i==0)

{

c=1;

n/=i;

v.push_back(i);

break;

}

if(n<10)

{

v.push_back(n);

break;

}

if(c==0)

{

v.clear();

cout<<"-1\n";

break;

}

if(v.size()==0)

continue;

for(int i=v.size()-1;i>=0;i--)

cout<<v[i];

cout<<"\n";

}

return 0;

}

960

Asif NaeemJune 1, 2014

Gaussian Prime Integer Problem Theory: First we should know that the multiple of two lengths is the length of the original one. For example, (4,3) has a length of 5, so if we can break (4,3) down into A & B, length(A) * length(B) is also 5. Next we’ll iterate through all possible combinations (lengths.)

Continue Reading “960” →

Category: Math

10023

10036

10078

10025

10061

993

960

Archives

Categories