2012年8月29日星期三

一、建立有向圖。
二、尋找所有Strongly Connected Component。
三、收縮每個Strongly Connected Component，成為有向無環圖DAG。
四、尋找縮圖的Topological Ordering。
五、在縮圖上，以Topological Ordering的反序，列出解。

* N个集团，每个集团2个人(0<=ni<2n p="p">

* 且每个集团只能选出一个人。如果两人有矛盾，他们不能同时被选中

* 问最多能选出多少人並列出

sample input:
3 4 (N M) (N組人M組條件)
1 2 (第1組)
3 4
5 6 (第3組)
1 3 (第1條件: 1不與3同時選上)
1 5
2 3
2 4

//reference: 演算法筆記 http://www.csie.ntnu.edu.tw/~u91029/SimulationModeling.html#a6
#include<stdio.h>
#include<string.h>
#include<iostream>
#define DBG 1

using namespace std;
int visit[20],map[20][20];
int sat[20];        
int finish[20], scc[20], n, N;
int f[20],x[20],y[20];

void DFS1(int i)
{
    visit[i] = true;
    for (int j=0; j<N+N; ++j)
        if (map[i][j] && !visit[j])
            DFS1(j);
    finish[n++] = i;
}
void DFS2(int i)
{
    scc[i] = n;
    if(DBG)printf("scc[%d]=%d\n",i+1,n);
    visit[i] = true;
    for (int j=0; j<N+N; ++j)
        if (map[j][i] && !visit[j]){
            DFS2(j);
        }
}
void two_satisfiability()
{
    n = 0;  // 時刻
    memset(visit, false, sizeof(visit));
    for (int i=0; i<N; ++i)
        if (!visit[i])
            DFS1(i);
            
    memset(visit, false, sizeof(visit));
    for (int k=N-1; k>=0; --k)
    {
        
        int i = finish[k];
        if (!visit[i])
            DFS2(i), n++;
    }
    // 檢查是否有解，無解則立即結束。
    for (int i=0; i<N; ++i)
        if (scc[i] == scc[f[i]])
            return;

    // 找出一組解
    memset(sat, 0, sizeof(sat));
    for (int k=0; k<N; ++k)
    {
        int i = finish[k];
        if (!sat[scc[i]])
        {
            sat[scc[i]] = 1;
            sat[scc[f[i]]] = 2;
        }
    }
    // 印出一組解
    for (int i=0; i<N; ++i)
        if (sat[scc[i]] == 1)
            cout << i+1 <<endl;
}

int main(){
    int m;
    while (scanf("%d%d",&N,&m)!=EOF && N+m){
        int p,q;
        for (int i=0;i<N;i++){
            scanf("%d%d",&p,&q),p--,q--;
            f[p]=q,f[q]=p;
        }
        for (int i=0;i<m;i++) scanf("%d%d",&p,&q),p--,q--,x[i]=p,y[i]=q;
        for (int i=0;i<m;i++){
            map[x[i]][f[y[i]]]=map[y[i]][f[x[i]]]=1;
        }
        N*=2;
        two_satisfiability();
    }
    return 0;
}

2012年8月28日星期二

SCC (Strong Connected Component) Tarjan解

Strongly Connected Component 


在無向圖當中，只要邊邊相連，即形成連通，不必在意方向。在有向圖當中，由於有了方向限制，因此細分為「強連通」和「弱連通」：所有兩點之間，雙向都有路可通，則是「強連通」；所有兩點之間，至少單向有路可通，則是「弱連通」。

一張有向圖的「強連通分量」，是所有兩點之間，雙向皆有路可通的連通分量。一張有向圖的強連通分量們，不可能互相重疊。

Tarjan解 - DFS紀錄當前節點所連接到最高的祖先，有環則輸出整個環，無環則個別為一個Component

//reference: ACM/ICPC代碼庫  http://ir.hit.edu.cn/~lfwang/docs/MyLib(For%20ACM).pdf
#include<stdio.h>
#include<vector>
#define V 100
#define DBG 0

using namespace std;

vector<int> vec[V];
int id[V], pre[V], low[V], s[V], stop, cnt, scnt;
void tarjan(int v, int n) // vertex: 0 ~ n-1
{
    int t, minc = low[v] = pre[v] = cnt++;
    vector<int>::iterator pv;
    s[stop++] = v;
    for (pv = vec[v].begin(); pv != vec[v].end(); ++pv) {
        if(-1 == pre[*pv]) tarjan(*pv, n);
        if(low[*pv] < minc) minc=low[*pv];
    }
    if(minc < low[v]) {
        low[v] = minc; return;
    }
    do {
        id[t = s[--stop]] = scnt; low[t] = n;
    } while(t != v);
    ++scnt;
}
int main(){
    int a,b,n,m,i;
    memset(pre,-1,sizeof(pre));
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)scanf("%d%d",&a,&b),a--,b--,vec[a].push_back(b);
    for(i=0; i<n; ++i) if(-1==pre[i]) tarjan(i, n);
    printf("scc: %d\n",scnt);
}

2012年8月24日星期五

最大團問題- Clique

wikepedia
團（clique）是圖論中的用語。對於給定圖G=(V,E)。其中，V={1,…,n}是圖G的頂點集，E是圖G的邊集。圖G的團就是一個兩兩之間有邊的頂點集合。如果一個團不被其他任一團所包含，即它不是其他任一團的真子集，則稱該團為圖G的極大團（maximal clique）。頂點最多的極大團，稱之為圖G的最大團（maximum clique）。最大團問題的目標就是要找到給定圖的最大團。
dynamic programming解:

//reference: ACM/ICPC代碼庫  http://ir.hit.edu.cn/~lfwang/docs/MyLib(For%20ACM).pdf
#include<stdio.h>
#include<iostream>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define V 100               //maximum point

using namespace std;

int g[V][V], dp[V], stk[V][V], mx;
int dfs(int n, int ns, int dep){
    if (0 == ns) {
        if (dep > mx) mx = dep;
        return 1;
    }
    int i, j, k, p, cnt;
    for (i = 0; i < ns; i++) {
        k = stk[dep][i]; cnt = 0;
        //if (dep + n - k <= mx) return 0;
        if (dep + dp[k] <= mx) return 0;
        for (j = i + 1; j < ns; j++) {
            p = stk[dep][j];
            if (g[k][p]) stk[dep + 1][cnt++] = p;
        }
        dfs(n, cnt, dep + 1);
    }
    return 1;
}
int clique(int n){
    int i, j, ns;
        for (mx = 0, i = n - 1; i >= 0; i--) {
        // vertex: 0 ~ n-1
            for (ns = 0, j = i + 1; j < n; j++)
                if (g[i][j]) stk[1][ ns++ ] = j;
            dfs(n, ns, 1);
            dp[i] = mx;
        }
    return mx;
}
int main(){
    int N,M,a,b,res;        //N是點數，M是邊數
    cin>>N>>M;              
    for(int i=0;i<b;i++)cin>>a>>b,g[a][b]=1,g[b][a]=1;
    res=clique(N);
    printf("%d\n",res);
}

2012年8月17日星期五

比較高效的大數運算

10000進位大數


//source: ACM/ICPC代碼庫  http://ir.hit.edu.cn/~lfwang/docs/MyLib(For%20ACM).pdf
#include<stdio.h>
#include<string.h>

