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;
}
06
Sep
11

[UVa] 944 – Happy Numbers

Very easy problem, couple of holes to look for to avoid TLE. Keep track if a number is revisited during the happy checks ;) Otherwise it might make you sad. And make a list instead of HAPPY/NOT-HAPPY list. Makes things faster.

Critics: Not much, see if your cycle number for 1 is 1. It’s gotta be 1.

#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 sqrs[10];
int digSums[100000]={0};
int list[100000][2];
void sqr()  //Function to generate squre of all decimal digits
{
    for (int i=0 ; i<=9 ; i++)
    {
        sqrs[i]=i*i;
    }
}
int digSum(int n)
{
    if (digSums[n])
        return digSums[n]; //If the value is already there, precalculated

    int sum=0, temp=n;
    while (n)
    {
        sum += sqrs[n%10];
        n/=10;
    }
    digSums[temp]=sum;
    return digSums[temp];
}
int happyList()
{
    int i, j, k=0, cycle=0;
    bool happy;
    sqr();
    for (i=1 ; i<=99999 ; i++)
    {
        bool vis[500]={false}; // Keeping track of cycles
        cycle=0;
        for (j=digSum(i), happy=false ; j<=405 ; j=digSum(j)) //the limit 405 is because sum_of_sqr_of_digits(999999) = 405
        {
            cycle++;
            if (j==1)
            {
                happy=true;
                break;
            }
            if (j==i || vis[j]) // Cycle detection
            {
                happy=false;
                break;
            }
            vis[j]=true;
        }
        if (happy)
        {
            list[k][0]=i;
            list[k][1]=cycle+1;
            k++;
        }
    }
    return k;
}


int main()
{
    int a, b, i, kase=1, listLength;
    listLength=happyList();

    if (a>=b) swap(a,b);

    list[0][1]=1; //System faults :p

    while (cin >> a >> b)
    {
        if (kase++>1) cout << endl;
        for (i=0 ; list[i][0]<a && i<listLength ; i++)
        {
            //cout << "Passing" << endl;
        }
        for (i ; list[i][0]<=b && i<listLength ; i++)
        {
            cout << list[i][0] << " " << list[i][1] << endl;
        }
    }
    return 0;
}

06
Sep
11

[UVa] 10191 – Longest Nap

The first version is a simple one, just sorting the task durations. The second one uses an array flagging and then using bruteforce finding the best time.

/* --------------------------> BISMILLAHIR RAHMANIR RAHIM <------------------------------ */
/* ------------------------> Tafhim Ul Islam [ CSE-09@IIUC ] <--------------------------- */
#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;
char input[1000];

struct timex
{
    int start;
    int end;
} array[500];

bool cmp(timex x, timex y)
{
    return (x.start < y.start);
}

int main()
{
    int nTask, i, maxStart, maxInterval, interval;
    int hour1, hour2, minute1, minute2, hour, minute, j, day=1;
    while ( cin >> nTask )
    {
        getchar();
        i=0;
        array[i].start = 600;
        array[i].end = 600;
        for (i=1 ; i<=nTask ; i++)
        {
            gets(input);
            sscanf(input,"%d:%d %d:%d",&hour1,&minute1,&hour2,&minute2);

            array[i].start = hour1*60 + minute1;
            array[i].end = hour2*60 + minute2;
        }
        array[i].start = 1080;
        array[i].end = 1080;
        i++;

        sort(array,array+i,cmp);

        for (j=1, maxInterval=-1 ; j<=nTask+1 ; j++)
        {
            interval = array[j].start-array[j-1].end;
            if (interval > maxInterval)
            {
                maxStart = array[j-1].end;
                maxInterval = interval;
            }
        }

        hour = (int)maxStart/60;
        minute = maxStart%60;

        if (maxInterval>=60)
            printf("Day #%d: the longest nap starts at %d:%.2d and will last for %d hours and %d minutes.\n",day++,hour,minute,(int)maxInterval/60,maxInterval%60);
        else
            printf("Day #%d: the longest nap starts at %d:%.2d and will last for %d minutes.\n",day++,hour,minute,maxInterval);

    }
    return 0;
}

/* --------------------------> BISMILLAHIR RAHMANIR RAHIM <------------------------------ */
/* ------------------------> Tafhim Ul Islam [ CSE-09@IIUC ] <--------------------------- */
#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;
char inp[10000];
int data[60][60];
struct time
{
    int h, m;
} initTime, maxInitTime;
int napTimer, maxNapTimer;

