Archive for the ‘Factorials’ Category

UVA – 941 – Permutations   1 comment


import java.util.*;

public class Permutations {
	public static long factorial(int n) {
		long res = 1;
		for (int i = 2; i <= n; i++)
			res *= i;
		return res;
	}

	public static String nThPermutation(String s, long n) {
		char[] arr = s.toCharArray();
		Arrays.sort(arr);
		StringBuilder sb = new StringBuilder(new String(arr));
		String res = "";
		while (n != 0) {
			int k = (int) (n / factorial(sb.length() - 1));
			long mod = n % factorial(sb.length() - 1);
			res = res + sb.charAt(k);
			sb.deleteCharAt(k);
			n = mod;
		}
		return res + sb;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int TC = in.nextInt();
		while (TC-- > 0) {
			String s = in.next();
			long n = in.nextLong();
			char[] arr = s.toCharArray();
			Arrays.sort(arr);
			System.out.println(nThPermutation(new String(arr), n));
		}
	}
}

Posted October 28, 2011 by epicrado in Factorials, Mathematics, Probability, String Processing

UVA – 568 – Just the Facts   Leave a comment


#include <stdio.h>
int main()
{
	int n,m,j,prod,five,two;
	while(scanf("%d",&m)==1)
	{
		n = m;
		five = 0;
		two = 0;
		prod=1;
		while(n>0)
		{
			j = n;
			while(j%5==0)
			{
				j/=5;
				five++;
			}
			while(j%2==0)
			{
				j/=2;
				two++;
			}
			prod=(prod*(j%10))%10;
			n--;
		}
		while(five>two)
		{
			prod=(prod*5)%10;
			five--;
		}
		while(two>five)
		{
			prod=(prod*2)%10;
			two--;
		}
		printf("%5d -> %d\n",m,prod);
	}
	return 0;
}

Posted September 5, 2011 by epicrado in Factorials

UVA – 10856 – Recover Factorial   1 comment


#include <stdio.h>
#define N 2703664
int factors[N];
int main()
{
	int i,j,k,mid,c=1;
	for(i=0;i<N;i++)
		factors[i]=0;
	for(i=2;i<N;i++)
	{
		if(!factors[i])
			factors[i]=1;
		for(j=2;(k=i*j)<N&&j<=i;j++)
			if(factors[j]==1)
				factors[k]=factors[j]+factors[i];
	}
	for(i=2;i<N;i++)
		factors[i]+=factors[i-1];
	scanf("%d",&k);
	while(k>=0)
	{
		i = 0;
		j = 2703663;
		while(j-i>1)
		{
			mid = (j+i)/2;
			if(factors[mid]<k)
				i = mid;
			else
				j = mid;
		}
		if(factors[i]==k)
			printf("Case %d: %d!\n",c++,i);
		else if(factors[j]==k)
			printf("Case %d: %d!\n",c++,j);
		else
			printf("Case %d: Not possible.\n",c++);
		scanf("%d",&k);
	}
	return 0;
}

Posted September 1, 2011 by epicrado in Breadth first search, Factorials, Prime numbers

UVA – 10338 – Mischievous Children   Leave a comment


No need to do anything special unsigned long long int enough for 20!
I've calculated all factorials and cached them to avoid recalculations! judge time : 0.028
#include <stdio.h>
#include <string.h>
char ascii[26];
char factorials[21];
unsigned long long int results[21];
int main()
{
	unsigned long long int res;
	register int i,j,cc;
	cc = 1;
	int c;
	char s[21];
	results[2]=2;
	for(i=3;i<21;i++)results[i]=results[i-1]*i;
	scanf("%d",&c);
	getchar();
	while(c-->0)
	{
		res = 1;
		gets(s);
		for(j=0;j<=20;j++)factorials[j]=0;
		for(i=0;i<26;i++)ascii[i]=0;
		i = strlen(s);
		for(j=0;j<i;j++)
			ascii[s[j]-'A']++;
		for(j=0;j<26;j++)
			factorials[ascii[j]]++;
		res = results[i];
		for(j=2;j<=20;j++)
			for(i=1;i<=factorials[j];i++)
				res/=results[j];
		printf("Data set %d: %llu\n",cc++,res);
	}
	return 0;
}

Posted August 19, 2011 by epicrado in Factorials

UVA – 11415 – Count the Factorials   Leave a comment


0.584 Seconds

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define N 2750000
static int* factors;
static int* counts;
int main()
{
	register int i,j,k;
	int  n,c;
	factors = (int*) malloc((N)*sizeof(int));
	counts = (int*) malloc(10000001*sizeof(int));
	factors[0] = 0;
	factors[1] = 0;
	for(i=2;i<N;i++)
	{
		factors[i] = 0;
	}
	for(i=2;i<N;i++)
	{
		if(!factors[i])
			factors[i] = 1;
		for(j=2;j<=i&&(k = j*i)<N;j++)
		{

			if(!factors[k]&&factors[j]==1)
					factors[k] = factors[i]+1;

		}

	}
	for(i=2;i<N;i++)
		factors[i] += factors[i-1];
	j = 0;
	for(i=1;i<10000001;i++)
	{
		for(;factors[j]<=i;j++);
		counts[i] = j;

	}
	scanf("%d",&c);
	while(c>0)
	{
		scanf("%d",&n);
		printf("%d\n",counts[n]);
		c--;
	}
	return 0;
}

Posted July 8, 2011 by epicrado in Factorials

UVA – 10220 – I Love Big Numbers !   Leave a comment


This one is pretty easy to solve using java's BigInteger class
import java.math.BigInteger;
import java.util.Scanner;

public class iLuvBigNumbers {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			BigInteger res = new BigInteger("1");
			int n = Integer.parseInt(in.nextLine());
			while (n > 0) {
				res = res.multiply(new BigInteger(n + ""));
				n--;
			}
			String r = res.toString();
			int sum = 0;
			for (int i = 0; i < r.length(); i++) {
				sum += (r.charAt(i) - 48);
			}
			System.out.println(sum);
		}
	}
}

Posted July 7, 2011 by epicrado in Factorials

UVA – 884 – Factorial Factors   Leave a comment


#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define N 1000001
static int* factors;
int main()
{
	register int i,j,k;
	int  n;
	factors = (int*) malloc((N)*sizeof(int));
	for(i=0;i<N;i++)
		factors[i] = 0;
	for(i=2;i<N/2;i++)
	{
		if(!factors[i])
			factors[i] = 1;
		for(j=2;j<=i&&(k = j*i)<N;j++)
			if(!factors[k]&&factors[j]==1)
					factors[k] = factors[i]+1;
	}
	for(i=N/2;i<N;i++)
		if(!factors[i])
			factors[i]=1;
	for(i=2;i<N;i++)
		factors[i] += factors[i-1];
	while(scanf("%d",&n)==1)
		printf("%d\n",factors[n]);
	return 0;
}


Posted July 7, 2011 by epicrado in Factorials