UVa 10986 - Sending email

/* 10986    C "Sending email" */

/* @BEGIN_OF_SOURCE_CODE */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>

#define PARENT(i) ((i)/2)     /* Parent of node i */
#define LEFT(i)      (2*(i))     /* Left child of node i */
#define RIGHT(i)  ((2*(i))+1) /* Right child of node i */

typedef int (*KEYCMP) (const void *a, const void *b);
typedef void (*DATACPY) (void *dst, const void *src);
typedef void (*DELNODE) (void *n);
typedef void (*PRINTNODE) (const void *n);

typedef struct _binary_heap {
   /* Functions to compare, print, copy, delete the elements of this heap */
   KEYCMP _keycmpfn;
   DATACPY _datacpyfn;
   DELNODE _delnodefn;
   PRINTNODE _printfn;

   char *elements; /* Dynamic array representing the binary heap */
   /* elements[] is an array of generic structures of size 'e_size' */
   size_t e_size; /* Size of one element */
   int nelements; /* Pre-allocated length of array elements[] */
   int heap_size; /* Size of the binary heap */
   int *indexOf ; /* Get the index in heap of the application object with identifier <id> */
   int *handleAt ; /* Instead of moving data in elements[], move pointers to elements[] <i> */
} BINARY_HEAP;

void heap_init(BINARY_HEAP *h, int initial_size, size_t e_size, KEYCMP k, DATACPY d, DELNODE n, PRINTNODE p);
void heap_clean(BINARY_HEAP *h);
void min_heap_insert(BINARY_HEAP *h, int id, const void * n);
void max_heap_insert(BINARY_HEAP *h, int id, const void * n);
void heap_increase_key(BINARY_HEAP *h, int id, const void * n);
void heap_decrease_key(BINARY_HEAP *h, int id, const void * n);
void heap_extract_max(BINARY_HEAP *h, void *min);
void heap_extract_min(BINARY_HEAP *h, void *min);
void heap_maximum(BINARY_HEAP *h, void *min);
void heap_minimum(BINARY_HEAP *h, void *min);
void max_heapify(BINARY_HEAP *h, int i);
void min_heapify(BINARY_HEAP *h, int i);

void heap_swap(BINARY_HEAP *h, int i, int j) {
    int t ;

    h->indexOf[h->handleAt[i]] = j ;
    h->indexOf[h->handleAt[j]] = i ;

    t = h->handleAt[i] ;
    h->handleAt[i] = h->handleAt[j] ;
    h->handleAt[j] = t ;
}

/*
Maintain the MAX-HEAP property.
 */
void max_heapify(BINARY_HEAP *h, int i) {
    register int largest, l = LEFT(i), r = RIGHT(i);

    largest = (l <= h->heap_size &&
            h->_keycmpfn(&h->elements[h->e_size * h->handleAt[l]],
            &h->elements[h->e_size * h->handleAt[i]]) > 0) ? l : i;

    largest = (r <= h->heap_size &&
            h->_keycmpfn(&h->elements[h->e_size * h->handleAt[r]],
            &h->elements[h->e_size * h->handleAt[largest]]) > 0) ? r : largest;

    if (largest != i) {
        heap_swap(h, i, largest);
        max_heapify(h, largest);
    }
}

/*
Maintain the MIN-HEAP property.
 */
void min_heapify(BINARY_HEAP *h, int i) {
    register int smallest, l = LEFT(i), r = RIGHT(i);

    smallest = (l <= h->heap_size &&
            h->_keycmpfn(&h->elements[h->e_size * h->handleAt[l]],
            &h->elements[h->e_size * h->handleAt[i]]) < 0) ? l : i;

    smallest = (r <= h->heap_size &&
            h->_keycmpfn(&h->elements[h->e_size * h->handleAt[r]],
            &h->elements[h->e_size * h->handleAt[smallest]]) < 0) ? r : smallest;

    if (smallest != i) {
        heap_swap(h, i, smallest);
        min_heapify(h, smallest);
    }
}

/*
Copies MAX element of the heap to the variable pointed by *max.
 */
void heap_maximum(BINARY_HEAP *h, void *max) {
    if (h->heap_size < 1)
        return;
    else h->_datacpyfn(&max, (void *) &h->elements[h->e_size * h->handleAt[1]]);
}