void setter(int hour1, int minute1, int hour2, int minute2)
{
    int i, j, jLimit;

    for (i=hour1 ; i<=hour2 ; i++)
    {
        if (i==hour1) j=minute1;
        else j=0;
        if (i==hour2) jLimit=minute2-1;
        else jLimit = 59;

        for ( ; j<=jLimit ; j++)
        {
            data[i][j]=1;
        }
    }
}

void parser(char *inp)
{
    int i, j, hour1, hour2, minute1, minute2;
    char h[10];

    for (i=0 ; !(inp[i]>='0') && !(inp[i]<='9') ; i++); // Skipping initial blanks
    for (i, j=0 ; inp[i]>='0' && inp[i]<='9' ; i++, j++)
    {
        h[j]=inp[i];
    }
    h[j]='\0';
    hour1 = atoi(h);
    for (i ; inp[i]!=':' ; i++);
    for (i ; inp[i]==':' ; i++);
    for (i ; !(inp[i]>='0') && !(inp[i]<='9') ; i++);
    for (i, j=0 ; inp[i]>='0' && inp[i]<='9' ; i++, j++)
    {
        h[j]=inp[i];
    }
    h[j]='\0';
    minute1 = atoi(h);

    //cout << " --> " << i << endl;
    for (i ; inp[i]==' ' ; i++); //Skipping spaces
    for (i, j=0 ; inp[i]>='0' && inp[i]<='9' ; i++, j++)
    {
        h[j]=inp[i];
    }
    h[j]='\0';
    hour2 = atoi(h);
    for (i ; inp[i]!=':' ; i++);
    for (i ; inp[i]==':' ; i++);
    for (i ; !(inp[i]>='0') && !(inp[i]<='9') ; i++);
    for (i, j=0 ; inp[i]>='0' && inp[i]<='9' ; i++, j++)
    {
        h[j]=inp[i];
    }
    h[j]='\0';
    minute2 = atoi(h);

    setter(hour1, minute1, hour2, minute2);
}

void initData()
{
    int i, j;
    for (i=10 ; i<=20 ; i++)
    {
        for (j=0 ; j<=60 ; j++)
        {
            data[i][j]=0;
        }
    }
}

void napFinder()
{
    bool napOpen;
    napTimer=0;
    maxNapTimer=-1;
    maxInitTime={-1,-1};
    initTime={-1,-1};
    int i, j;
    napOpen=false;
    if (data[10][0]==0)
    {
        //napOpen=true;
        initTime={10,0};
    }

    for (i=10 ; i<18 ; i++)
    {
        //cout << "\t" << i << endl;

        for (j=0 ; j<=59 ; j++)
        {

            if (data[i][j]==0)
            {
                if (napOpen)
                {
                    napTimer++;

                }
                else
                {
                    napOpen=true;
                    initTime={i,j};

                    napTimer=0;
                }
            }
            else
            {
                if (napOpen)
                {
                    napOpen=false;
                    if (napTimer>maxNapTimer)
                    {
                        maxNapTimer=napTimer;
                        maxInitTime=initTime;
                        //cout << " -> " << napTimer << endl;
                        napTimer=0;
                    }
                } else
                {
                    napTimer=0;
                }
            }

        }
    }
    if (napOpen)
    {
        napOpen=false;
        if (napTimer>maxNapTimer)
        {
            maxNapTimer=napTimer;
            maxInitTime=initTime;

            napTimer=0;
        }
    }
}

int main()
{

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

    int nTask, i, hours, minutes, kase=1;
    char maxInitTimeHourPrint[100], maxInitTimeMinutePrint[100];
    while (cin >> nTask)
    {
        getchar();
        initData();
        for (i=0 ; i<nTask ; i++)
        {
            gets(inp);
            parser(inp);
        }
        napFinder();

        maxNapTimer++;
        hours = maxNapTimer / 60;
        if (maxNapTimer%60)
            minutes = maxNapTimer%60;

        if (maxInitTime.h>9)
            sprintf(maxInitTimeHourPrint,"%d",maxInitTime.h);
        else
            sprintf(maxInitTimeHourPrint,"0%d",maxInitTime.h);
        if (maxInitTime.m>9)
            sprintf(maxInitTimeMinutePrint,"%d",maxInitTime.m);
        else
            sprintf(maxInitTimeMinutePrint,"0%d",maxInitTime.m);

        printf("Day #%d: the longest nap starts at %s:%s and will last for ",kase++,maxInitTimeHourPrint,maxInitTimeMinutePrint);
        if (maxNapTimer>=60)
            printf("%d hours and %d minutes.\n",(int)maxNapTimer/60,maxNapTimer%60);
        else
            printf("%d minutes.\n",maxNapTimer);
    }
    return 0;
}




Rap sheet

  • 5,558 hits

Follow

Get every new post delivered to your Inbox.