UVa 102 -- Ecological Bin Packing

Friday,2008-08-22 at 17:10:49

水题,枚举即可.
第一次提交WA,没有注意这道题并不是Special Judge,如果有多组顺序符合要求,需要输出字典序最靠前的一组.
虽然用了string,不过代码写的还是很垃圾.

/*
  UVa 102; Ecological Bin Packing
  - sqybi's code
*/
//for my winsty
 
#include 
#include 
using namespace std;
 
const int nn = 3;
int t, res, now;
int a[nn][nn];
bool u[nn];
char ch[nn] = {'B', 'G', 'C'};
string ress, nows;
 
void get(int i)
{
    if (i == 3)
    {
        if (now > res || (now == res && nows < ress))
        {
            res = now;
            ress = nows;
        }
        return;
    }
    for (int j = 0; j != 3; ++ j)
        if (! u[j])
        {
            u[j] = true;
            now = now + a[i][j];
            nows += ch[j];
            get(i+1);
            nows = nows.erase(i, 1);
            now = now - a[i][j];
            u[j] = false;
        }
}
 
int main()
{
    while (scanf("%d", &a[0][0]) != EOF)
    {
        t = a[0][0];
        for (int i = 0; i != 3; ++ i)
            for (int j = 0; j != 3; ++ j)
                if (i + j)
                {
                    scanf("%d", &a[i][j]);
                    t += a[i][j];
                }
        res = 0;
        now = 0;
        nows = "";
        memset(u, false, sizeof(u));
        get(0);
        cout << ress << ' ' << t - res << endl;
    }
}
By sqybi | Posted in About Computer, [OI, ACM, etc] | Tagged , | Comments (0)

UVa 100 -- The 3n + 1 problem

Friday,2008-08-22 at 00:09:12

经典的3n+1,没有想到这道题调了一个晚上.
在Project Euler上看过这道题,于是按照那道题写了个部分DP.然后诡异的WA了.
调啊,调啊,只找到了一个trick:输入的两个数不一定小数在前大数在后.
然后呢,我这个程序是search,可加了一个预处理,for i=1~10000 do dp[i]=f(i),然后调用f(i)的地方改成dp[i],就过不了,都鬼了...怀疑数据范围有问题.

search可以1s过掉.

/*
  UVa 100; The 3n + 1 problem
  - sqybi's code
*/
//for my winsty
 
//#define DEBUG
#include 
using namespace std;
 
const int nn = 1000001, mm = 10001;
int l, r, ll, rr, maxa;
 
int f(int i)
{
    if (i == 1)
        return 1;
    else if (i % 2)
        return f(i*3+1)+1;
    else
        return f(i/2)+1;
}
 
int main()
{
    #ifdef DEBUG
    freopen("uva100.in", "r", stdin);
    freopen("uva100.out", "w", stdout);
    #endif
 
    while (scanf("%d%d", &ll, &rr) != EOF)
    {
        l = ll;
        r = rr;
        if (l > r) swap(l, r);
        maxa = 0;
        for (int i = l; i <= r; ++ i)
            if (f(i) > maxa) maxa = f(i);
        printf("%d %d %d\n", ll, rr, maxa);
    }
}
By sqybi | Posted in About Computer, [OI, ACM, etc] | Tagged , | Comments (2)

UVa Plan正式启动

Thursday,2008-08-21 at 20:40:46

本来一直就没关注过UVa,甚至连用户都没有注册过.昨天在sjtu的网站上到处瞎逛,偶然看到了一个做题计划.分为两档,一个是初学者,一个是进阶.初学者那个推荐了USACO,被我直接忽略掉.不过那个进阶吸引了我,那里面推荐了UVa的200道题.

想想以后进入sjtu说不定也要做题,于是干脆这段时间就刷UVa这些题算了.
决定启动UVa Plan.

SGU的刷题计划已然结束,50多题显然不是我想要的.希望这次能坚持的更长(我不奢望我能完成这200道题的计划).
语言用C++.
每道题都会在这里发布题解,订阅Feed的童鞋们会比较痛苦,请原谅我...

sjtu推荐的200道题及我的完成情况(随时更新):
http://sqybi.com/blog/plan

By sqybi | Posted in About Computer, [OI, ACM, etc] | Tagged , | Comments (0)