/*
Copies MIN element of the heap to the variable pointed by *min.
 */
void heap_minimum(BINARY_HEAP *h, void *min) {
    heap_maximum(h, min);
}

/*
Removes MAX element from the heap and copies it to *max.
 */
void heap_extract_max(BINARY_HEAP *h, void *min) {
    if (h->heap_size < 1)
        return;

    h->_datacpyfn(min, &h->elements[h->e_size * h->handleAt[1]]);

    h->indexOf[h->handleAt[h->heap_size]] = 1 ;
    h->indexOf[h->handleAt[1]] = 0 ;

    h->handleAt[1] = h->handleAt[h->heap_size] ;
    h->handleAt[h->heap_size] = 0 ;

    (h->heap_size)--;
    max_heapify(h, 1);
}

/*
Removes MIN element from the heap and copies it to *min.
 */
void heap_extract_min(BINARY_HEAP *h, void *min) {
    if (h->heap_size < 1)
        return;

    h->_datacpyfn(min, &h->elements[h->e_size * h->handleAt[1]]);

    h->indexOf[h->handleAt[h->heap_size]] = 1 ;
    h->indexOf[h->handleAt[1]] = 0 ;

    h->handleAt[1] = h->handleAt[h->heap_size] ;
    h->handleAt[h->heap_size] = 0 ;

    (h->heap_size)--;
    min_heapify(h, 1);
}

/*
Increases the key of an element.
 */
void heap_increase_key(BINARY_HEAP *h, int id, const void * n) {
    int i ;

    /* Get index of the element whose key is to be decreased */
    i = h->indexOf[id] ;

    if (i < 1 || i > h->heap_size)
        return;

    while (i > 1 && h->_keycmpfn(&h->elements[h->e_size * h->handleAt[PARENT(i)]], n) < 0) {
        h->indexOf[h->handleAt[PARENT(i)]] = i ;
        h->handleAt[i] = h->handleAt[PARENT(i)] ;
        i = PARENT(i) ;
    }

    h->handleAt[i] = id ;
    h->indexOf[id] = i ;
    h->_datacpyfn(&h->elements[h->e_size * id], n);
}

/*
Inserts an element in the maximum binary heap.
Additionally, Increases the size of the underlying array representing the heap if
nelements is already reached.
 */
void max_heap_insert(BINARY_HEAP *h, int id, const void * n) {
    int i = ++(h->heap_size);

    h->indexOf[id] = i ;
    heap_increase_key(h, id, n);
}

/*
 * Decreases the key of an element.
 */
void heap_decrease_key(BINARY_HEAP *h, int id, const void * n) {
    int i ;

    /* Get index of the element whose key is to be decreased */
    i = h->indexOf[id] ;

    if (i < 1 || i > h->heap_size)
        return;

    while (i > 1 && h->_keycmpfn(&h->elements[h->e_size * h->handleAt[PARENT(i)]], n) > 0) {
        h->indexOf[h->handleAt[PARENT(i)]] = i ;
        h->handleAt[i] = h->handleAt[PARENT(i)] ;
        i = PARENT(i) ;
    }

    h->handleAt[i] = id ;
    h->indexOf[id] = i ;
    h->_datacpyfn(&h->elements[h->e_size * id], n);
}

/*
Inserts an element in the minimum binary heap.
Additionally, Increases the size of the underlying array representing the heap if
nelements is already reached.
 */
void min_heap_insert(BINARY_HEAP *h, int id, const void * n) {
    int i = ++(h->heap_size);

    h->indexOf[id] = i ;
    heap_decrease_key(h, id, n);
}

/*
Cleans a HEAP, removing all the nodes.
 */
void heap_clean(BINARY_HEAP *h) {
    int i;

    if (h->elements != NULL) {
        if (h->_delnodefn)
            for (i = 1; i <= h->heap_size; i++)
                h->_delnodefn((void *)&h->elements[h->e_size * h->handleAt[i]]) ;
        free(h->elements);
        h->elements = NULL;
    }

/*
    printf("\nindex: ") ;
    for (i=1; i<=h->nelements; i++) {
        printf("%d ", h->indexOf[i]) ;
    }

    printf("\nhandle: ") ;
    for (i=1; i<=h->nelements; i++) {
        printf("%d ", h->handleAt[i]) ;
    }
*/

    h->heap_size = 0;
    h->nelements = 0;
    h->e_size = 0;
}