const int base = 10000; // (base^2) fit into int
const int width = 4; // width = log base
const int N = 1000; // n * width: 
struct bint{
    int ln, v[N];
    bint (int r = 0) {  //to use string use read
        for (ln = 0; r > 0; r /= base) v[ln++] = r % base;
    }
    bint& operator = (const bint& r) {
        memcpy(this, &r, (r.ln + 1) * sizeof(int));// !
        return *this;
    }
};
bool operator < (const bint& a, const bint& b){
    int i;
    if (a.ln != b.ln) return a.ln < b.ln;
    for (i = a.ln - 1; i >= 0 && a.v[i] == b.v[i]; i--);
    return i < 0 ? 0 : a.v[i] < b.v[i];
}
bool operator <= (const bint& a, const bint& b){
    return !(b < a);
}
bint operator + (const bint& a, const bint& b){
    bint res; int i, cy = 0;
    for (i = 0; i < a.ln || i < b.ln || cy > 0; i++) {
        if (i < a.ln) cy += a.v[i];
        if (i < b.ln) cy += b.v[i];
        res.v[i] = cy % base; cy /= base;
    }
    res.ln = i;
    return res;
}
bint operator - (const bint& a, const bint& b){
    bint res; int i, cy = 0;
    for (res.ln = a.ln, i = 0; i < res.ln; i++) {
        res.v[i] = a.v[i] - cy;
        if (i < b.ln) res.v[i] -= b.v[i];
        if (res.v[i] < 0) cy = 1, res.v[i] += base;
        else cy = 0;
    }
    while (res.ln > 0 && res.v[res.ln - 1] == 0) res.ln--;
    return res;
}
bint operator * (const bint& a, const bint& b){
    bint res; res.ln = 0;
    if (0 == b.ln) { res.v[0] = 0; return res; }
    int i, j, cy;
    for (i = 0; i < a.ln; i++) {
        for (j=cy=0; j < b.ln || cy > 0; j++, cy/= base) {
            if (j < b.ln) cy += a.v[i] * b.v[j];
            if (i + j < res.ln) cy += res.v[i + j];
            if (i + j >= res.ln) res.v[res.ln++] = cy % base;
            else res.v[i + j] = cy % base;
        }
    }
    return res;
}
bint operator / (const bint& a, const bint& b)
{
    bint tmp, mod, res;
    int i, lf, rg, mid;
    mod.v[0] = mod.ln = 0;
    for (i = a.ln - 1; i >= 0; i--) {
        mod = mod * base + a.v[i];
        for (lf = 0, rg = base -1; lf < rg; ) {
            mid = (lf + rg + 1) / 2;
            if (b * mid <= mod) lf = mid;
            else rg = mid - 1;
        }
        res.v[i] = lf;
        mod = mod - b * lf;
    }
    res.ln = a.ln;
    while (res.ln > 0 && res.v[res.ln - 1] == 0) res.ln--;
    return res; // return mod 就是%運算
}
int digits(bint& a) // 返回位數
{
    if (a.ln == 0) return 0;
    int l = ( a.ln - 1 ) * 4;
    for (int t = a.v[a.ln - 1]; t; ++l, t/=10) ;
    return l;
}
bool read(char s[],bint& b, char buf[]) //
{
    if (1 != sscanf(s,"%s", buf)) return 0;
    printf("buf: %s\n",buf);
    int w, u, ln = strlen(buf);
    memset(&b, 0, sizeof(bint));
    if ('0' == buf[0] && 0 == buf[1]) return 1;
    for (w = 1, u = 0; ln; ) {
        u += (buf[--ln] - '0') * w;
        if (w * 10 == base) {w=1, b.v[b.ln++] = u,u=0;}
        else w *= 10;
    }
    if (w != 1) b.v[b.ln++] = u;
    return 1;
}
void write(const bint& v){
    int i;
    printf("%d", v.ln == 0 ? 0 : v.v[v.ln - 1]);
    for (i = v.ln - 2; i >= 0; i--)
    printf("%04d", v.v[i]); // ! 4 == width
    printf("\n");
}
int main(){
    char s1[]="12345678901234567890",
         s2[]="1234567890123456789",buf[100];
    bint bn1,bn2;
    read(s1,bn1,buf);
    read(s2,bn2,buf);
    write(bn1);
    write(bn2);
    bint bn3 = bn1*bn2;
    printf("bn3 = ");
    write(bn3);
}

RMQ - Region Minimum Query

演算法筆記- Region Minimum Query -
complexity: nlgn

#include<stdio.h>
#include<stdlib.h>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define N 100

//RMQ離線算法 O(N*logN)+O(1)
// INIT: val[]為待查詢數組,  initrmq(n);
int st[20][N], val[N];
int min(int a,int b){return a<b?a:b;}
void initrmq(int n){
    int i, j, k, sk;
    for (i = 0; i < n; i++) st[0][i] = val[i];
    for (i = 1, k = 2; k < n; i++, k <<= 1) {
        for (j = 0, sk = (k >> 1); j+k-1 < n; ++j, ++sk)
            st[i][j] = min(st[i-1][j],st[i-1][sk]);
    }
}
int query(int x, int y) // min of { val[x] ... val[y] }
{
    int bl = 31-__builtin_clz(y-x+1);
    return min(st[bl][x], st[bl][y-(1<<bl)+1]);
}
int main(){
    rep(i,N)val[i]=i;
    initrmq(N);
    rep(i,20){
        int c=rand()%60,d=rand()%100;
        while(d<c)d=rand()%100;
        printf("(%d %d): %d\n",c,d,query(c,d));
    }
}

suffix array - 使用倍增算法

演算法筆記-String Matching

suffix array ( 後綴陣列 )

使用倍增算法(Prefix Doubling)构造后缀数组

如果采用对每个后缀排序的方法来生成后缀数组，即使采用快速排序，由于每次比较的对象是字符串（设输入字符串的长度为n），因此每一个比较操作的复杂度不再是常数，而是O(n)，快速排序本身的平均情况下时间复杂度为O(nlgn)，因此总的时间复杂度是O(n^2*lgn)，如果考虑到采用快速排序最坏情况下复杂度为O(n^2)，那么最坏时总的复杂度为O(n^3)，显然在输入串长度很大时这种做法不可取。

Prefix Doubling算法（倍增法）是构造后缀数组一个比较实用的算法。其基本思想是先计算出每个后缀的k-前缀的rank值，然后在此基础上计算每个后缀的2k-前缀rank值，k从1开始。直到每个后缀都排出先后顺序为止（任何两个后缀都不会相等，换句话说，每个后缀终究都能排出先后顺序）。在处理2k-前缀时，只需要使用基数排序（radix sort）算法，先后对两位数字排序（可以采用计数排序算法(counting sort)对每一位数字排序）。在最坏情况下，需要做lgn次基数排序，每一次基数排序的操作次数为2*O(n)，因此它的时间复杂度是O(nlgn)。倍增法虽然没有达到像DC3算法的线性复杂度，但是它的优点是实现比较简单，因此在实践中常被采用。

在以下实现中，当k=1时，由于只需要对输入串的每个字符排序，因此在采用基数排序时，只有一位数字需要排序。当k>1时，需要对两位数字排序（为考虑通用性，代码中Tuple.digits数组长度可以取>=1的任何整数，而不限于两位数字的基数排序）。如果rank数组中某个后缀具有最大rank值，而且该rank值等于输入串的长度，这时说明每一个后缀都排出了次序，因而可以提前终止程序。另外，假设字母表中最大的字符为MAX_CHAR。

注：rank数组中的rank值对应SA数组的下标+1。例如T=mississippi#,那么SA=(11,10,7,4,1,0,9,8,6,3,5,2),这里第7个后缀（即ippi$）在SA数组中的下标是2，因此Rank[7]=3。


//reference: ACM/ICPC代碼庫  http://ir.hit.edu.cn/~lfwang/docs/MyLib(For%20ACM).pdf
#include<stdio.h>
#include<string>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
#define N 512
using namespace std;
//////////////////////////////////////////////////////
// 后綴數組 O(N * log N), prefix doubling algorithm
// INIT: n = strlen(s) + 1;    (利用\0作為分隔符號)
// CALL: makesa(); lcp();
//////////////////////////////////////////////////////

//////////////////////////////////////////////////////
//sa: suffix array
//height: LCP value
//rank: sa之反函數，i,e., sa[rank[i]]= i
//tmp: 暫存最新之sa
//top: top[i]在迴圈中表示目前計算中排序第i名之字串前方(第1~i-1名)共有幾個字串
//////////////////////////////////////////////////////
int n,sa[N], height[N], rank[N], tmp[N], top[N];
char s[N];      // N > 256
void makesa(){  // O(N * log N)
    int i, j, len, na;
    na = (n < 256 ? 256 : n);
    memset(top, 0, na * sizeof(int));
    for (i = 0; i < n ; i++) top[ rank[i] = s[i]]++;
    for (i = 1; i < na; i++) top[i] += top[i - 1];          //counting sort
    for (i = 0; i < n ; i++) sa[ --top[ rank[i] ] ] = i;
    for (len = 1; len < n; len <<= 1) {             //len每次乘2
        if(DBG){rep(k,n)printf("%d ",sa[k]);printf("\n");}
        for (i = 0; i < n; i++) {                   //計算最新之sa, radix sort
            j = sa[i] - len;
            if(DBG)printf("j= %d - %d = %d(%d)\n",sa[i],len,j,j<0?j+n:j);
            if (j < 0) j += n;
            tmp[ top[ rank[j] ]++ ] = j;
            if(DBG)printf("tmp[%d]=%d\n",top[ rank[j] ]-1,j);
        }
        //此處sa被拿來暫存新的rank
        sa[ tmp[ top[0] = 0 ] ] = j = 0;
        for (i = 1; i < n; i++) {                   //計算top和rank
            if (rank[ tmp[i] ] != rank[ tmp[i-1] ] || rank[ tmp[i]+len ]!=rank[ tmp[i-1]+len ])
                top[++j] = i;
            sa[ tmp[i] ] = j;
        }
        if(DBG)printf("j= %d\n",j);
        memcpy(rank, sa , n * sizeof(int));
        memcpy(sa , tmp, n * sizeof(int));
        if (j >= n - 1) break;
    }
}
//lcp: 計算從每個字串之LCP (from s[0] to s[n-1])
//note: rank[0]>0, 因sa[0]=n (\0)
void lcp(){ // O(4 * N)
    int i, j, k;
    for (j = rank[height[i=k=0]=0]; i < n - 1; i++, k++){
        while (k >= 0 && s[i] != s[ sa[j-1] + k ]){
            height[j] = (k--), j = rank[ sa[j] + 1 ];
        }
    }
}
int main(){
    bool ll=0;
    char arr[5][100]={"ttttttt", "mississippi#", "abcdefghijklmmnopqrstuvwxyz#",
        "yabbadabbado#", "DFDLKJLJldfasdlfjasdfkldjasfldafjdajfdsfjalkdsfaewefsdafdsfa#"
        };
    rep(i,5){
        strcpy(s,arr[i]);
        n=strlen(s)+1;              //+1!
        if(ll)printf("********************************\n");ll=1;
        printf("Text: %s\n",s);
        makesa();
        lcp();
        printf("suffix array: \n");
        rep(i,n)printf(" %d",sa[i]);printf("\n");
        printf("rank array: \n");
        rep(i,n)printf(" %d",rank[i]+1);printf("\n");
        //printf("lcp: ");
        //rep(i,n)printf("%d ",height[i]);printf("\n");
    }
}

