Archive for the 'UVa Solutions' Category

05
Feb
12

[UVa] 10006 – Carmichael Numbers

Theory: http://www.geeksforgeeks.org/archives/28

/* Faith-M */

//Headers
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <clocale>
//Defines
#define pow2(i) (1<<i)
#define bit(i) (1<<i)
#define isOdd(i) (i&1)
#define isEven(i) (!(i&1))
#define isPrime(i) ((i==2) || ((i&1) && !pTest[i])) //pTest has to be the bool array's name
#define sz(i) i.size()
#define vec(type,name) vector< type > name
#define rep(i,a,b) for(int i=a ; i<=b ; i++)
#define swap(type,a,b) {type t=a; a=b; b=t;}
#define sum(a,n) ( (n*(n+1)/2) - (a-1)*a/2 )
#define iscap(i) (i>='A'&&i<='Z')
#define issmall(i) (i>='a'&&i<='z')
#define isnum(i) (i>='0'&&i<='9')
#define issymbol(i) (!(i>='a'&&i<='z') && !(i>='A'&&i<='Z') && !(i>='0'&&i<='9'))
#define mk(i,j) make_pair(i,j)
#define ERROR 1e-11
#define mx(a,b) (a>b?a:b)
//Type Defs
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;

using namespace std;

bool ver[1000000];
bool crm[65000];

int sv()
{
    int i, j, k=1;

    ver[0]=ver[1]=true;
    ver[2]=false;
    for (i=3 ; i<=65000 ; i+=2)
    {
        if (!ver[i])
        {
            k++;
            for (j=3 ; i*j<=65000 ; j+=2)
            {
                ver[i*j] = true;
            }
        }
    }
    return k;
}



//long bigmod(long b,long p,long m) {
//    if (p == 0)
//        return 1;
//    else if (p%2 == 0)
//        return square(bigmod(b,p/2,m)) % m; // square(x) = x * x
//    else
//        return ((b % m) * bigmod(b,p-1,m)) % m;
//}

lint powr(lint a, lint n)
{
    lint t = n;
    lint x = a%n;

    while (t-->1)
    {
        //if (a>=n) a%=n;
        a%=n;
        a*=(x);
    }
    return (a%n);
}

lint pwr(lint n, lint p, lint b)
{
    if (!p) return 1; // Joke

    lint r=1;

    while (p > 0)
    {
        if ((p&1) == 1)     // The current power is odd so after sqrt() modding u multiply an extra n
        {
            r = (r * n) % b;
        }

        p >>= 1;    // Shifting 1 bit right, getting to the next power

        n = (n * n) % b;
    }

    return r % b;
}

void gen_crm()
{
    lint n, i;

    for (n=2 ; n<=65000 ; n++)
    {
        if (ver[n])
        for (i=2 ; i<=(n-1) ; i++)
        {
            if ( pwr(i,n,n) != i )
            {
                crm[n] = true;
                break;
            }
        }
    }
}

//int ar[] = {561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973};

int main()
{
    /*freopen("input.txt","r+",stdin);
    freopen("output.txt","w+",stdout);/**/

    //int kase=1, kounter=1;

//    for (cin >> kase ; kase ; kase--)
//    {
//
//    }

    lint n, i;

    sv();
    gen_crm();


    while (cin >> n && n)
    {

        if ( ver[n] && !crm[n] )
        {
            cout << "The number " << n << " is a Carmichael number." << endl;
        } else
        {
            cout << n << " is normal." << endl;
        }
    }

    return 0;
}


26
Sep
11

[UVa] 10004 – Bicoloring

Method:
First color the whole graph using DFS
Then recheck the given edge list for common colors in vertexes.

bool state;
int c[1000], color[1000], clr, n, adj[1000][1000], list[1000][2];
void dfs_core(int i, int n, int p)
{
    int j;

    color[i]=true;
    if (p<0) c[i]=0;
    else c[i]=(p+1)%2;

    FOR(j, 0, n)
    {
        if (!color[j] && adj[i][j])
        {
            dfs_core(j,n,c[i]);
        }

    }
}
void dfs_shell(int n)
{
    int i;

    clr=0;
    FOR(i, 0, n)
    {
        color[i]=false;
        c[i]=-1;
    }
    FOR(i, 0, n)
    {
        if (!color[i])
            dfs_core(i,n,c[i]);
    }
}

