Willing's Blog - C++博客

SGU-296 Sasha vs. Kate

http://acm.sgu.ru/problem.php?contest=0&problem=296

水题，贪心。每次从最高位开始按非上升顺序搜索，遇到上升的则删除或者是到达尾部删除尾部。
例如，19192，要删去2位，则先删去第一个1，然后再删除第二个1.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

int main(void) {
    char s[1002];
    int k;
    scanf ("%s%d", s, &k);
    int i, j, pre;
    int len = strlen(s);
    for (i = 0; i < k; ++i) {
        bool del = false;
        j = 0;
        while (s[j]<'0') {
            ++j;
        }
        pre = j++;
        for (; j < len; ++j) {
            if (s[j] < '0') {
                continue;
            }
            if (s[pre] < s[j]) {
                s[pre] = 1;
                del = true;
                break;
            } else {
                pre = j;
            }
        }
        if (!del) {
            s[pre] = 1;
        }
    }
    for (i = 0; i < len; ++i) {
        if (s[i] > 1) {
            printf ("%c", s[i]);
        }
    }
    printf ("\n");
    return 0;
}

posted @ 2010-05-07 17:19 Willing 阅读(372) | 评论 (0) | 编辑收藏

SGU-222 Little Rooks

http://acm.sgu.ru/problem.php?contest=0&problem=222

类似八皇后，但比八皇后简单。只需要输出解的个数，不需要输出具体的解。另外也不需要判断对角线。
当k>n时显然没有解。
当k=n时有k!个解。
当k<n时，分别从n行和n列中选出k行和k列有 $C_n^k \cdot c_n^k$ 种，在k*k个格中排列有k!种，所有共有 $C_n^k \cdot c_n^k$ *k!种

submit1 : AC

#include <stdio.h>

long long fact(long n) {
    return (n>1) ? fact(n-1)*n : 1;
}

int main(void) {
    long long n, k;
    scanf ("%I64d%I64d", &n, &k);
    if (k > n) {
        printf ("0\n");
    } else {
        printf ("%I64d\n", fact(n)/(fact(k)*fact(n-k))*fact(n)/fact(n-k));
    }
    return 0;
}

posted @ 2010-05-07 16:04 Willing 阅读(409) | 评论 (0) | 编辑收藏

SGU-114 Telecasting station

http://acm.sgu.ru/problem.php?contest=0&problem=114

求带权中位数，一开始也不知道带权中位数是什么。求带权中位数代码里用的是先排序再用二分查找（好像二分查找写得很恶心。。）。求带权中位数还有线性时间的算法，等过几天再写写吧。WA了很多次，都是在二分查找的边界处理上

#include <stdio.h>
#include <stdlib.h>

typedef struct tagCity {
    float x;
    long long p;
} City;

int cmp(const void* a, const void* b) {
    City* pa = (City*)a, *pb = (City*)b;
    if (pa->x < pb->x) {
        return -1;
    } else if (pa->x > pb->x) {
        return 1;
    } else {
        return 0;
    }
}

int main(void) {
    int n;
    scanf ("%d", &n);
    City cities[15000];
    int i;
    for (i = 0; i < n; ++i) {
        scanf ("%f%I64d", &cities[i].x, &cities[i].p);
    }
    qsort(cities, n, sizeof(cities[0]), cmp);
    for (i = 1; i < n; ++i) {
        cities[i].p += cities[i-1].p;
    }
    long long mid = cities[n-1].p / 2;
    i = 0;
    int j = n-1, m;
    while (i <= j) {
        m = (i+j)/2+1;
        if (i == j) {
            m = i;
            break;
        }
        if (cities[m-1].p>=mid) {
            j=m-1;
        } else if (cities[m].p<mid) {
            i=m+1;
        } else {
            break;
        }
    }
    printf ("%.5f\n", cities[m].x);
    return 0;
}