2012年8月15日星期三

左偏樹

图解数据结构（9）——左偏树

十三、左偏树（Leftist Tree）
树这个数据结构内容真的很多，上一节所讲的二叉堆，其实就是一颗二叉树，这次讲的左偏树（又叫“左翼堆”），也是树。
二叉堆是个很不错的数据结构，因为它非常便于理解，而且仅仅用了一个数组，不会造成额外空间的浪费，但它有个缺点，那就是很难合并两个二叉堆，对于“合并”，“拆分”这种操作，我觉得最方面的还是依靠指针，改变一下指针的值就可以实现，要是涉及到元素的移动，那就复杂一些了。
左偏树跟二叉堆比起来，就是一棵真正意义上的树了，具有左右指针，所以空间开销上稍微大一点，但却带来了便于合并的便利。BTW：写了很多很多的程序之后，我发觉“空间换时间”始终是个应该考虑的编程方法。:)
左偏左偏，给人感觉就是左子树的比重比较大了，事实上也差不多，可以这么理解：左边分量重，那一直往右，就一定能最快地找到可以插入元素的节点了。所以可以这样下个定义：左偏树就是对其任意子树而言，往右到插入点的距离（下面简称为“距离”）始终小于等于往左到插入点的距离，当然了，和二叉堆一样，父节点的值要小于左右子节点的值。


//reference: ACM/ICPC代碼庫  http://ir.hit.edu.cn/~lfwang/docs/MyLib(For%20ACM).pdf
#include<stdio.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

#define N 100

using namespace std;

#define typec int // type of key val
const int na = -1;
struct node { typec key; int l, r, f, dist; } tr[N];
int iroot(int i){ // find i's root
    if (i == na) return i;
    while (tr[i].f != na) i = tr[i].f;
    return i;
}
int merge(int rx, int ry){ // two root: rx, ry
    if (rx == na) return ry;
    if (ry == na) return rx;
    if(DBG)printf("merge %d %d\n",rx,ry);
    if (tr[rx].key > tr[ry].key)swap(rx, ry);
    int r = merge(tr[rx].r, ry);
    tr[rx].r = r; tr[r].f = rx;
    if (tr[r].dist > tr[tr[rx].l].dist)
    swap(tr[rx].l, tr[rx].r);
    if (tr[rx].r == na) tr[rx].dist = 0;
    else tr[rx].dist = tr[tr[rx].r].dist + 1;
    if(DBG)printf("root %d(%d)\n",rx,tr[rx].key);
    return rx; // return new root
}
int del(int i) { // delete node i
    if (i == na) return i;
    int x, y, l, r;
    l = tr[i].l; r = tr[i].r; y = tr[i].f;
    tr[i].l = tr[i].r = tr[i].f = na;
    tr[x = merge(l, r)].f = y;
    if (y != na && tr[y].l == i) tr[y].l = x;
    if (y != na && tr[y].r == i) tr[y].r = x;
    for ( ; y != na; x = y, y = tr[y].f) {
        if (tr[tr[y].l].dist < tr[tr[y].r].dist)
        swap(tr[y].l, tr[y].r);
        if (tr[tr[y].r].dist + 1 == tr[y].dist) break;
        tr[y].dist = tr[tr[y].r].dist + 1;
        }
        if (x != na) return iroot(x); // return new root
        else return iroot(y);
    }
node top(int root){
    return tr[root];
}
node pop(int &root){
    node out = tr[root];
    int l = tr[root].l, r = tr[root].r;
    tr[root].l = tr[root].r = tr[root].f = na;
    tr[l].f = tr[r].f = na;
    root = merge(l, r);
    return out;
}
int ins(int i, typec key, int &root){ // add a new node(i, key)
    tr[i].key = key;
    tr[i].l = tr[i].r = tr[i].f = na;
    tr[i].dist = 0;
    if(DBG)printf("ins %d %d\n",i,key);
    return root = merge(root, i); // return new root
}
int add(int i, typec val) // tr[i].key += val
{
    if (i == na) return i;
    if (tr[i].l == na && tr[i].r == na && tr[i].f == na) {
        tr[i].key += val;
        return i;
    }
    typec key = tr[i].key + val;
    int rt = del(i);
    return ins(i, key, rt);
}
void init(int n){
    for (int i = 1; i <= n; i++) {
        scanf("%d", &tr[i].key); //%d: type of key
        tr[i].l = tr[i].r = tr[i].f = na;
        tr[i].dist = 0;
    }
    if(DBG)printf("end of init\n");
}
int main(){
    int root=1;
    node n;
    init(1);
    REP(i,2,11)ins(i,i,root);
    rep(i,10)printf("pop %d\n",pop(root).key);
}

中國餘數定理

wiki

在中國古代著名數學著作《孫子算經》卷下第28题，叫做“物不知數”，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。

克罗内克符号

为了便于表述，对任意的正整数 $\mathbf{i,j}$ 用一个常用函数 $\zeta_{i,j}$ 表示，称之为克罗内克符号(Kronecker).定义：

$\zeta_{i,j} =\begin{cases} 1, \; i=j \\ 0, \; i \ne j \end{cases}$

使用该符号，即可给出上述一般同餘方程组的求解过程，分两步完成

对每个 $1 \le i \le k$ ，先求出正整数 $b_i$ 满足 $b_i \equiv \zeta_{i,j} \pmod {m_j}$ ，即所求的 $b_i$ 满足条件： $b_i \equiv 1 \pmod {m_i}$ ，但被每个 $m_j(i\ne j)$ 整除。其求法如下：记 $r_i =m_{1} \cdots m_{i-1} m_{i+1} \cdots m_k$ ，根据条件 $m_1 ,\cdots,m_k$ 两两互素，可知 $r_i$ 和 $m_i$ 也互素，故存在整数 $c_i$ 和 $d_i$ 使得 $r_i c_i + m_i d_i=1$ .令 $b_i = r_i c_i$ ，则对每个 $i \ne j$ ，相对应的 $m_j$ 显然整除 $b_i$ ，并且 $b_i \equiv 1 \pmod {m_i}$ 。由此表明 $b_i$ 即为所求。
对于前述所求的 $b_i$ ，令 $x_0 = \sum_{i=1}^k a_ib_i$ ，则 $x_0 \equiv a_i b_i \equiv a_i \pmod {m_i}$ ，这说明 $x_0$ 为上述同餘方程组的一个解，从而所有的解可表示为 $x = x_0 + n \prod_{i=1}^k m_i$ ，其中的n可以取遍所有的整数。

#include<stdio.h>
#define DBG 1

int w[3],b[3];
int extgcd(int a, int b, int & x, int & y){
    if (b == 0) { x=1; y=0; return a; }
    int d = extgcd(b, a % b, x, y);
    int t = x; x = y; y = t - a / b * y;
    return d;
}
int china(int k){
    int i, d, x, y, m, a = 0, n = 1;
    for (i = 0; i < k; i++) n *= w[i];
    for (i = 0; i < k; i++) {
        m = n / w[i];
        d = extgcd(w[i], m, x, y);
        a += (y * m * b[i]) % n;
        if(DBG)printf("a y m b %d %d %d %d\n",a,y,m,b[i]);
    }
    if (a > 0) return a;
    else return (a + n);
}
int main(){
    w[0]=3,w[1]=5,w[2]=7,b[0]=0,b[1]=3,b[2]=4;
    int ans = china(2);
    printf("ans: %d\n",ans);
}

質數測試算法(基于Miller-Rabin的MC算法)

素數測試算法(基于Miller-Rabin的MC算法)
wiki

強偽素數
設n是一個大于4的奇整數，s和t是使得(n-1)=2^s*t的正整數，其中t為奇數，設B(n)是如下定義的整數集合：
a屬于集合B(n)當且僅當2≤a≤n-2且
1: a^tmodn=1
2: 存在整數i，0<=i<s滿足a^((2^i)*t) mod n=n-1
當n為素數時，任意a在2和n-1中，均有a屬于集合B(n)
當n為合數時，若a屬于集合B(n)，則稱n為一個以a為底(基)的強偽素數，稱a為n素性的強偽證據。
n為素數，說明它對所有底均為強偽素數

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

bool witness(int a,int n){
    int t=n-1,s=0,x=1;
    while(t%2==0)s++,t/=2;
    rep(i,t)x=(x*a)%n;
    if(x==n-1||x==1)return 0;
    rep(i,s-1){
        x=(x*x)%n;
        if(x==1)return 1;
        if(x==n-1)return 0;
    }
    return 1;
}
bool miller(int n,int s){
    if(n==2)return 1;
    if(n%2==0)return 0;
    rep(i,s){
        int a=rand()*(n-2)/RAND_MAX+1;
        if(witness(a,n))return 0;
    }
    return 1;
}
int main(){
    float t1,t2;
    REP(i,2,10001){
        if(miller(i,10))printf("%d\n",i);
    }
    t1 = clock();
    printf("time: (%f seconds)\n",(t1)/CLOCKS_PER_SEC);
}

