UVa10123 No Tipping

简介: UVa10123 No Tipping
#include <stdio.h>#include <string.h>intL, M, N, find;
intC, lenl, lenr;
structnode{
intl, w;
} left[30], right[30], res[30];
intis_ok(intl, intr)
{
intlsum=0, rsum=0;
inti;
for (i=0; i<l; i++)
    {
lsum+= (-left[i].l*2-3) *left[i].w;
    }
for (i=0; i<r; i++)
    {
rsum+= (right[i].l*2+3) *right[i].w;
    }
rsum+=C;
if (lsum>rsum) return0;
lsum=0, rsum=0;
for (i=0; i<l; i++)
    {
lsum+= (-left[i].l*2+3) *left[i].w;
    }
for (i=0; i<r; i++)
    {
rsum+= (right[i].l*2-3) *right[i].w;
    }
lsum+=C;
if (rsum>lsum) return0;
return1;
}
voiddfs(intcur, intl, intr)
{
inti;
if (cur==N)
    {
for (i=cur-1; i>=0; i--)
printf("%d %d\n", res[i].l, res[i].w);
find=1;
return;
    }
for (i=l; i<lenl; i++)
    {
if (is_ok(i, r) &&!find)
        {
res[cur].l=left[i].l;
res[cur].w=left[i].w;
dfs(cur+1, i+1, r);
        }
elsebreak;
    }
for (i=r; i<lenr; i++)
    {
if (is_ok(l, i) &&!find)
        {
res[cur].l=right[i].l;
res[cur].w=right[i].w;
dfs(cur+1, l, i+1);
        }
elsebreak;
    }
}
intmain()
{
#ifndef ONLINE_JUDGEfreopen("d:\\UVa\\uva_in.txt", "r", stdin);
#endifintcas=1;
inti, j;
intu, v;
structnodetem;
while (scanf("%d%d%d", &L, &M, &N) &&L+M+N)
    {
lenl=lenr=0;
for (i=0; i<N; i++)
        {
scanf("%d%d", &u, &v);
if (u<0)
            {
left[lenl].l=u;
left[lenl++].w=v;
            }
else            {
right[lenr].l=u;
right[lenr++].w=v;
            }
        }
for (i=1; i<lenl; i++)
        {
for (j=0; j<lenl-i; j++)
            {
if ((-left[j].l*2-3) *left[j].w> (-left[j+1].l*2-3) *left[j+1].w)
                {
tem=left[j];
left[j] =left[j+1];
left[j+1] =tem;
                }
            }
        }
for (i=1; i<lenr; i++)
        {
for (j=0; j<lenr-i; j++)
            {
if ((right[j].l*2-3) *right[j].w> (right[j+1].l*2-3) *right[j+1].w)
                {
tem=right[j];
right[j] =right[j+1];
right[j+1] =tem;
                }
            }
        }
C=3*M;
printf("Case %d:\n", cas++);
find=0;
dfs(0, 0, 0);
if (!find) printf("Impossible\n");
    }
return0;
}
目录
相关文章
UVa11968 - In The Airport
UVa11968 - In The Airport
55 0
uva10152 ShellSort
uva10152 ShellSort
59 0
概率dp - UVA 11021 Tribles
Tribles  Problem's Link:  http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33059   Mean:  有k个细菌,每个细菌只能存活一天,在死去之前可能会分裂出0,1,2....n-1个细菌,对应的概率为p0,p1,p2....pn-1。
825 0
|
C++
UVA 之10010 - Where's Waldorf?
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/SunnyYoona/article/details/24863879 ...
710 0
|
机器学习/深度学习 人工智能
uva 10870 Recurrences
点击打开uva 10870 思路:构造矩阵+矩阵快速幂 分析: 1 题目给定f(n)的表达式 f(n) = a1 f(n - 1) + a2 f(n - 2) + a3 f(n -3) + .
733 0
|
人工智能
uva 305 Joseph
点击打开链接uva 305 思路: 数学+打表 分析: 1 传统的约瑟夫问题是给定n个人和m,每次数m次把当前这个人踢出局,问最后留下的一个人的编号 2 这一题是前k个人是好人,后面k个是坏人。
1046 0
uva 1203 Argus
点击打开链接uva 1203 思路: 优先队列 分析: 1 题目要求前k个事件的编号,我们利用优先队列来维护即可 2 优先队列保存的是一个struct,因此我们需要重载 s.
1295 0