int main()
{
    int i, j, x, y, e;
    while (scanf("%d",&n) && n)
    {
        FOR(i, 0, n)
        {
            FOR(j, 0, n)
            {
                adj[i][j]=0;
            }
        }
        scanf("%d",&e);
        FOR(i, 0, e)
        {
            scanf("%d %d",&x,&y);
            adj[x][y]=adj[y][x]=1;
            list[i][0]=x;
            list[i][1]=y;
        }
        dfs_shell(n);

        state=true;
        FOR(i, 0, e)
        {
            if (c[list[i][0]]==c[list[i][1]])
            {
                state=false;
                break;
            }
        }

        if (state)
        {
            printf("BICOLORABLE.\n");
        } else
        {
            printf("NOT BICOLORABLE.\n");
        }
    }
    return 0;
}
16
Sep
11

[UVa] 495 – Fibonacci Freeze


import java.util.Scanner;
import java.math.BigInteger;
/**
 *
 * @author Tafhim
 */
public class Main {

    public static void main(String[] args) {
        BigInteger[] fibs = new BigInteger[5004];
        fibs[0] = BigInteger.ZERO;
        fibs[1] = BigInteger.ONE;
        for (int i=2 ; i&lt;=5000 ; i++)
        {
            fibs[i] = fibs[i-1].add(fibs[i-2]);
        }
        Scanner input = new Scanner(System.in);

        int q;

        while (input.hasNext())
        {
            q = input.nextInt();
            System.out.printf(&quot;The Fibonacci number for %d is %d\n&quot;,q,fibs[q]);
            
        }
    }
}

09
Sep
11

Analysis:
Draw the coordinate system but start from 1 not 0, just to escape negative value problems. Draw it like a triangle where the top has 1. Now see that on the right side, every i-th number is the sum of all numbers till i.
1 = 1x(1+1)/2
3 = 2x(2+1)/2
6 = 3x(3+1)/2
10 = 4x(4+1)/2
15 = 5x(5+1)/2
So, given the x coordinate you can find the first number in that row using X*(X+1)/2, BUT make X=X+1 first.
To find the Y-th element (in my case (Y+1)-th, you can use the formula
S = a + (a+d) + (a+2d) + … + [a + (n-1)d] = n[2a + (n-1)d]/2
But you have to modify it a bit first. This is derived from the analysis that every number in a row has some initial numbers lost except the first row. In X=2, 2 is not in the series, in X=3, 3 and 4 are not in the series. This keeps increasing by 1 at every i. So the series is
Y[0], Y[0]+1×1, Y[0]+1×2, Y[0]+1×3 ……
So you can simply use the formula with a=0 and n=Y+(X-1). Just add X to that.
Find both the numbers this way and print their difference. Done!!!.

A useful link for Summation formulas

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;
int sum(int a, int n)
{
    return n*(2*a+(n-1)*1)/2;
}
int main()
{
    int test, kase=1, x1, x2, y1, y2, num1, num2, temp, n, a;
    scanf("%d",&test);
    while (test--)
    {
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        x1++; x2++; y1++; y2++;


        num1 = x1+(sum(0,y1+(x1-1)));
        num2 = x2+(sum(0,y2+(x2-1)));


        printf("Case %d: %d\n",kase++,num2-num1);
    }
    return 0;
}

08
Sep
11

[UVa] 11057 – Exact Sum

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;
int a[20000]={0};

bool cmp(int x, int y)
{
    return (x<y);
}
int cmp2(const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}
int main()
{
    int n, i, val, *p, x, s, maxDiff, pX, pY;

    while (scanf("%d",&n)==1)
    {

        for (i=0 ; i<n ; i++)
        {
            scanf("%d",&a[i]);

        }
        scanf("%d",&val);
        QSORT(a,n,int,cmp2);
        maxDiff = 9999999;
        for (i=0 ; i<n-1 ; i++)
        {
            x=a[i];
            s = val-x;

            p = NULL;
            p = (int*)bsearch(&s,&a[i+1],n-i-1,sizeof(int),cmp2);
            if (p)
            {
                if (abs((*p)-x)<maxDiff)
                {
                    pX = x;
                    pY = (*p);
                    maxDiff = abs((*p)-x);

                }
            }

        }
        if (pX>pY) swap(pX,pY);
        printf("Peter should buy books whose prices are %d and %d.\n\n",pX,pY);

    }
    return 0;
}



Rap sheet

  • 5,079 hits

Follow

Get every new post delivered to your Inbox.