2012年8月14日星期二

uva 10258 - Contest Scoreboard

Question B - Contest Scoreboard

Think the contest score boards are wrong? Here's your chance to come up with the right rankings.

Contestants are ranked first by the number of problems solved (the more the better), then by decreasing amounts of penalty time. If two or more contestants are tied in both problems solved and penalty time, they are displayed in order of increasing team numbers.
A problem is considered solved by a contestant if any of the submissions for that problem was judged correct. Penalty time is computed as the number of minutes it took for the first correct submission for a problem to be received plus 20 minutes for each incorrect submission received prior to the correct solution. Unsolved problems incur no time penalties.

Input:

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Input consists of a snapshot of the judging queue, containing entries from some or all of contestants 1 through 100 solving problems 1 through 9. Each line of input will consist of three numbers and a letter in the format
contestant problem time L
where L can be C, I, R, U or E. These stand for Correct, Incorrect, clarification Request, Unjudged and Erroneous submission. The last three cases do not affect scoring.
Lines of input are in the order in which submissions were received.

Output:

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Output will consist of a scoreboard sorted as previously described. Each line of output will contain a contestant number, the number of problems solved by the contestant and the time penalty accumulated by the contestant. Since not all of contestants 1-100 are actually participating, display only the contestants that have made a submission.

Sample Input:

Sample Output:

1 2 66
3 1 11

sorting

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

struct Team{
    Team(int a):no(a){solve=pnt=0;}
    int solve,pnt,no;
};
vector<Team>tv;
bool comp(Team a,Team b){
    if(a.solve!=b.solve)return a.solve>b.solve;
    if(a.pnt!=b.pnt)return a.pnt<b.pnt;
    return a.no<b.no;
}
void ans(){
    sort(tv.begin(),tv.end(),comp);
    rep(i,tv.size()){
        printf("%d %d %d\n",tv[i].no,tv[i].solve,tv[i].pnt);
    }
}
int main(){
    int a,b,c,d;
    char nds[100];
    string type;
    stringstream buf;
    bool ll=0,solved[100][10],submit[100];
    int tm[100],pnts[100][10];
    scanf("%d ",&a);
    rep(i,a){
        memset(solved,0,sizeof(solved));
        memset(submit,0,sizeof(submit));
        memset(pnts,0,sizeof(pnts));
        tv.clear();
        while(fgets(nds,100,stdin)){
            if(nds[0]=='\n')break;
            if(nds[strlen(nds)-1]=='\n')nds[strlen(nds)-1]='\0';
            buf.clear(),buf.str(nds);
            buf>>b>>c>>d>>type;
            if(DBG)printf("type: %d %d %d %s\n",b,c,d,type.c_str());
            b--;
            if(!submit[b])tm[b]=tv.size(),tv.push_back(Team(b+1)),submit[b]=1;
            if(type[0]=='C'&&!solved[b][c])solved[b][c]=1,tv[tm[b]].pnt+=d,tv[tm[b]].solve++,
                    tv[tm[b]].pnt+=pnts[b][c];
            if(type[0]=='I'&&!solved[b][c])pnts[b][c]+=20;
        }
        if(ll)printf("\n");ll=1;
        ans();
    }
}

uva 10194 - Football (aka Soccer)

Problem A: Football (aka Soccer)

The Problem

Football the most popular sport in the world (americans insist to call it "Soccer", but we will call it "Football"). As everyone knows, Brasil is the country that have most World Cup titles (four of them: 1958, 1962, 1970 and 1994). As our national tournament have many teams (and even regional tournaments have many teams also) it's a very hard task to keep track of standings with so many teams and games played!
So, your task is quite simple: write a program that receives the tournament name, team names and games played and outputs the tournament standings so far.
A team wins a game if it scores more goals than its oponent. Obviously, a team loses a game if it scores less goals. When both teams score the same number of goals, we call it a tie. A team earns 3 points for each win, 1 point for each tie and 0 point for each loss.
Teams are ranked according to these rules (in this order):

Most points earned.
Most wins.
Most goal difference (i.e. goals scored - goals against)
Most goals scored.
Less games played.
Lexicographic order.

The Input

The first line of input will be an integer N in a line alone (0 < N < 1000). Then, will follow N tournament descriptions. Each one begins with the tournament name, on a single line. Tournament names can have any letter, digits, spaces etc. Tournament names will have length of at most 100. Then, in the next line, there will be a number T (1 < T <= 30), which stands for the number of teams participating on this tournament. Then will follow T lines, each one containing one team name. Team names may have any character that have ASCII code greater than or equal to 32 (space), except for '#' and '@' characters, which will never appear in team names. No team name will have more than 30 characters.
Following to team names, there will be a non-negative integer G on a single line which stands for the number of games already played on this tournament. G will be no greater than 1000. Then, G lines will follow with the results of games played. They will follow this format:

team_name_1#goals1@goals2#team_name_2

For instance, the following line:

Team A#3@1#Team B

Means that in a game between Team A and Team B, Team A scored 3 goals and Team B scored 1. All goals will be non-negative integers less than 20. You may assume that there will not be inexistent team names (i.e. all team names that appear on game results will have apperead on the team names section) and that no team will play against itself.

The Output

For each tournament, you must output the tournament name in a single line. In the next T lines you must output the standings, according to the rules above. Notice that should the tie-breaker be the lexographic order, it must be done case insenstive. The output format for each line is shown bellow:

[a]) Team_name [b]p, [c]g ([d]-[e]-[f]), [g]gd ([h]-[i])

Where:

[a] = team rank
[b] = total points earned
[c] = games played
[d] = wins
[e] = ties
[f] = losses
[g] = goal difference
[h] = goals scored
[i] = goals against

There must be a single blank space between fields and a single blank line between output sets. See the sample output for examples.

Sample Input

2
World Cup 1998 - Group A
4
Brazil
Norway
Morocco
Scotland
6
Brazil#2@1#Scotland
Norway#2@2#Morocco
Scotland#1@1#Norway
Brazil#3@0#Morocco
Morocco#3@0#Scotland
Brazil#1@2#Norway
Some strange tournament
5
Team A
Team B
Team C
Team D
Team E
5
Team A#1@1#Team B
Team A#2@2#Team C
Team A#0@0#Team D
Team E#2@1#Team C
Team E#1@2#Team D

Sample Output

World Cup 1998 - Group A
1) Brazil 6p, 3g (2-0-1), 3gd (6-3)
2) Norway 5p, 3g (1-2-0), 1gd (5-4) 
3) Morocco 4p, 3g (1-1-1), 0gd (5-5)
4) Scotland 1p, 3g (0-1-2), -4gd (2-6)

Some strange tournament
1) Team D 4p, 2g (1-1-0), 1gd (2-1)
2) Team E 3p, 2g (1-0-1), 0gd (3-3)
3) Team A 3p, 3g (0-3-0), 0gd (3-3)
4) Team B 1p, 1g (0-1-0), 0gd (1-1)
5) Team C 1p, 2g (0-1-1), -1gd (3-4)

sorting, notice 'case insensitive'

useful scanf method:

scanf ("%[^#]#%d@%d#%[^\n]\n", team1, &goalsForTeam1, &goalsForTeam2, team2);


#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

string lower(string s){
    rep(i,s.size())s[i]=tolower(s[i]);
    return s;
}
struct Team{
    Team(string a):name(a){name2=lower(name),win=lose=pts=tie=games=gd=gd1=gd2=0;}
    string name,name2;
    int win,lose,tie, pts,games, gd, gd1,gd2;
};
map<string,int>mp;
vector<Team>tv;
bool comp(Team a,Team b){
    if(a.pts!=b.pts)return a.pts>b.pts;
    if(a.win!=b.win)return a.win>b.win;
    if(a.gd!=b.gd)return a.gd>b.gd;
    if(a.gd1!=b.gd1)return a.gd1>b.gd1;
    if(a.games!=b.games)return a.games<b.games;
    return a.name2<b.name2;
}
void ans(){
    sort(tv.begin(),tv.end(),comp);
    rep(i,tv.size())
    printf("%d) %s %dp, %dg (%d-%d-%d), %dgd (%d-%d)\n",i+1,tv[i].name.c_str(),tv[i].pts,
        tv[i].games,tv[i].win,tv[i].tie,tv[i].lose,tv[i].gd,tv[i].gd1,tv[i].gd2);
}
int main(){
    int a,b,c,i1,i2,r1,r2,tmp;
    char nds[105];
    string ts;
    bool ll=0;
    scanf("%d ",&a);
    rep(i,a){
        tv.clear(),mp.clear(),c=0;
        scanf("%[^\n]\n",nds);
        ts=nds;
        scanf("%d ",&b);
        rep(i,b){
            scanf("%[^\n]\n",nds);
            mp[nds]=c++;
            tv.push_back(Team(nds));
            if(DBG)printf("team %s\n",nds);
        }
        scanf("%d ",&b);
        rep(i,b){
            char t1[35],t2[35];
            int n1,n2;
            scanf("%[^#]#%d@%d#%[^\n]\n", t1, &n1, &n2, t2);
            if(DBG){printf("%s %d:%d %s\n",t1,n1,n2,t2);}
            r1=mp[t1],r2=mp[t2];
            if(n1!=n2){
                if(n1<n2){tmp=r1,r1=r2,r2=tmp,tmp=n1,n1=n2,n2=tmp;}
                tv[r1].win++,tv[r1].gd+=n1-n2,tv[r1].gd1+=n1,tv[r1].gd2+=n2,tv[r1].pts+=3;
                tv[r2].lose++,tv[r2].gd+=n2-n1,tv[r2].gd1+=n2,tv[r2].gd2+=n1;
            }else{
                tv[r1].tie++,tv[r1].gd1+=n1,tv[r1].gd2+=n2,tv[r1].pts+=1;
                tv[r2].tie++,tv[r2].gd1+=n2,tv[r2].gd2+=n1,tv[r2].pts+=1;
            }
            tv[r1].games++,tv[r2].games++;
        }
        scanf(" ");
        if(ll)printf("\n");ll=1;
        printf("%s\n",ts.c_str());
        ans();
    }
}

