UVA – Page 2 – hahaschool

LA3971 Assemble

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题11

思路

二分答案。

典型的“最小值最大问题”，考虑二分答案，检查一次二分的时间是可以接受的，因此本题得到解决。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

struct Component{
    int q,p;
    bool operator < (const Component &b) const{
        if(q == b.q){
            return p < b.p;
        }
        return q < b.q;
    }
    Component(){
    }
    Component(int _p,int _q){
        p = _p;
        q = _q;
    }
};

typedef map<string,vector<Component> > Table;
Table tab;
int n,b;

void input(){
    tab.clear();
    scanf(" %d %d",&n,&b);
    for(int i = 1; i <= n; i++){
        string type;
        string name;
        int p,q;
        cin >> type >> name >> p >> q;
        tab[type].push_back(Component(p,q));
    }
    for(Table::iterator it = tab.begin(); it != tab.end(); it++){
        sort(it->second.begin(),it->second.end());
    }
}

bool check(int miq){
    int cst = 0;
    for(Table::iterator it = tab.begin(); it != tab.end(); it++){
        int sel = b+1;
        for(int i = 0; i < it->second.size(); i++){
            if(it->second[i].q >= miq){
                sel=min(sel,it->second[i].p);
            }
        }
        if(sel == b+1){
            return false;
        }else{
            cst += sel;
            if(cst > b){
                return false;
            }
        }
    }
    return true;
}

int solve(){
    int l = 0,r = 1000000000,mid;
    while(l < r){
        mid = l + (r-l+1)/2;
        if(check(mid)){
            l = mid;
        }else{
            r = mid-1;
        }
    }
    if(check(r)){
        return r;
    } else{
        return l;
    }
}

int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    while(caseCnt--){
        input();
        cout << solve() << endl;
    }

    return 0;
}

100

101

102

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

struct Component{

int q,p;

bool operator < (const Component &b) const{

if(q == b.q){

return p < b.p;

}

return q < b.q;

}

Component(){

}

Component(int _p,int _q){

p = _p;

q = _q;

}

};

typedef map<string,vector<Component> > Table;

Table tab;

int n,b;