posted @ 2010-05-07 00:35 Willing 阅读(265) | 评论 (0) | 编辑收藏

SGU-124 Broken line

http://acm.sgu.ru/problem.php?contest=0&problem=124

计算几何题，判断一个点是在所给的简单多边形内部，外部或是边界上。判断的方法：
从测试点任意引出射线，与多边形的边相交的交点总数如果是奇数，则在多边形内部。如果是偶数，则在多边形内部。
边界情况的考虑：
如果引出的射线正好通过多边形的某个顶点，那么应该是算1个交点还是2个交点。可以这样判断，如果顶点所在的两条线段处在射线的同侧，则算为2个点，如果是不同侧，则算作一个点。对于引出的射线恰好与多边形的某条边重合的情况也是类似的判断。
为什么可以按照上面判断，一开始我也是不清楚，搜到了WindyWinter牛的解题报告。里面提到了另一种判断边界情况的方法。"解决特殊问题的办法基于这样一个思想——对于不在多边形边上的待测点，把它向上（或向下）移动一个极小量，是不会改变它与多边形的位置关系的。但是移动以后却带来巨大的好处，不会再出现这么多麻烦的特殊情况了。另外，由于移动的是“极小量”，所以不用担心把原本不特殊的情况移动成了特殊情况。 "(From WindyWinter's blog)。所以就可以解释为什么可以通过同侧不同侧来判断了，比如说不同侧的情况，将测试点稍微上移，那么由于线段在不同侧，所以射线将只与其中一条线段相交，所以应该算一个交点。编程中实现的话还是用移动一个极小量来实现简单。
另外题目中提到了所有的边都与坐标轴平行，所以判断与射线的相交也不需要用叉积判断。

submit1: WA on test 5. 其中一个语句的x和y弄混了
submit2: AC

#include <stdio.h>
#include <stdbool.h>

typedef struct tagPoint {
    int x;
    int y;
} Point;

bool OnBorder(Point* a, Point* b, Point* p);
bool cross(Point* a, Point* b, Point* c);

int main(void) {
    int n;
    scanf ("%d", &n);
    Point edge[10000][2], P;
    int i;
    for (i = 0; i < n; ++i) {
        scanf ("%d%d%d%d", &edge[i][0].x, &edge[i][0].y, &edge[i][1].x, &edge[i][1].y);
    }
    scanf ("%d%d", &P.x, &P.y);
    int count = 0;
    for (i = 0; i < n; ++i) {
        if (OnBorder(&edge[i][0], &edge[i][1], &P)) {
            printf ("BORDER\n");
            return 0;
        }
        if (cross(&edge[i][0], &edge[i][1], &P)) {
            count++;
        }
    }
    if (count&1) {
        printf ("INSIDE\n");
    } else {
        printf ("OUTSIDE\n");
    }
    return 0;
}

bool OnBorder(Point* a, Point* b, Point* c) {
    if (a->y == b->y && ((a->x <= c->x && c->x <= b->x) || (a->x >= c->x && c->x >= b->x))) {
        return (a->y == c->y) ? true: false;
    }
    if (a->x == c->x && ((a->y <= c->y && c->y <= b->y) || (a->y >= c->y && c->y >= b->y))) {
        return true;
    }
    return false;
}

bool cross(Point* a, Point* b, Point* c) {
    if (((a->y > c->y && b->y <= c->y) || (a->y <= c->y && b->y > c->y)) && c->x < a->x) {
        return true;
    }
    return false;
}

posted @ 2010-05-06 18:17 Willing 阅读(463) | 评论 (0) | 编辑收藏

SGU-152 Making Round

http://acm.sgu.ru/problem.php?contest=0&problem=152

给几个数，算出每个数所占数的总和的百分比，所有的百分比加起来要等于100，取整的时候可以向上取整或向下（就是可以截断取整数或截断后再加1）。可以将每次取整的误差叠加起来，当误差超过一个百分比时就将误差减去一个百分比，并将这个百分比加到当前数的百分比。

题目还提到如果没有解的话要输出"No solution"，但题目不可能没有解，所以不用管它。

submit1: AC

#include <stdio.h>

int main(void) {
    int n;
    scanf ("%d", &n);
    int a[10001];
    int i;
    int sum = 0;
    for (i = 0; i < n; ++i) {
        scanf ("%d", a+i);
        sum += a[i];
    }
    int part = a[0]*100/sum;
    int little = a[0]*100-part*sum;
    printf ("%d", part);
    for (i = 1; i < n; ++i) {
        part = a[i]*100/sum;
        little += a[i]*100-part*sum;
        if (little >= sum) {
            part++;
            little -= sum;
        }
        printf (" %d", part);
    }
    printf ("\n");
    return 0;
}

posted @ 2010-05-05 12:25 Willing 阅读(374) | 评论 (0) | 编辑收藏

SGU-144 Meeting

http://acm.sgu.ru/problem.php?contest=0&problem=144

概率中的几何概型题目，数据也不大，直接上代码

#include <stdio.h>

int main(void) {
    double x, y, z;
    scanf ("%lf%lf%lf", &x, &y, &z);
    double a = (y-x)*60;
    printf ("%.7f\n", (a*a-(a-z)*(a-z))/(a*a));
    return 0;
}

posted @ 2010-05-04 21:10 Willing 阅读(233) | 评论 (0) | 编辑收藏

SGU-169 Numbers

http://acm.sgu.ru/problem.php?contest=0&problem=169

P(n)定义为n的所有位数的乘积，例如P(1243)=1*2*3*4=24，然后如果P(n)!=0且n mod P(n) = 0，则称n为good number.
如果n和n+1都为good numbers，则称n为perfect number。然后给出位数k(1<=k<=1000000)，找出位数为k的perfect number.

题目看起来很玄虚，而且给出的位数k很大，其实越大的数据不是用高精度的话往往就会有简便的方法，这道题也不例外。
设n有i位，各位分别为a1,a2,...,ai，因为个位为9的数不可能为perfect number（因为n+1不是good number）。
所以n+1的各位分别为a1+1, a2, a3, ... , ai
因为要求n mod P(n) = 0，所以n = s*a1*a2*...*ai，类似的有n+1 = t*(a1+1)*a2*a3*...*ai
所以(n+1)-n = 1 = [t*(a1+1)-s*a1]*a2*a3*...*ai
所以可以推出a2,a3,... ,ai必都为1，则有a1 | n, (a1+1) | (n+1)
所以只需考虑a1的情况，a1有8个取值，（考虑位数大于1的情况）
a1=1时，显然是可以的。
a1=2时，需要判断3能否整除n+1，因为前面有k-1个1，所以只需判断(k-1+3)%3是否等于0
a1=3时，(a1+1)=4,显然4不能整除14，所以3不行
a1=4同上也不行
a1=5时，判断6能否整除n+1,显然与判断a1=3一样
a1=6时，判断7能否整除n+1,经过简单的除法计算可以知道当前面1的个数(k-1)是6的倍数时才有7 | (n+1)
a1=7时，8不能整除118，所以7不行
a1=8时同上不行，所以代码如下：

#include <stdio.h>

int main(void) {
    int k;
    scanf ("%d", &k);
    if (k == 1) {
        printf ("8\n");
        return 0;
    }
    int count = 1;
    if ((k-1)%3==0) {
        count += 2;
        if ((k-1)%6==0) {
            count++;
        }
    }
    printf ("%d\n", count);
    return 0;
}

posted @ 2010-05-04 00:24 Willing 阅读(635) | 评论 (0) | 编辑收藏

SGU-112 a^b-b^a

http://acm.sgu.ru/problem.php?contest=0&problem=112

高精度题，在这道题纠结了很久，最终还是不知道为什么会WA on 2。有知道的同学麻烦告诉我一下。
就是用代码中的PrintBI函数输出就不行，一定得把高精度数先转成字符串，然后再输出字符串才AC。。

#include <iostream>
#include <string>
#include <list>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef list<int> BigInt;

void PrintBI(BigInt& a);

void MulBig(BigInt& a, BigInt& b, BigInt& c) {
    c.clear();
    BigInt::reverse_iterator ia, ib, ic, head;
    int x = 0;
    head = c.rbegin();
    for (ia = a.rbegin(); ia != a.rend(); ++ia) {
        ic = head;
        x = 0;
        for (ib = b.rbegin(); ib != b.rend(); ++ib) {
            if (ic == c.rend()) {
                c.push_front(0);
            }
            x = (*ia)*(*ib)+x/10000+*ic;
            *(ic++) = x%10000;
        }
        if (x /= 10000) {
            c.push_front(x);
        }
        head++;
    }
}

void BigPow(BigInt& a, int b, BigInt& c) {
    c.clear();
    BigInt d = a, tmp;
    c.push_front(1);
    while (b) {
        if (b%2) {
            MulBig(d, c, tmp);
            c = tmp;
        }
        b = b >> 1;
        MulBig(d, d, tmp);
        d = tmp;
    }
}

int cmp(BigInt& a, BigInt& b) {
    if (a.size() > b.size()) {
        return 1;
    }
    if (a.size() < b.size()) {
        return -1;
    }
    BigInt::iterator it1, it2;
    for (it1 = a.begin(), it2 = b.begin(); it1 != a.end(); ++it1, ++it2) {
        if (*it1 > *it2) {
            return 1;
        }
        if (*it1 < *it2) {
            return -1;
        }
    }
    return 0;
}

void Minus(BigInt a, BigInt& b, BigInt& c) {
    c.clear();
    BigInt::reverse_iterator ia, ib, tmp;
    ia = a.rbegin();
    ib = b.rbegin();
    while (ia != a.rend() && ib != b.rend()) {
        if (*ia<*ib) {
            tmp = ia;
            (*(++tmp))--;
            *ia += 10000;
        }
        c.push_front(*(ia++)-*(ib++));
    }
    while (ia != a.rend()) {
        if (*ia < 0) {
            tmp = ia;
            (*(++tmp))--;
            c.push_front(*ia+10000);
        } else {
            c.push_front(*ia);
        }
        ia++;
    }
    while (c.begin() != c.end() && *(c.begin()) == 0) {
        c.erase(c.begin());
    }
}

void atobi(const char* str, BigInt& a) {
    int i;
    for (i = strlen(str)-1; i >= 0; i -= 4) {
        int sum = 0;
        if (i >= 3) {
            sum += (str[i-3]-'0')*1000;
        }
        if (i >= 2) {
            sum += (str[i-2]-'0')*100;
        }
        if (i >= 1) {
            sum += (str[i-1]-'0')*10;
        }
        sum += str[i]-'0';
        a.push_front(sum);
    }
}

void PrintBI(BigInt& a) {
    BigInt::iterator it = a.begin();
    cout << *it;
    for (++it; it != a.end(); ++it) {
        if (*it < 1000) cout << '0';
        if (*it < 100) cout << '0';
        if (*it < 10) cout << '0';
        cout << *it;
    }
}

void BItoa(BigInt& a, char* str) {
    BigInt::iterator it = a.begin();
    int j = 0;
    if (*it >= 1000)
    str[j++]=(*it)/1000+'0';
    if (*it >= 100)
    str[j++] = (*it)/100%10+'0';
    if (*it >= 10)
    str[j++] = (*it)/10%10+'0';
    str[j++] = (*it)%10+'0';
    for (it++; it != a.end(); ++it) {
        str[j++] = (*it)/1000+'0';
        str[j++] = (*it)/100%10+'0';
        str[j++] = (*it)/10%10+'0';
        str[j++] = (*it)%10+'0';
    }
    str[j] = '\0';
}

int main(void) {
    int ia, ib;
    cin >> ia >> ib;
    BigInt a, b, r1, r2, ans;
    a.push_front(ia);
    b.push_front(ib);

    BigPow(a, ib, r1);
    BigPow(b, ia, r2);
    if (cmp(r1, r2) < 0) {
        BigInt tmp;
        tmp = r1;
        r1 = r2;
        r2 = tmp;
        cout << '-';
    }
    Minus(r1, r2, ans);
    char str[300];
    BItoa(ans, str);
    //PrintBI(ans);
    cout << str << endl;
    return 0;
}

posted @ 2010-05-03 21:47 Willing 阅读(330) | 评论 (0) | 编辑收藏

SGU-154 Factorial

http://acm.sgu.ru/problem.php?contest=0&problem=154

给出数Q，求出最小的自然数N使得N!的末尾恰有Q个0，无解输出"No solution"

对于一个数n，求出它的末尾有几个0，只需看n之内的数的质因子5的个数，因为2的个数远多于5。所以可知道一个数末尾0的个数
Q = n/5 + n/(5^2) + n/(5^3) + ...
而题目给出的是Q，要求出的是N，由于是要求出最小的自然数，所以N必定是5的倍数，这点不多做解释。
根据等比数列的求和公式，有
Q = N(5^k - 1) / [4*(5^k)]，由此得
N = 4Q * [(5^k)/(5^k-1)]
注意到 1 < (5^k)/(5^k-1) <= 5/4，且当k->无穷时，(5^k)/(5^k-1)->1，所以可先算出N=4Q的末尾零的个数与所给的Q比较，显然所求的数就在4Q的附近，所以不需要二分查找。
不知道题目的自然数包不包括0，所以提交前先去论坛看了一下，发现0不算入自然数，所以修改了下程序判断0的情况。

#include <stdio.h>

int ZeroTrail(int n);

int main(void) {

int q;

scanf ("%d", &q);

if (!q) {

printf ("1\n");

return 0;

}

int i = 4*q/5*5;

while (ZeroTrail(i) < q) {

i += 5;

}

if (q == ZeroTrail(i)) {

printf ("%d\n", i);

} else {

printf ("No solution\n");

}

return 0;

}

int ZeroTrail(int n) {

int count = 0;

while (n) {

count += n/5;

n /= 5;

}

return count;

}

posted @ 2010-05-03 15:03 Willing 阅读(381) | 评论 (0) | 编辑收藏

SGU-118 Digital Root

http://acm.sgu.ru/problem.php?contest=0&problem=118

一开始是逐位逐位加求出digital root，结果超时了。
到网上看了一下，其实就是数n模9。可以证明如下：
设x = an* 10^(n-1) + ... + a1* 10^0 = an* (1+9)^(n-1) + ... + a1* (1+9)^0
所以x ≡ an + ... + a1 (mod 9)，递推下去即可得证。当取模等于0时，应该取9.

#include <stdio.h>

inline int DigitSum(int n);

int main(void) {
    int k, n;
    int d[1001] = {1};
    scanf ("%d", &k);
    int i, a;
    while (k--) {
        scanf ("%d", &n);
        for (i = 0; i < n; ++i) {
            scanf ("%d", &a);
            d[i+1] = DigitSum(DigitSum(a)*d[i]);
        }
        int result = 0;
        for (i = 1; i <= n; ++i) {
            result += d[i];
        }
        printf ("%d\n", DigitSum(result));
    }
    return 0;
}

int DigitSum(int n) {
    return (n%9) ? n%9 : 9;
}

posted @ 2010-05-02 23:28 Willing 阅读(252) | 评论 (0) | 编辑收藏

仅列出标题

导航

常用链接

留言簿

随笔分类(26)

随笔档案(24)

搜索

最新评论

阅读排行榜

评论排行榜