uva 10152 - ShellSort

Problem D: ShellSort

He made each turtle stand on another one's back
And he piled them all up in a nine-turtle stack.
And then Yertle climbed up. He sat down on the pile.
What a wonderful view! He could see 'most a mile!

The Problem

King Yertle wishes to rearrange his turtle throne to place his highest-ranking nobles and closest advisors nearer to the top. A single operation is available to change the order of the turtles in the stack: a turtle can crawl out of its position in the stack and climb up over the other turtles to sit on the top.
Given an original ordering of a turtle stack and a required ordering for the same turtle stack, your job is to determine a minimal sequence of operations that rearranges the original stack into the required stack.
The first line of the input consists of a single integer K giving the number of test cases. Each test case consist on an integern giving the number of turtles in the stack. The next n lines specify the original ordering of the turtle stack. Each of the lines contains the name of a turtle, starting with the turtle on the top of the stack and working down to the turtle at the bottom of the stack. Turtles have unique names, each of which is a string of no more than eighty characters drawn from a character set consisting of the alphanumeric characters, the space character and the period (`.'). The next n lines in the input gives the desired ordering of the stack, once again by naming turtles from top to bottom. Each test case consists of exactly 2n+1 lines in total. The number of turtles (n) will be less than or equal to two hundred.
For each test case, the output consists of a sequence of turtle names, one per line, indicating the order in which turtles are to leave their positions in the stack and crawl to the top. This sequence of operations should transform the original stack into the required stack and should be as short as possible. If more than one solution of shortest length is possible, any of the solutions may be reported. Print a blank line after each test case.

Sample Input

2
3
Yertle
Duke of Earl
Sir Lancelot
Duke of Earl
Yertle
Sir Lancelot
9
Yertle
Duke of Earl
Sir Lancelot
Elizabeth Windsor
Michael Eisner
Richard M. Nixon
Mr. Rogers
Ford Perfect
Mack
Yertle
Richard M. Nixon
Sir Lancelot
Duke of Earl
Elizabeth Windsor
Michael Eisner
Mr. Rogers
Ford Perfect
Mack

Sample Output

Duke of Earl

Sir Lancelot
Richard M. Nixon
Yertle

sorting
1. finding the lowest element Ei among elements that should crawl.
2. crawl all elements from Ei to 0.


#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int N;
vector<string>seq,tar;
void ans(){
    N=seq.size();
    int rank[200],m=-1,cur;
    map<string,int>mp;
    rep(i,N)mp[tar[i]]=i;
    rep(i,N){
        rank[i]=mp[seq[i]];
        if(DBG)printf("%s: %d\n",seq[i].c_str(), rank[i]);
    }
    cur=rank[0];
    REP(i,1,N){
        if(cur>rank[i])m=max(rank[i],m);
        cur=max(cur,rank[i]);
    }
    if(DBG)printf("m: %d %s\n",m,tar[m].c_str());
    for(int i=m;i>=0;i--)printf("%s\n",tar[i].c_str());
    printf("\n");
}
int main(){
    int a,b;
    char nds[100];
    string s;
    cin>>a;
    rep(i,a){
        tar.clear(),seq.clear();
        scanf("%d ",&b);
        rep(i,b){
            fgets(nds,100,stdin);
            if(nds[strlen(nds)-1]=='\n')nds[strlen(nds)-1]='\0';
            seq.push_back(nds);
        }
        rep(i,b){
            fgets(nds,100,stdin);
            if(nds[strlen(nds)-1]=='\n')nds[strlen(nds)-1]='\0';
            if(DBG)printf("b: %s\n",nds);
            tar.push_back(nds);
        }
        ans();
    }
}

uva 630 - Anagrams (II)

Anagrams (II)

One of the preferred kinds of entertainment of people living in final stages of XX century is filling in the crosswords. Almost every newspaper and magazine has a column dedicated to entertainment but only amateurs have enough after solving one crossword. Real professionals require more than one crossword for a week. And it is so dull - just crosswords and crosswords - while so many other riddles are waiting out there. For those are special, dedicated magazines. There are also quite a few competitions to take part in, even reaching the level of World Championships. Anyway - a lot.

You were taken on by such a professional for whom riddle solving competing is just a job. He had a brilliant idea to use a computer in work not just to play games. Somehow anagrams found themselves first in the line. You are to write a program which searches for anagrams of given words, using a given vocabulary, tediously filled with new words by yours employer.

Input

The first line of the input is an integer M, then a blank line followed by M datasets. There is a blank line between datasets. The structure of each dataset is given below:



..............


................

END

is an integer number N < 1000. up to are words from the vocabulary. up to are the words to find anagrams for. All words are lowercase (word END means end of data - it is NOT a test word). You can assume all words are not longer than 20 characters.

Output

For each list the found anagrams in the following way:

Anagrams for: 
) 
...............

should be printed on 3 chars.
In case of failing to find any anagrams your output should look like this:

Anagrams for: 
No anagrams for:

Print a blank line between datasets.

Sample Input

1

8
atol
lato
microphotographics
rata
rola
tara
tola
pies
tola
kola
aatr
photomicrographics
END

Sample Output

Anagrams for: tola
  1) atol
  2) lato
  3) tola
Anagrams for: kola
No anagrams for: kola
Anagrams for: aatr
  1) rata
  2) tara
Anagrams for: photomicrographics
  1) microphotographics

Miguel A. Revilla
2000-01-10

string anagrams


#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

vector<string>seq,query;
struct Node{
    Node(int a,string b):ind(a),s(b){}
    int ind;
    string s;
};
bool comp(Node a,Node b){return a.s<b.s;}
void getNum(){
    int cnt[26];
    string s;
    vector<string>res[query.size()],qs;
    vector<Node>sst;
    vector<Node>::iterator ite,start;
    rep(i,seq.size()){
        string s2;
        memset(cnt,0,sizeof(cnt));
        s=seq[i];
        rep(j,s.size())cnt[s[j]-'a']++;
        rep(j,26){if(cnt[j])s2+=char(cnt[j]+'0');else s2+='0';}
        sst.push_back(Node(i,s2));
    }
    rep(i,query.size()){
        string s2;
        memset(cnt,0,sizeof(cnt));
        s=query[i];
        rep(j,s.size())cnt[s[j]-'a']++;
        rep(j,26){if(cnt[j])s2+=char(cnt[j]+'0');else s2+='0';}
        if(DBG)printf("qs %s %s\n",query[i].c_str(),s2.c_str());
        qs.push_back(s2);
    }
    sort(sst.begin(),sst.end(),comp);
    rep(i,qs.size()){
        start = lower_bound(sst.begin(),sst.end(),Node(0,qs[i]),comp);
        for(ite=start;ite!=sst.end();ite++)
            if(qs[i]==(*ite).s){
                if(DBG)printf("%s: found %s\n",query[i].c_str(),seq[(*ite).ind].c_str());
                res[i].push_back(seq[(*ite).ind]);
            }
    }
    rep(i,query.size())
        if(!res[i].size())printf("Anagrams for: %s\nNo anagrams for: %s\n",query[i].c_str(),query[i].c_str());
        else{
            printf("Anagrams for: %s\n",query[i].c_str());
            rep(j,res[i].size())printf("  %d) %s\n",j+1,res[i][j].c_str());
        }
}
int main(){
    int a,b;
    bool ll=0;
    string s;
    scanf("%d ",&a);
    rep(i,a){
        seq.clear(),query.clear();
        cin>>b;
        rep(i,b)cin>>s,seq.push_back(s);
        while(cin>>s){
            if(s=="END")break;
            query.push_back(s);
        }
        if(ll)printf("\n");ll=1;
        getNum();
    }
}

uva 454 - Anagrams

Anagrams

An anagram is a word or phrase formed by rearranging the letters of another word or phrase. For example, ``carthorse" is an anagram of ``orchestra". Blanks within a phrase are ignored in forming anagrams. Thus, ``orchestra" and ``horse cart" are also anagrams.

Write a program that reads a list of phrases and prints all pairs of anagrams occurring in the list.

Input

The input file will contain a single integer at the first line of the input, indicate the number of test case you need to test followed by a blank line. Each test case will consist of from 1 to 100 lines. A completely empty or blank line signals the end of a test case. Each line constitutes one phrase.

Output

Some number of lines (including possibly 0 if there are no anagrams in the list), each line containing two anagrammatic phrases separated by `='.

Each anagram pair should be printed exactly once, and the order of the two phrases within a printed pair must be lexicographic, as well as the first phrases and the second ones in case some first are equal.
Two consecutive output for two consecutive input is separated by a single blank line.

Sample Input

1

carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra

Sample Output

carthorse = horse cart
carthorse = orchestra
horse cart = orchestra
i do not know u = ok i now donut

anagram strings


#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

vector<string>seq,seq2;
struct Node{
    Node(int a,string b,string c):ind(a),s(b),ori(c){}
    int ind;
    string s,ori;
};
bool comp(Node a,Node b){if(a.s!=b.s)return a.s<b.s; else return a.ori<b.ori;}
void getNum(){
    int cnt[60];
    string s;
    vector<pair<string,string> >res;
    vector<Node>sst;
    rep(i,seq.size()){
        string s2;
        memset(cnt,0,sizeof(cnt));
        s=seq[i];
        rep(j,s.size())if(s[j]!=' ')cnt[s[j]-'A']++;
        rep(j,60){if(cnt[j])s2+=char(cnt[j]+'0');else s2+='0';}
        sst.push_back(Node(i,s2,s));
    }
    sort(sst.begin(),sst.end(),comp);
    rep(i,sst.size()){
        int j=i;
        while(j+1<sst.size()&&sst[j].s==sst[j+1].s){
            REP(k,i,j+1)res.push_back(make_pair(sst[k].ori,sst[j+1].ori));
            j++;
        }
        i=j;
    }
    sort(res.begin(),res.end());
    rep(i,res.size())printf("%s = %s\n",res[i].first.c_str(),res[i].second.c_str());
}
int main(){
    int a;
    char nds[1000];
    bool ll=0;
    string s;
    scanf("%d ",&a);
    rep(i,a){
        seq.clear();
        while(fgets(nds,1000,stdin)){
            if(nds[0]=='\n')break;
            if(nds[strlen(nds)-1]=='\n')nds[strlen(nds)-1]='\0';
            s=nds;
            seq.push_back(s);
        }
        if(ll)printf("\n");ll=1;
        getNum();
    }
}

2012年8月13日星期一

uva 156 - Ananagrams

Ananagrams

Most crossword puzzle fans are used to anagrams--groups of words with the same letters in different orders--for example OPTS, SPOT, STOP, POTS and POST. Some words however do not have this attribute, no matter how you rearrange their letters, you cannot form another word. Such words are called ananagrams, an example is QUIZ.

Obviously such definitions depend on the domain within which we are working; you might think that ATHENE is an ananagram, whereas any chemist would quickly produce ETHANE. One possible domain would be the entire English language, but this could lead to some problems. One could restrict the domain to, say, Music, in which case SCALE becomes a relative ananagram (LACES is not in the same domain) but NOTE is not since it can produce TONE.

Write a program that will read in the dictionary of a restricted domain and determine the relative ananagrams. Note that single letter words are, ipso facto, relative ananagrams since they cannot be ``rearranged'' at all. The dictionary will contain no more than 1000 words.

Input

Input will consist of a series of lines. No line will be more than 80 characters long, but may contain any number of words. Words consist of up to 20 upper and/or lower case letters, and will not be broken across lines. Spaces may appear freely around words, and at least one space separates multiple words on the same line. Note that words that contain the same letters but of differing case are considered to be anagrams of each other, thus tIeD and EdiT are anagrams. The file will be terminated by a line consisting of a single #.

Output

Output will consist of a series of lines. Each line will consist of a single word that is a relative ananagram in the input dictionary. Words must be output in lexicographic (case-sensitive) order. There will always be at least one relative ananagram.

Sample input

ladder came tape soon leader acme RIDE lone Dreis peat
 ScAlE orb  eye  Rides dealer  NotE derail LaCeS  drIed
noel dire Disk mace Rob dries
#

Sample output

Disk
NotE
derail
drIed
eye
ladder
soon

string


#include<stdio.h>
#include<string.h>
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 1

using namespace std;

bool fail[1000];
vector<string>seq,seq2;
struct Node{
    Node(int a,string b):ind(a),s(b){}
    int ind;
    string s;
};
bool comp(Node a,Node b){return a.s<=b.s;}
string lower(string s){
    rep(i,s.size())s[i]=tolower(s[i]);
    return s;
}
void getNum(){
    int cnt[26];
    string s;
    vector<string>res;
    vector<Node>sst;
    rep(i,seq.size()){
        string s2;
        memset(cnt,0,sizeof(cnt));
        s=seq2[i];
        rep(j,s.size())cnt[s[j]-'a']++;
        rep(j,26){if(cnt[j])s2+=char(cnt[j]+'0');else s2+='0';}
        sst.push_back(Node(i,s2));
    }
    sort(sst.begin(),sst.end(),comp);
    rep(i,sst.size()){
        int j=i;
        while(j+1<sst.size()&&sst[j].s==sst[j+1].s)fail[j]=fail[j+1]=1,j++;
        if(!fail[j])res.push_back(seq[sst[j].ind]);
        i=j;
    }
    sort(res.begin(),res.end());
    rep(i,res.size())printf("%s\n",res[i].c_str());
}
int main(){
    char nds[100];
    stringstream buf;
    string s,s2;
    set<string>st;
    while(fgets(nds,100,stdin)){
        if(nds[0]=='#')getNum();
        if(nds[strlen(nds)-1]=='\n')nds[strlen(nds)-1]='\0';
        buf.clear(),buf.str(nds);
        while(!buf.eof()){
            buf>>s;
            if(!st.count(s)){
                st.insert(s);
                seq.push_back(s);
                seq2.push_back(lower(s));
            }
        }
    }
}

uva 153 - Permalex

Permalex

Given a string of characters, we can permute the individual characters to make new strings. If we can impose an ordering on the characters (say alphabetic sequence), then the strings themselves can be ordered and any given permutation can be given a unique number designating its position in that ordering. For example the string `acab' gives rise to the following 12 distinct permutations:

tabular21

Thus the string `acab' can be characterised in this sequence as 5.

Write a program that will read in a string and determine its position in the ordered sequence of permutations of its constituent characters. Note that numbers of permutations can get very large; however we guarantee that no string will be given whose position is more than

Input and Output

Input will consist of a series of lines, each line containing one string. Each string will consist of up to 30 lower case letters, not necessarily distinct. The file will be terminated by a line consisting of a single #.

Output will consist of a series of lines, one for each line of the input. Each line will consist of the position of the string in its sequence, right justified in a field of width 10.

Sample input

bacaa
abc
cba
#

Sample output

        15
         1
         6

permutation

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

string S;
vector<int>prime;
int base[50],cur[50];
int notp[30];

void getP(){
    notp[0]=notp[1]=1;
    int b;
    rep(i,30)
        if(!notp[i]){
            prime.push_back(i);
            if(DBG)printf("%d\n",i);
            for(int b=i*2;b<30;b+=i)notp[b]=1;
        }
}
void getEle(int c){
    int a;
    REP(i,2,c+1){
        a=i;
        rep(j,prime.size()){
            while(a%prime[j]==0)a/=prime[j],base[prime[j]]++;
            if(a==1)break;
        }
    }
}
void getCur(int c){
    int a;
    REP(i,2,c+1){
        a=i;
        rep(j,prime.size()){
            while(a%prime[j]==0){
                a/=prime[j];
                if(base[prime[j]])base[prime[j]]--;
                else cur[prime[j]]++;
            }
            if(a==1)break;
        }
    }
}
int getN(string s,int a,int b){
    int cnt[26];
    memset(cnt,0,sizeof(cnt));
    memset(cur,0,sizeof(cur));
    REP(i,a,b)cnt[s[i]-'a']++;
    rep(i,26)if(cnt[i]>1)getEle(cnt[i]);
    getCur(b-a);
    int c=1;
    REP(i,2,32)if(cur[i])c*=int(pow(i,cur[i])+0.5);
    if(DBG)printf("getN: %s\n",s.c_str());
    return c;
}
void getNum(){
    int c=0;
    char d;
    bool add[256];
    string s;
    rep(i,S.size()-1){
        memset(add,0,sizeof(add));
        REP(j,i+1,S.size())
            if(S[j]<S[i]&&!add[S[j]]){
                s=S;
                add[s[j]]=1;
                d=s[i],s[i]=s[j],s[j]=d;
                c+=getN(s,i+1,s.size());
            }
    }
    printf("%10d\n",c+1);
}
int main(){
    getP();
    while(cin>>S){
        if(S[0]=='#')break;
        getNum();
    }
}

uva 750 - 8 Queens Chess Problem

8 Queens Chess Problem

In chess it is possible to place eight queens on the board so that no one queen can be taken by any other. Write a program that will determine all such possible arrangements for eight queens given the initial position of one of the queens.
Do not attempt to write a program which evaluates every possible 8 configuration of 8 queens placed on the board. This would require 8⁸ evaluations and would bring the system to its knees. There will be a reasonable run time constraint placed on your program.

Input

The first line of the input contains the number of datasets, and it's followed by a blank line. Each dataset will be two numbers separated by a blank. The numbers represent the square on which one of the eight queens must be positioned. A valid square will be represented; it will not be necessary to validate the input.To standardize our notation, assume that the upper left-most corner of the board is position (1,1). Rows run horizontally and the top row is row 1. Columns are vertical and column 1 is the left-most column. Any reference to a square is by row then column; thus square (4,6) means row 4, column 6.
Each dataset is separated by a blank line.

Output

Output for each dataset will consist of a one-line-per-solution representation.Each solution will be sequentially numbered $1 \dots N$ . Each solution will consist of 8 numbers. Each of the 8 numbers will be the ROW coordinate for that solution. The column coordinate will be indicated by the order in which the 8 numbers are printed. That is, the first number represents the ROW in which the queen is positioned in column 1; the second number represents the ROW in which the queen is positioned in column 2, and so on.
The sample input below produces 4 solutions. The full 8 $\times$ 8 representation of each solution is shown below.

DO NOT SUBMIT THE BOARD MATRICES AS PART OF YOUR SOLUTION!

   SOLUTION 1           SOLUTION 2           SOLUTION 3           SOLUTION 4

1 0 0 0 0 0 0 0      1 0 0 0 0 0 0 0      1 0 0 0 0 0 0 0      1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0      0 0 0 0 0 0 1 0      0 0 0 0 0 1 0 0      0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0      0 0 0 1 0 0 0 0      0 0 0 0 0 0 0 1      0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1      0 0 0 0 0 1 0 0      0 0 1 0 0 0 0 0      0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0      0 0 0 0 0 0 0 1      0 0 0 0 0 0 1 0      0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0      0 1 0 0 0 0 0 0      0 0 0 1 0 0 0 0      0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0      0 0 0 0 1 0 0 0      0 1 0 0 0 0 0 0      0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0      0 0 1 0 0 0 0 0      0 0 0 0 1 0 0 0      0 0 0 1 0 0 0 0

Submit only the one-line, 8 digit representation of each solution as described earlier. Solution #1 below indicates that there is a queen at Row 1, Column 1; Row 5, Column 2; Row 8, Column 3; Row 6, Column 4; Row 3,Column 5; ... Row 4, Column 8.
Include the two lines of column headings as shown below in the sample output and print the solutions in lexicographical order.
Print a blank line between datasets.

Sample Input

1

1 1

Sample Output

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      1 5 8 6 3 7 2 4
 2      1 6 8 3 7 4 2 5
 3      1 7 4 6 8 2 5 3
 4      1 7 5 8 2 4 6 3

Miguel A. Revilla
2000-02-09

DFS

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int R,C;
bool thr[8][8];
int pad[4][2];
vector<vector<int> >res;
vector<int>cur;
void init(){
    pad[0][0]=-1,pad[0][1]=-1,
    pad[1][0]=-1,pad[1][1]=1,
    pad[2][0]=1,pad[2][1]=1,
    pad[3][0]=1,pad[3][1]=-1;
}
bool valid(int a,int b){
    return a>=0&&b>=0&&a<8&&b<8;
}
void add(int a,int b){
    rep(i,8)thr[a][i]=1,thr[i][b]=1;
    int c,d;
    rep(i,4){
        c=a,d=b;
        while(valid(c+pad[i][0],d+pad[i][1]))c+=pad[i][0],d+=pad[i][1],thr[c][d]=1;
    }
}
void DFS(int c){
    if(c==8){res.push_back(cur);return;}
    if(c==C){cur.push_back(R),DFS(c+1),cur.erase(cur.end()-1);}
    else{
        bool tthr[8][8];
        rep(i,8){
            if(!thr[i][c]){
                memcpy(tthr,thr,sizeof(thr));
                cur.push_back(i);
                if(DBG)printf("push %d %d\n",i,c);
                add(i,c);
                DFS(c+1);
                memcpy(thr,tthr,sizeof(thr));
                cur.erase(cur.end()-1);
            }
        }
    }
}
void getNum(){
    res.clear();
    if(DBG)rep(i,8){rep(j,8)printf("%d ",thr[i][j]);printf("\n");}
    DFS(0);
    rep(i,res.size()){
        printf("%2d      ",i+1);
        rep(j,res[i].size()){if(j)printf(" ");printf("%d",res[i][j]+1);}
        printf("\n");
    }
}
int main(){
    int a;
    bool ll=0;
    cin>>a;
    init();
    
    rep(i,a){
        memset(thr,0,sizeof(thr));
        cin>>R>>C,R--,C--;
        add(R,C);
        if(ll)printf("\n");ll=1;
        printf("SOLN       COLUMN\n #      1 2 3 4 5 6 7 8\n\n");
        getNum();
    }
}

uva 439 - Knight Moves

Knight Moves

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

Input Specification

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

Output Specification

For each test case, print one line saying "To get from xx to yy takes n knight moves.".

Sample Input

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

Sample Output

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

BFS

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<queue>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int R1,C1,R2,C2;
string S1,S2;
bool visit[8][8];
int pad[8][2];
struct Node{
    Node(int a,int b,int c):r(a),c(b),dis(c){}
    int r,c,dis;
};
void init(){
    pad[0][0]=-1,pad[0][1]=-2,
    pad[1][0]=-1,pad[1][1]=2,
    pad[2][0]=1,pad[2][1]=2,
    pad[3][0]=1,pad[3][1]=-2,
    pad[4][0]=-2,pad[4][1]=-1,
    pad[5][0]=-2,pad[5][1]=1,
    pad[6][0]=2,pad[6][1]=1,
    pad[7][0]=2,pad[7][1]=-1;
}
bool valid(int a,int b){
    return a>=0&&b>=0&&a<8&&b<8;
}
void getNum(){
    int ans=0;
    bool f=0;
    memset(visit,0,sizeof(visit));
    queue<Node>q;
    q.push(Node(R1,C1,0));
    if(!(R1==R2&&C1==C2))
        while(q.size()){
            int x=q.front().r,y=q.front().c,dis=q.front().dis;
            q.pop();
            visit[x][y]=1;
            if(DBG)printf("x y dis %d %d %d\n",x,y,dis);
            rep(i,8){
                int c=x+pad[i][0],d=y+pad[i][1];
                if(valid(c,d)&&!visit[c][d]){
                    if(c==R2&&d==C2){ans=dis+1,f=1;break;}
                    q.push(Node(c,d,dis+1));
                }
            }
            if(f)break;
        }
    printf("To get from %s to %s takes %d knight moves.\n",S1.c_str(),S2.c_str(),ans);
}
int main(){
    init();
    while(cin>>S1>>S2){
        R1=(S1[1]-'1'),C1=S1[0]-'a';
        R2=(S2[1]-'1'),C2=S2[0]-'a';
        if(DBG)printf("%d %d %d %d\n",R1,C1,R2,C2);
        getNum();
    }
}

2012年8月10日星期五

uva 278 - Chess

Chess

Almost everyone knows the problem of putting eight queens on an

chessboard such that no Queen can take another Queen. Jan Timman (a famous Dutch chessplayer) wants to know the maximum number of chesspieces of one kind which can be put on an

board with a certain size such that no piece can take another. Because it's rather difficult to find a solution by hand, he asks your help to solve the problem.

He doesn't need to know the answer for every piece. Pawns seems rather uninteresting and he doesn't like Bishops anyway. He only wants to know how many Rooks, Knights, Queens or Kings can be placed on one board, such that one piece can't take any other.

Input

The first line of input contains the number of problems. A problem is stated on one line and consists of one character from the following set r, k, Q, K, meaning respectively the chesspieces Rook, Knight, Queen or King. The character is followed by the integers m (

) and n (

), meaning the number of rows and the number of columns or the board.

Output

For each problem specification in the input your program should output the maximum number of chesspieces which can be put on a board with the given formats so they are not in position to take any other piece.

Note: The bottom left square is 1, 1.

Sample Input

2
r 6 7
k 8 8

Sample Output

6
32

chess, no need to use DFS >"<


#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int R,C,T,G;
bool tht[10][10];
int mp[128];
void init(){
    mp['r']=0,mp['k']=1,mp['Q']=2,mp['K']=3;
}
void getNum(){
    int ans;
    if(T==3){R=R%2?R+1:R,C=C%2?C+1:C,printf("%d\n",R*C/4);return;}
    if(T==1){ans=R*C/2,printf("%d\n",ans);return;}
    if(T==0||T==2){printf("%d\n",G);return;}
}
int main(){
    int a,b,c;
    string s;
    cin>>a;
    init();
    rep(i,a){
        cin>>s>>R>>C;
        G=min(R,C);
        if(DBG)printf("R C %d %d\n",R,C);
        T=mp[s[0]];
        getNum();
    }
}

uva 167 - The Sultan's Successors

The Sultan's Successors

The Sultan of Nubia has no children, so she has decided that the country will be split into up to k separate parts on her death and each part will be inherited by whoever performs best at some test. It is possible for any individual to inherit more than one or indeed all of the portions. To ensure that only highly intelligent people eventually become her successors, the Sultan has devised an ingenious test. In a large hall filled with the splash of fountains and the delicate scent of incense have been placed k chessboards. Each chessboard has numbers in the range 1 to 99 written on each square and is supplied with 8 jewelled chess queens. The task facing each potential successor is to place the 8 queens on the chess board in such a way that no queen threatens another one, and so that the numbers on the squares thus selected sum to a number at least as high as one already chosen by the Sultan. (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one.)

Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions. (You know that the Sultan is both a good chess player and a good mathematician and you suspect that her score is the best attainable.)

Input

Input will consist of k (the number of boards), on a line by itself, followed by k sets of 64 numbers, each set consisting of eight lines of eight numbers. Each number will be a positive integer less than 100. There will never be more than 20 boards.

Output

Output will consist of k numbers consisting of your k scores, each score on a line by itself and right justified in a field 5 characters wide.

Sample input

1
 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

Sample output

eight queen

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int brd[8][8];
bool row[8],tht[8][8];
vector<pair<int,int> >pos;
bool threat(int r,int c){
    rep(i,pos.size()){
        int x=pos[i].first,y=pos[i].second;
        if(x==r||abs(x-r)==abs(y-c))return 1;
    }
    return 0;
}

int DFS(int c,int d){
    if(c==8)return d;
    int m=0;
    rep(i,8)
        if(!threat(i,c)){
            pos.push_back(make_pair(i,c)),m=max(m,DFS(c+1,d+brd[i][c]));
            pos.erase(pos.end()-1);
        }
    return m;
}
void getNum(){
    printf("%5d\n",DFS(0,0));
}
int main(){
    int a;
    cin>>a;
    rep(i,a){
        rep(i,8)rep(j,8)scanf("%d",&brd[i][j]);
        getNum();
    }
}

2012年8月9日星期四

uva 793 - Network Connections

Network Connections

Bob, who is a network administrator, supervises a network of computers. He is keeping a log connections between the computers in the network. Each connection is bi-directional. Two computers are interconnected if they are directly connected or if they are interconnected with the same computer. Occasionally, Bob has to decide, quickly, whether two given computers are connected, directly or indirectly, according to the log information.

Write a program which based on information input from a text file counts the number of successful and the number of unsuccessful answers to the questions of the kind :

is computer_i interconnected with computer_j ?

Input and Output

The first line of the input contains the number of dataset, and it's followed by a blank line. Each dataset is defined as follows:

1.

The number of computers in the network (a strictly positive integer);

2.

A list of pairs of the form:

(a): c computer_i computer_j, where computer_i and computer_j are integers from 1 to $no\_of\_computers$ . A pair of this form shows that computer_i and computer_j get interconnected.
(b): q computer_i computer_j, where computer_i and computer_j are integers from 1 to $no\_of\_computers$ . A pair of this form stands for the question: is computer_i interconnectedwith computer_j?

There's a blank line between datasets.
Each pair is on a separate line. Pairs can appear in any order, regardless of their type. The log is updated after each pair of type (a) and each pair of type (b) is processed according to the current network configuration.

For example, the input file illustrated in the sample below corresponds to a network of 10 computers and 7 pairs. There are N1 successfully answered questions and N2 unsuccessfully answered questions. The program prints these two numbers to the standard output on the same line, in the order: successful answers, unsuccessful answers, as shown in the sample output. Print a blank line between datasets.

Sample Input

Sample Input

1,2

Miguel Revilla
2001-01-05

union-set

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int N;
int *par;
int find(int a){
    if(par[a]==a)return a;
    int c=a;
    while(par[a]!=a)a=par[a];
    return par[c]=a;
}
void merge(int to,int from){
    int a=find(to),b=find(from);
    par[b]=a;
}
int main(){
    int a,b,c,c1,c2;
    char nds[100];
    bool ll=0;
    scanf("%d",&a);
    rep(i,a){
        c1=c2=0;
        scanf("%d ",&N);
        par=(int *)malloc(N*sizeof(int));
        rep(i,N)par[i]=i;
        if(DBG)printf("N %d\n",N);
        while(fgets(nds,100,stdin)){
            if(nds[0]=='\n')break;
            if(nds[0]=='c'){
                sscanf(&nds[1],"%d%d",&b,&c),c--,b--;
                if(find(b)!=find(c))merge(b,c);
            }
            else if(nds[0]=='q'){
                sscanf(&nds[1],"%d%d",&b,&c),c--,b--;
                if(find(b)!=find(c))c2++;
                else c1++;
            }
        }
        if(ll)printf("\n");ll=1;
        printf("%d,%d\n",c1,c2);
    }
}

uva 10397 - Connect the Campus

Problem E
Connect the Campus
Input: standard input
Output: standard output
Time Limit: 2 seconds

Many new buildings are under construction on the campus of the University of Waterloo. The university has hired bricklayers, electricians, plumbers, and a computer programmer. A computer programmer? Yes, you have been hired to ensure that each building is connected to every other building (directly or indirectly) through the campus network of communication cables.

We will treat each building as a point specified by an x-coordinate and a y-coordinate. Each communication cable connects exactly two buildings, following a straight line between the buildings. Information travels along a cable in both directions. Cables can freely cross each other, but they are only connected together at their endpoints (at buildings).

You have been given a campus map which shows the locations of all buildings and existing communication cables. You must not alter the existing cables. Determine where to install new communication cables so that all buildings are connected. Of course, the university wants you to minimize the amount of new cable that you use.

Fig: University of Waterloo Campus

Input

The input file describes several test case. The description of each test case is given below:

The first line of each test case contains the number of buildings N (1<=N<=750). The buildings are labeled from 1 to N. The next N lines give the x and y coordinates of the buildings. These coordinates are integers with absolute values at most 10000. No two buildings occupy the same point. After that there is a line containing the number of existing cables M (0 <= M <= 1000) followed by M lines describing the existing cables. Each cable is represented by two integers: the building numbers which are directly connected by the cable. There is at most one cable directly connecting each pair of buildings.

Output

For each set of input, output in a single line the total length of the new cables that you plan to use, rounded to two decimal places.

Sample Input

4
103 104
104 100
104 103
100 100
1
4 2

4
103 104

104 100

104 103

100 100

4 2

Sample Output
4.41
4.41

(Problem-setters: G. Kemkes & G. V. Cormack, CS Dept, University of Waterloo)

“A man running away from a tiger need not run faster than the tiger but run faster than the friend.”

MST - kruskal (note: use double instead of float to avoid floating-point error)

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<set>
#include<math.h>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0

using namespace std;

int N,E;
bool con[750][750];
vector<pair<int,int> >ver;
int par[750];
struct Edge{
    Edge(int a,int b,double dis):a(a),b(b),dis(dis){}
    int a,b;
    double dis;
    bool operator <(const Edge a)const{return dis<a.dis;}
};
vector<Edge>eg;

int find(int a){
    if(par[a]==a)return a;
    int c=a;
    while(par[a]!=a)a=par[a];
    return par[c]=a;
}
void merge(int to,int from){
    int a=find(to),b=find(from);
    par[b]=a;
}
void getNum(){  
    double sum=0;
    if(E<N-1){
        int c=E; 
        sort(eg.begin(),eg.end());
        rep(i,eg.size()){
            int a=eg[i].a,b=eg[i].b;
            if(find(a)!=find(b)){
                if(DBG)printf("eg %d %d\n",a+1,b+1);
                merge(a,b),sum+=eg[i].dis;
                if(c==N-1)break;
            } 
        }
    }
    printf("%.2f\n",sum);
}
double dist(double a,double b,double c,double d){
    return sqrt(pow(a-c,2)+pow(b-d,2));
}
void getDis(){
    rep(i,N)REP(j,i+1,N){
        if(!con[i][j])
            eg.push_back(Edge(i,j,dist(ver[i].first,ver[i].second,ver[j].first,ver[j].second)));
    }
}
int main(){
    int a,b,c,d,x,y;
    while(cin>>N){
        eg.clear(),E=0;
        ver.clear(),memset(con,0,sizeof(con));
        rep(i,N)par[i]=i;           //init
        rep(i,N)cin>>x>>y,ver.push_back(make_pair(x,y));
        cin>>b;
        rep(i,b){
            cin>>c>>d,c--,d--,con[c][d]=con[d][c]=1;
            if(find(c)!=find(d)){
                if(DBG)printf("insert %d %d\n",c+1,d+1);
                merge(c,d),E++;
            }
        }
        getDis();
        getNum();
    }
}

訂閱：文章 (Atom)

2012年8月29日 星期三

2012年8月28日 星期二

2012年8月24日 星期五

2012年8月17日 星期五

2012年8月15日 星期三

克罗内克符号

2012年8月14日 星期二

Input:

Output:

Sample Input:

Sample Output:

The Problem

The Input

The Output

Sample Input

Sample Output

Problem D: ShellSort

The Problem

Sample Input

Sample Output

Input

Output

Sample Input

Sample Output

2012年8月13日 星期一

Input

Output

Sample input

Sample output

Input and Output

Sample input

Sample output

Input Specification

Output Specification

Sample Input

Sample Output

2012年8月10日 星期五

Input

Output

Sample Input

Sample Output

Input

Output

Sample input

Sample output

2012年8月9日 星期四

2012年8月29日星期三

2012年8月28日星期二

2012年8月24日星期五

2012年8月17日星期五

2012年8月15日星期三

2012年8月14日星期二

2012年8月13日星期一

2012年8月10日星期五

2012年8月9日星期四