/*
Initializes a BINARY_HEAP
 */
void heap_init(BINARY_HEAP *h, int initial_size, size_t e_size, KEYCMP k, DATACPY d, DELNODE n, PRINTNODE p) {
    h->_keycmpfn = k;
    h->_datacpyfn = d;
    h->_delnodefn = n;
    h->_printfn = p;

    h->heap_size = 0;

    h->e_size = e_size;
    h->nelements = initial_size;

    /* Allocate nelements+1 elements because index in C starts from 1 and
     * our heap starts from 1 */
    h->elements = (char *) malloc((h->nelements+1) * h->e_size) ;

    /* An application object with identifier <id> is stored at index[id] in heap */
    h->indexOf = (int *) calloc((h->nelements + 1), sizeof(int));
    /* Index <i> in heap points to application object with identifier handle[i] */
    h->handleAt = (int *) calloc((h->nelements + 1), sizeof(int));
}

typedef struct _priority_queue {
   struct _priority_queue *THIS;
   BINARY_HEAP heap;
} PQ, *PQPTR;

void pq_init(PQ *q, size_t initial_size, size_t ele_size, KEYCMP k, DATACPY d, DELNODE n, PRINTNODE p);
void pq_enqueue(PQ *q, const void *n, int id);
void pq_dequeue(PQ *q, void *n);
void pq_peek(PQ *q, void *n);
void pq_decrease_priority(PQ *q, void *n, int id);
void pq_delete(PQ *q);
int is_pq_empty(PQ *q);

void pq_init(PQ *q, size_t initial_size, size_t e_size,
        KEYCMP k, DATACPY d, DELNODE n, PRINTNODE p) {
    q->THIS = q;
    heap_init(&(q->heap), initial_size, e_size, k, d, n, p);
}

int is_pq_empty(PQ *q) {
    return (q->heap.heap_size == 0) ? 1 : 0;
}

void pq_enqueue(PQ *q, const void *n, int id) {
    min_heap_insert(&(q->heap), id, n);
}

void pq_dequeue(PQ *q, void *min) {
    heap_extract_min(&(q->heap), min);
}

void pq_peek(PQ *q, void *min) {
    heap_minimum(&(q->heap), min);
}

void pq_delete(PQ *q) {
    heap_clean(&(q->heap));
}

void pq_decrease_priority(PQ *q, void *n, int id) {
    heap_decrease_key(&(q->heap), id, n) ;
}

enum {undirected=0, directed=1} ;

typedef int weight;

typedef struct _edge {
   int v ;                 /* adjacent node */
   weight w ;              /* cost of edge (u,v) */
   struct _edge *next ;    /* pointer to next edge */
} EDGE ;

typedef struct _graph {
   EDGE **adj ;            /* adjacency list of vertex u */
   int nvertices ;         /* number of vertices in the graph */
   int nedges ;            /* number of edge in the graph */
   short is_directed ;     /* directed or undirected */
   int *degree ;           /* degree of each vertex */
} GRAPH ;

size_t sizeof_edge ;       /* sizeof EDGE */
void graph_init(GRAPH *g, int nvertices, int nedges, short is_directed) ;
void add_edge(GRAPH *g, int u, int v, int cost) ;
void graph_display(GRAPH *g) ;
void graph_clean(GRAPH *g) ;

void graph_init(GRAPH *g, int nvertices, int nedges, short is_directed) {
    int i;

    sizeof_edge = sizeof (EDGE);

    g->nvertices = nvertices;
    g->nedges = nedges;
    g->is_directed = is_directed;

    g->adj = (EDGE **) malloc((g->nvertices+1) * sizeof (EDGE *));
    g->degree = (int *) malloc((g->nvertices+1) * sizeof (int));

    for (i = 1; i <= g->nvertices; i++) {
        g->adj[i] = NULL;
        g->degree[i] = 0;
    }
}