void input(){

tab.clear();

scanf(" %d %d",&n,&b);

for(int i = 1; i <= n; i++){

string type;

string name;

int p,q;

cin >> type >> name >> p >> q;

tab[type].push_back(Component(p,q));

}

for(Table::iterator it = tab.begin(); it != tab.end(); it++){

sort(it->second.begin(),it->second.end());

}

bool check(int miq){

int cst = 0;

for(Table::iterator it = tab.begin(); it != tab.end(); it++){

int sel = b+1;

for(int i = 0; i < it->second.size(); i++){

if(it->second[i].q >= miq){

sel=min(sel,it->second[i].p);

}

if(sel == b+1){

return false;

}else{

cst += sel;

if(cst > b){

return false;

}

return true;

}

int solve(){

int l = 0,r = 1000000000,mid;

while(l < r){

mid = l + (r-l+1)/2;

if(check(mid)){

l = mid;

}else{

r = mid-1;

}

if(check(r)){

return r;

} else{

return l;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

while(caseCnt--){

input();

cout << solve() << endl;

}

return 0;

}

UVa 10795 A Different Task

December 06, 20152015-12-06hahaschoolLeave a comment

题意

可以参考LRJ大礼包白书第一章例题11

和汉诺塔游戏一样的规则，区别是这个问题会给出多达60个圆盘每一个最开始在哪根柱子上，要你求出从这个局势开始到终盘(00n)最少要移动多少次。

思路

大概是个。。。构造题？

思路比较复杂，而且还涉及传统汉诺塔问题的结论（把一根有k个盘子的堆移到一个空柱子上，需要((2^k)-1)步）。

具体的思路可以参考白书P27.

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

const int MAXN = 105;

int init[MAXN];
int end[MAXN];
int n;

int interchange(int a,int b){
    return 6-a-b;
}

long long func(int *P,int i,int fin){
    if(i == 0){
        return 0;
    }
    if(P[i] == fin){
        return func(P,i-1,fin);
    }
    return func(P,i-1,interchange(P[i],fin)) + (1LL << (i-1));
}

long long solve(){
    int k = n;
    for(; k >= 1; k--){
        if(init[k] != end[k]){
            break;
        }
    }
    if(!k) return k;
    return func(init,k-1,interchange(init[k],end[k])) + func(end,k-1,interchange(init[k],end[k])) + 1;
}

int main(){
    int caseCnt = 0;
    while(scanf(" %d",&n) != EOF && n){
        caseCnt++;
        for(int i = 1; i<= n;i++){
            scanf(" %d",&init[i]);
        }
        for(int i = 1; i<= n; i++){
            scanf(" %d",&end[i]);
        }
        printf("Case %d: %lld\n",caseCnt,solve());
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

const int MAXN = 105;

int init[MAXN];

int end[MAXN];

int n;

int interchange(int a,int b){

return 6-a-b;

}

long long func(int *P,int i,int fin){

if(i == 0){

return 0;

}

if(P[i] == fin){

return func(P,i-1,fin);

}

return func(P,i-1,interchange(P[i],fin)) + (1LL << (i-1));

}

long long solve(){

int k = n;

for(; k >= 1; k--){

if(init[k] != end[k]){

break;

}

if(!k) return k;

return func(init,k-1,interchange(init[k],end[k])) + func(end,k-1,interchange(init[k],end[k])) + 1;

}

int main(){

int caseCnt = 0;

while(scanf(" %d",&n) != EOF && n){

caseCnt++;

for(int i = 1; i<= n;i++){

scanf(" %d",&init[i]);

}

for(int i = 1; i<= n; i++){

scanf(" %d",&end[i]);

}

printf("Case %d: %lld\n",caseCnt,solve());

}

return 0;

}

UVa 11384 Help is needed for Dexter

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题10

思路

试验小数据，找规律。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int main(){
    long long a;
    while(scanf(" %lld",&a) != EOF){
        int res = 0;
        long long fac = 1;
        while(fac <= a){
            fac *= 2;
            res++;
        }
        printf("%d\n",res);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int main(){

long long a;

while(scanf(" %lld",&a) != EOF){

int res = 0;

long long fac = 1;

while(fac <= a){

fac *= 2;

res++;

}

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

}

return 0;

}

UVa 11464 Even Parity

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题7.

思路

大概是个带有机智成分的枚举。

为什么这么说，因为这道题的关键思路点就是发现只要知道第一行，就可以构造出整个数表，这样我们只要枚举第一行就可以解决问题，复杂度直接降低了一次幂。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int n;
int per[16];
int orig[16][16];
int now[16][16];

void genPermutation(int s){
    int cur = n;
    while(cur){
        if(s&1){
            per[cur] = 1;
        }else{
            per[cur] = 0;
        }
        cur--;
        s >>= 1;
    }
}

void genNow(){
    memset(now,0,sizeof(now));
    for(int i = 1; i <= n; i++){
        now[1][i] = per[i];
    }
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= n; j++){
            int cnt = now[i-1][j] + now[i][j-1] + now[i][j+1];
            if(cnt % 2){
                now[i+1][j] = 1;
            }else{
                now[i+1][j] = 0;
            }
        }
    }
}

int compare(){
    int ret = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(now[i][j] == 0 && orig[i][j] == 1){
                return 0x3f3f3f3f;
            }
            if(now[i][j] != orig[i][j]){
                ret++;
            }
        }
    }
    return ret;
}



int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        scanf(" %d",&n);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                scanf(" %d",&orig[i][j]);
            }
        }
        int res = 0x3f3f3f3f;
        for(int i = 0; i < (1 << n); i++){
            genPermutation(i);
            genNow();
            res = min(res,compare());
        }
        if(res == 0x3f3f3f3f){
            res = -1;
        }
        printf("Case %d: %d\n",d,res);
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int n;

int per[16];

int orig[16][16];

int now[16][16];

void genPermutation(int s){

int cur = n;

while(cur){

if(s&1){

per[cur] = 1;

}else{

per[cur] = 0;

}

cur--;

s >>= 1;

}

void genNow(){

memset(now,0,sizeof(now));

for(int i = 1; i <= n; i++){

now[1][i] = per[i];

}

for(int i = 1; i < n; i++){

for(int j = 1; j <= n; j++){

int cnt = now[i-1][j] + now[i][j-1] + now[i][j+1];

if(cnt % 2){

now[i+1][j] = 1;

}else{

now[i+1][j] = 0;

}

int compare(){

int ret = 0;

for(int i = 1; i <= n; i++){

for(int j = 1; j <= n; j++){

if(now[i][j] == 0 && orig[i][j] == 1){

return 0x3f3f3f3f;

}

if(now[i][j] != orig[i][j]){

ret++;

}

return ret;

}

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for(int d = 1; d <= caseCnt; d++){

scanf(" %d",&n);

for(int i = 1; i <= n; i++){

for(int j = 1; j <= n; j++){

scanf(" %d",&orig[i][j]);

}

int res = 0x3f3f3f3f;

for(int i = 0; i < (1 << n); i++){

genPermutation(i);

genNow();

res = min(res,compare());

}

if(res == 0x3f3f3f3f){

res = -1;

}

printf("Case %d: %d\n",d,res);

}

return 0;

}

UVA 10881 Piotr's Ants

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题5

思路

两个蚂蚁相遇会马上调换方向，从视觉上看其实相当于擦身而过（虽然两只蚂蚁的身份并没有交换）。就像在物理中，两个质量相等的小球发生完全弹性碰撞，交换速度。这里是本题第一个思路点。

无论在任何时候，第i只蚂蚁永远是第i只蚂蚁，因为上面也说了，只是视觉上的擦身，实际上蚂蚁又各自回去了。这是第二个思路点。在这个地方还有一个问题，那就是可能会以为仅仅是位置关系保持原来的顺序，其实方向关系也是保持原来的顺序的，这样就可以解决蚂蚁的最终状态的判定问题。

这样我们就有了解法：首先利用擦身而过的想法，求出最终所有蚂蚁的分布。然后利用标号守恒的想法，把终止状态和起始状态对应。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

struct Ant{
    int pos;
    int dir;//1:R -1:L 0:turing
    int id;
    bool operator < (const Ant &b) const{
        return pos < b.pos;
    }
};

bool cmp(const Ant &a, const Ant &b){
    return a.id < b.id;
}

vector<Ant> all;
int loc[10005];

int main(){
    int caseCnt;
    scanf(" %d",&caseCnt);
    for(int d = 1; d <= caseCnt; d++){
        int L,T,n;
        scanf(" %d %d %d",&L,&T,&n);
        Ant tmp;
        all.clear();
        all.resize(n);
        for(int i = 0; i < n; i++){
            tmp.id = i;
            scanf(" %d",&tmp.pos);
            char dir;
            scanf(" %c",&dir);
            if(dir == 'L'){
                tmp.dir = -1;
            }else{
                tmp.dir = 1;
            }
            all[i] = tmp;
        }
        sort(all.begin(),all.end());
        for(int i = 0; i < n; i++){
            loc[all[i].id] = i;
            all[i].pos += all[i].dir * T;
        }
        sort(all.begin(),all.end());
        for(int i = 0; i < all.size(); i++){
            if((i > 0 && all[i].pos == all[i-1].pos) || (i < all.size()-1 && all[i+1].pos== all[i].pos)){
                all[i].dir = 0;
            }
        }
        //sort(all.begin(),all.end(),cmp);
        printf("Case #%d:\n",d);
        for(int i = 0; i < all.size(); i++){
            if(all[loc[i]].pos < 0 || all[loc[i]].pos > L){
                puts("Fell off");
            }else{
                printf("%d ",all[loc[i]].pos);
                if(all[loc[i]].dir == 1){
                    puts("R");
                }else if(all[loc[i]].dir == -1){
                    puts("L");
                }else{
                    puts("Turning");
                }
            }
        }
        puts("");
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

struct Ant{

int pos;

int dir;//1:R -1:L 0:turing

int id;

bool operator < (const Ant &b) const{

return pos < b.pos;

}

};

bool cmp(const Ant &a, const Ant &b){

return a.id < b.id;

}

vector<Ant> all;

int loc[10005];

int main(){

int caseCnt;

scanf(" %d",&caseCnt);

for(int d = 1; d <= caseCnt; d++){

int L,T,n;

scanf(" %d %d %d",&L,&T,&n);

Ant tmp;

all.clear();

all.resize(n);

for(int i = 0; i < n; i++){

tmp.id = i;

scanf(" %d",&tmp.pos);

char dir;

scanf(" %c",&dir);

if(dir == 'L'){

tmp.dir = -1;

}else{

tmp.dir = 1;

}

all[i] = tmp;

}

sort(all.begin(),all.end());

for(int i = 0; i < n; i++){

loc[all[i].id] = i;

all[i].pos += all[i].dir * T;

}

sort(all.begin(),all.end());

for(int i = 0; i < all.size(); i++){

if((i > 0 && all[i].pos == all[i-1].pos) || (i < all.size()-1 && all[i+1].pos== all[i].pos)){

all[i].dir = 0;

}

//sort(all.begin(),all.end(),cmp);

printf("Case #%d:\n",d);

for(int i = 0; i < all.size(); i++){

if(all[loc[i]].pos < 0 || all[loc[i]].pos > L){

puts("Fell off");

}else{

printf("%d ",all[loc[i]].pos);

if(all[loc[i]].dir == 1){

puts("R");

}else if(all[loc[i]].dir == -1){

puts("L");

}else{

puts("Turning");

}

puts("");

}

return 0;

}

LA 3708 Graveyard

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白书第一章例题4.

思路

大概是构造题。

跟白书不太一样的解法，贪心地把两种方案的一个顶点对在一起，然后逐个检查，取两种方案的最小角度差，加在一起，就是答案。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int main(){
    double a,b;
    while(scanf(" %lf %lf",&a,&b) != EOF){
        double sumdeg = 0;
        for(int i = 0; i <= a; i++){
            double deg = 360.0*(double)i/a;
            while(deg > 360.0/(a+b)){
                deg -= 360.0/(a+b);
            }
            sumdeg += min(deg,abs(360.0/(a+b)-deg));
        }
        double ans = sumdeg*10000.0/360.0;
        printf("%.4lf\n",ans);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int main(){

double a,b;

while(scanf(" %lf %lf",&a,&b) != EOF){

double sumdeg = 0;

for(int i = 0; i <= a; i++){

double deg = 360.0*(double)i/a;

while(deg > 360.0/(a+b)){

deg -= 360.0/(a+b);

}

sumdeg += min(deg,abs(360.0/(a+b)-deg));

}

double ans = sumdeg*10000.0/360.0;

printf("%.4lf\n",ans);

}

return 0;

}

UVa 11300 Spreading the Wealth

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考LRJ白第一章例题3

思路

大概是个构造题。

解决的方法是把整个题转化成一个方程组，令每个人手里的初始金币数量为Ai(已知)，送出数量Xi,受付数量Yi,最终每个人金币数量M(已知)，这样得到由若干形如Ai-Xi+Yi=M方程组成的方程组，当所有方程形式一样时，考虑逐个联立消去未知量，最终得到了关于X1和Xi的若干等式（注意到Xi和Yi+1的相等关系），我们的目标是令Xi之和最小，我们把所有Xi加在一起，就得到了一个仅关于X1的和式。

这个和式的形式可以几何表示是求数轴上一个点，使得其与若干已知点距离之和最短，这个问题的解取在中位数，这样本问题就可以解决了。（中位数是解的想法在白书上有详细的证明，使用反证法）

综合来看，本体需要适当转化，数学变形，数形结合。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

long long n;
long long c[1000005];

int main() {
    while(scanf(" %lld",&n) != EOF) {
        unsigned long long m = 0;
        for(int i = 1; i <= n; i++) {
            scanf(" %llu",&c[i]);
            m += c[i];
        }
        m /= n;
        for(int i = 1; i <= n; i++) {
            c[i] -= m;
            c[i] += c[i-1];
        }
        sort(c,c+n);
        long long rf;
        if(n % 2) {
            rf = c[n/2];
        } else {
            rf = (c[n/2] + c[n/2-1])/2;
        }
        long long res = 0;
        for(int i = 0; i <= n-1; i++) {
            res += abs(c[i] - rf);
        }
        printf("%lld\n",res);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

long long n;

long long c[1000005];

int main() {

while(scanf(" %lld",&n) != EOF) {

unsigned long long m = 0;

for(int i = 1; i <= n; i++) {

scanf(" %llu",&c[i]);

m += c[i];

}

m /= n;

for(int i = 1; i <= n; i++) {

c[i] -= m;

c[i] += c[i-1];

}

sort(c,c+n);

long long rf;

if(n % 2) {

rf = c[n/2];

} else {

rf = (c[n/2] + c[n/2-1])/2;

}

long long res = 0;

for(int i = 0; i <= n-1; i++) {

res += abs(c[i] - rf);

}

printf("%lld\n",res);

}

return 0;

}

UVa 11729 Commando War

December 06, 20152015-12-06hahaschoolLeave a comment

题意

请参考《LRJ大礼包::白》第一章例题2

思路

大概是贪心。

只要交代了任务，部下自己就会给做完了，基于这样的题意我们就可以设计这样的一种贪心策略：优先考虑完成任务时间长的，这样交代完了之后就会有更多的时间可以一边交代任务一边有人完成任务，更有效率。

具体操作就是把完成任务时间从大到小排个序，然后顺着检查一遍。

这个策略的证明在白书上面有提供，大概的证明套路就是说明不用这个策略时得到的答案不会更优，在证明时分类讨论了两种情况。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

int n;
pair<int,int> task[1005];

bool cmp(pair<int,int> a,pair<int,int> b){
    if(a.second == b.second){
        return a.first < b.first;
    }else{
        return a.second > b.second;
    }
}

int work(){
    int bound = 0;
    int now = 0;
    for(int i = 1; i <= n; i++){
        now += task[i].first;
        bound = max(now + task[i].second, bound);
    }
    return bound;
}

int main(){
    int d = 0;
    while(scanf(" %d",&n) != EOF){
        d++;
        if(!n){
            break;
        }
        for(int i = 1; i <= n; i++){
            scanf(" %d %d",&task[i].first,&task[i].second);
        }
        sort(task+1,task+1+n,cmp);
        printf("Case %d: %d\n",d,work());
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

int n;

pair<int,int> task[1005];

bool cmp(pair<int,int> a,pair<int,int> b){

if(a.second == b.second){

return a.first < b.first;

}else{

return a.second > b.second;

}

int work(){

int bound = 0;

int now = 0;

for(int i = 1; i <= n; i++){

now += task[i].first;

bound = max(now + task[i].second, bound);

}

return bound;

}

int main(){

int d = 0;

while(scanf(" %d",&n) != EOF){

d++;

if(!n){

break;

}

for(int i = 1; i <= n; i++){

scanf(" %d %d",&task[i].first,&task[i].second);

}

sort(task+1,task+1+n,cmp);

printf("Case %d: %d\n",d,work());

}

return 0;

}

UVA 12946 Peanoland contacting Gaussland

October 31, 20152015-10-31hahaschoolLeave a comment

题意

给出了一个从整数到复数的映射，你要求出给你的整数映射成的复数的实部和虚部。

思路

STL complex裸题。

直接模拟就好，当然自己写一个complex结构体也不是难事。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <complex>

using namespace std;

complex<long long> imo[33];

void pre(){
    imo[0] = 1;
    for(int i = 1; i<= 32; i++){
        imo[i] = imo[i-1] * complex<long long>(-1,1);
    }
}



int main(){
    pre();
    long long p;
    while(scanf(" %lld",&p) != EOF){
        complex<long long> ans = 0;
        int cur = 0;
        while(p){
            if(p & 1){
                ans += imo[cur];
            }
            cur++;
            p >>= 1;
        }
        printf("%lld %lld\n",ans.real(),ans.imag());
    }

    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

#include <map>

#include <complex>

using namespace std;

complex<long long> imo[33];

void pre(){

imo[0] = 1;

for(int i = 1; i<= 32; i++){

imo[i] = imo[i-1] * complex<long long>(-1,1);

}

int main(){

pre();

long long p;

while(scanf(" %lld",&p) != EOF){

complex<long long> ans = 0;

int cur = 0;

while(p){

if(p & 1){

ans += imo[cur];

}

cur++;

p >>= 1;

}

printf("%lld %lld\n",ans.real(),ans.imag());

}

return 0;

}

UVA 12955 Factorial

October 31, 20152015-10-31hahaschoolLeave a comment

题意

给出你一个数，问你这个数最少能用多少个数（可以重复）的阶乘表示出来。

思路

使用一种简单的贪心策略：

从一个刚好比给出的数小的阶乘开始，不断尝试减掉较大的阶乘，直到将给出的数减为0 。

这个贪心策略是合理的，因为如果我们当前可以减掉n!，我们减掉(n-1)!一定不如减掉n!优，因为n!=n*(n-1)!，相当于我们多减了n次，所以我们要减掉n!才能保证最优。

代码

#include<iostream>
using namespace std;
const int mxa = 10;
int sum[mxa];
void Premake(){
	sum[1] = 1;
	for(int i=2;i<mxa;i++)
		sum[i] = sum[i-1]*i;
}
int main(){
	Premake();
	int input;
	while(cin >> input){
		int ans = 0;
		int last = 8;
		while(input && last){
			if(input < sum[last]){
				last -= 1;
				continue;
			}
			input -= sum[last];
			ans ++;
		}
		cout << ans << endl;
	}
	return 0;
}

#include<iostream>

using namespace std;

const int mxa = 10;

int sum[mxa];

void Premake(){

sum[1] = 1;

for(int i=2;i<mxa;i++)

sum[i] = sum[i-1]*i;

}

int main(){

Premake();

int input;

while(cin >> input){

int ans = 0;

int last = 8;

while(input && last){

if(input < sum[last]){

last -= 1;

continue;

}

input -= sum[last];

ans ++;

}

cout << ans << endl;

}

return 0;

}