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;
}
目录
相关文章
uva10152 ShellSort
uva10152 ShellSort
57 0
uva10112 Myacm Triangles
uva10112 Myacm Triangles
39 0
UVa11776 - Oh Your Royal Greediness!
UVa11776 - Oh Your Royal Greediness!
50 0
|
存储 固态存储
|
机器学习/深度学习
uva 12470 Tribonacci
点击打开uva12470  思路: 矩阵快速幂 分析: 1 裸题 代码: /************************************************ * By: chenguolin ...
988 0
|
人工智能
uva 305 Joseph
点击打开链接uva 305 思路: 数学+打表 分析: 1 传统的约瑟夫问题是给定n个人和m,每次数m次把当前这个人踢出局,问最后留下的一个人的编号 2 这一题是前k个人是好人,后面k个是坏人。
1045 0
uva 10054 - The Necklace
点击打开链接uva 10054 思路: 欧拉回路 分析: 1 对于一个无向图来说如果这个图是一个欧拉图,那么必须满足该图是连通的并且每个点的度数都是偶数 2 题目给定n条边的无向图问我们是否是一个欧拉图,是的话输出欧拉图的一条路径 3 ...
837 0
uva 1394 - And Then There Was One
点击打开链接uva 1394 思路: 数学递推 分析: 1 题目是一道变形的约瑟夫环变形问题 2 网上看到一篇很好的数学递推法 问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。
989 0
|
JavaScript 定位技术
uva 10047 - The Monocycle
点击打开链接uva 10047 思路:bfs 分析: 1 题目给定一个起始的状态然后要求是否可以到达目标状态 2 这些状态包括了位置,方向,底面颜色。
849 0