/*
 * Insert an edge (u,v) at the start of the list adj[u].
 * Algorithm Design Manual, Skiena., Pg 154.
 */
void __insert_edge(GRAPH *g, int u, int v, int cost, short is_directed) {
    EDGE *e;

    e = (EDGE *) malloc(sizeof_edge);
    e->w = cost;
    e->v = v;
    e->next = g->adj[u];

    g->adj[u] = e;
    g->degree[u]++;

    /* if the graph is undirected, create another edge (v,u) */
    if (!is_directed)
        __insert_edge(g, v, u, cost, directed);
}

/*
 * Insert an edge (u,v) at the start of the list adj[u].
 */
void add_edge(GRAPH *g, int u, int v, int cost) {
    __insert_edge(g, u, v, cost, g->is_directed);
}

void graph_display(GRAPH *g) {
    EDGE *e;
    int u;

    for (u = 1; u <= g->nvertices; u++) {
        printf("%d:", u);
        e = g->adj[u];
        while (e != NULL) {
            printf(" (%d,%d)", e->v, e->w);
            e = e->next;
        }
        printf("\n");
    }
}

/*
 * Destroys the graph.
 */
void graph_clean(GRAPH *g) {
    EDGE *e, *k;
    int u ;
    for (u = 1; u <= g->nvertices; u++) {
        e = g->adj[u];
        while (e != NULL) {
            k = e ;
            e = e->next;
            free(k) ;
        }
        g->adj[u] = NULL ;
    }
    if (g->adj != NULL)
        free(g->adj);
    if (g->degree != NULL)
        free(g->degree);

    g->nvertices = g->nedges = g->is_directed = 0;
}

typedef struct _vertex {
    int handle;  /* identifies the application object (vertex) in heap.
                  * index 1..nelements */
    int v ;
    int dist;
} vertex;

int d_key_cmp(const void *a, const void *b) {
    if (((vertex *) a)->dist > ((vertex *) b)->dist) return 1;
    else if (((vertex *) a)->dist < ((vertex *) b)->dist) return -1;

    return 0;
}

void d_data_copy(void *dest, const void *src) {
    vertex *n = (vertex *) dest;
    n->dist = ((vertex *) src)->dist;
    n->v = ((vertex *) src)->v;
}

/*
 * Implements Dijkstra Single-Source Shortest Path algorithm.
 * The main data structure MIN-PRIORITY-QUEUE used in this algorithm uses a
 * MIN-BINARY-HEAP.
 */
void dijkstra(GRAPH *g, int start, int dist[], int path[]) {

    PQ pq;
    EDGE *e;
    int v, u;
    vertex n;

    /* initialize single source */
    pq_init(&pq, g->nvertices, sizeof (vertex), d_key_cmp, d_data_copy, NULL, NULL);

    for (v = 1; v <= g->nvertices; v++) {
        dist[v] = 1000010;
        path[v] = -1;
        n.v = v ;
        n.dist = dist[v];
        pq_enqueue(&pq, &n, v);
    }

    dist[start] = 0;
    dist[start] = 0;
    n.v=start ;
    n.dist=0 ;
    pq_decrease_priority(&pq, &n, start);

    while (!is_pq_empty(&pq)) {
        pq_dequeue(&pq, &n);
        u = n.v ;

        e = g->adj[u]; /* for each node (u,v) */
        while (e != NULL) {
            if (dist[e->v] > dist[u] + e->w) {
                dist[e->v] = dist[u] + e->w;
                path[e->v] = u;

                n.v = e->v ;
                n.dist = dist[e->v];
                pq_decrease_priority(&pq, &n, n.v);
            }
            e = e->next;
        }
    }

    pq_delete(&pq) ;
}

int main()
{
   GRAPH g;
   int n, m, S, T, cases, k, i, u, v, w;
    int dist[20001], path[20001] ;

   #ifndef ONLINE_JUDGE
   freopen("10986.in", "r", stdin) ;
   #endif

    scanf("%d", &cases);

    k = 0;
    while (cases--) {
        k++;
        scanf("%d%d%d%d", &n, &m, &S, &T);
        graph_init(&g, n, m, undirected);
        for (i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            add_edge(&g, u+1, v+1, w);
        }

        dijkstra(&g, S+1, dist, path) ;
        if (dist[T+1]>=1000010)
            printf("Case #%d: unreachable\n", k) ;
        else
            printf("Case #%d: %d\n", k, dist[T+1]) ;
        graph_clean(&g) ;
    }

   return 0;
}

/* @END_OF_SOURCE_CODE */

UVa 10298 - Power Strings

/* 10298    C "Power Strings" */

/* @BEGIN_OF_SOURCE_CODE */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>

char s[1000010] ;
int len, half ;

int find_min_rep_substring(void)
{
   int i, j, k, min=len, f ;
   char *p ;

   for (i=half; i>=2; i--) {
      if (len%i!=0)
         continue ;

      p = s+i ;
      f = 1 ;
      /* compare k-1 substrings of length i */
      for (k=len/i, j=1; j<k; j++) {
         if (strncmp(s, p, i)!=0) {
            f = 0 ;
            break ;
         }
         p+=i ;
      }

      if (f) min = i ;
   }

   return len/min ;
}

int main()
{
   int i, j, n, k ;

   #ifndef ONLINE_JUDGE
   freopen("10298.in", "r", stdin) ;
   #endif

   while (scanf("%s", s)) {
      if (s[0]=='.' && s[1]=='\0')
         break ;

      len = strlen(s) ;
      half = len/2 ;

      for (i=0; i<half; i++)
         if (s[i]!=s[len-i-1])
            break ;

      if (i==half && s[0]==s[half]) printf("%d\n", len) ;
      /* for odd strings, largest repeating substring would be either of length 1 or len */
      else if (len%2) printf("1\n") ;
      else printf("%d\n", find_min_rep_substring()) ;
   }

   return 0;
}

/* @END_OF_SOURCE_CODE */

See also UVa 455

UVa 568 - Just the Facts

/* 568    C "Just the Facts" */

/* @BEGIN_OF_SOURCE_CODE */

#include <stdio.h>

#define FACT_UPTO 10001

int n, fact_lnzd[FACT_UPTO] ;

void precompute(void)
{
   int i, fact ;

   fact_lnzd[0] = fact_lnzd[1] = fact = 1 ;

   for (i=2; i<=FACT_UPTO; i++) {
      fact = fact * i ;
      while (fact%10==0)
         fact /= 10 ;
      fact = fact%100000 ;
      fact_lnzd[i] = fact%10 ;
   }
}

int main()
{
   precompute() ;
   while (scanf("%d", &n) != EOF)
      printf("%5d -> %d\n", n, fact_lnzd[n]) ;
   return 0;
}

/* @END_OF_SOURCE_CODE */

0-1 Knapsack Code

#define MAX_ITEMS 20
#define CAPACITY  5000

int V[MAX_ITEMS+1][CAPACITY+1], K[MAX_ITEMS+1][CAPACITY+1] ;

/* Find a solution to maximizing VALUE while subjected to a maximum WEIGHT of W */
/* values[n+1] = {0, v1, v2, ...vn} ;
   weights[n+1] = {0, w1, w2, ... wn} ;
   n = total number of items
   W = maximum capacity of the knapsack
*/
int knapsack01(int W, int n, int values[MAX_ITEMS+1], int weights[MAX_ITEMS+1])
{
   int i, j, w, t, sol[MAX_ITEMS+1] ;

   for (w=0; w<=W; w++)
      V[0][w] = 0 ;

   for (i=1; i<=n; i++) {
      for (w=0; w<=W; w++) {
         if (weights[i]<=w) {
            t = values[i] + V[i-1][w-weights[i]] ;
            if (V[i-1][w] > t) {
               V[i][w] = V[i-1][w] ;
               K[i][w] = 0 ;
            }
            else {
               V[i][w] = t ;
               K[i][w] = 1 ;
            }
         }
         else {
            V[i][w] = V[i-1][w] ;
            K[i][w] = 0 ;
         }
      }
   }

   t = W ;
   for (i=n, j=0; i>=1; i--) {
      if (K[i][t]==1) {
         sol[j++] = values[i] ;
         t = t-weights[i] ;
      }
   }

   for (--j; j>=0; j--)
      printf("%d ", sol[j]) ;

   return V[n][W] ;
}