uva :: Programming Challenges :: Chapter 1-100 - The 3n + 1 problem

 1 /* 
 2  * File:   100.cpp
 3  * Author: GongZhi
 4  * Problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=36
 5  * Created on 2009年7月25日, 下午9:01
 6  */
 7 
 8 #include <stdlib.h>
 9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 using namespace std;
16 
17 /*
18  *
19  */
20 int f(int i) {
21     if (i == 1)
22         return 1;
23     else if (i % 2)
24         return f(i * 3 + 1) + 1;
25     else
26         return f(i / 2) + 1;
27 }
28 
29 int main() {
30     int i, j;
31     int r, l, t;
32     int rr, ll;
33     int ans;
34     while (scanf("%d%d", &r, &l) != EOF) {
35         rr = r;
36         ll = l;
37         if (r > l) {
38             t = r;
39             r = l;
40             l = t;
41         }
42         ans = 0;
43         for (i = r; i <= l; i++)
44             if (f(i) > ans) ans = f(i);
45         printf("%d %d %d\n", rr, ll, ans);
46     }
47     return 0;
48 }
49 
50 
51 

posted @ 2009-07-25 21:52 gong 阅读(831) | 评论 (0) | 编辑 收藏

转 ACM/ICPC 中的STL——next_permutation()

在对元素进行字典序组合排列时可以使用STL提供的next_permutation()和prev_permutation()。这里例举两种简单的应用。 

POJ 1731 Orders （使用默认比较方法）

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int main()
{
    int i,j,k,m,n;
    char a[210];   
    while(gets(a) && a[0])
    {       
        n=strlen(a);
        sort(a,a+n);    //先排序
        printf("%s\n",a);
        while(next_permutation(a,a+n))    //返回bool，若无更大的字典序排列返回false
            printf("%s\n",a);
    }
    return 0;
} 

POJ 1256 Anagram （需要自定义cmp函数）

#include<algorithm>
#include<iostream>
#include<cstring>
#include<ctype.h>

using namespace std;

int cmp(char a, char b)      //自定义cmp函数
{
    if(tolower(a)==tolower(b))
        return a<b;
    return tolower(a)<tolower(b);
}

int main()
{
    char s[15];
    int i,j,k,m,n;
    cin>>n;
    cin.ignore();
    while(n--)
    {
        cin.getline(s,15);
        k=strlen(s);
        sort(s,s+k,cmp);
        cout<<s<<endl;
        while(next_permutation(s,s+k,cmp))
            cout<<s<<endl;
    }
    return 0;
}

posted @ 2008-08-27 00:01 gong 阅读(516) | 评论 (0) | 编辑 收藏

TJU 2096 Triangle Encapsulation 题解

就是判断一个坐标系里面的三角形内有多少个整数点
就是枚举所有的整数点然后判断是否在三角形内就是了。
判断是否在三角形内的方法就是求一下三部分的面积是否等于那个大三角形的面积
求面积可以用叉乘或者海伦公式
最好不要用实数来判等
因为三角形的面积乘以2以后是个整数
所以判等的过程中就要使用整数来就可以了
注意输出格式
 1#include<stdio.h>
 2#include<string.h>
 3#include<math.h>
 4char map[50][50];
 5int S(int a,int b,int c,int d)
 6{
 7    int k;
 8    k=a*d-b*c;
 9    if(k<0)k=-k;
10    return k;
11}
12int main()
13{
14//    freopen("aaaaaaa.txt","w",stdout);
15    int x1,x2,x3,y1,y2,y3,mx,my,mmx,mmy,minx,miny,maxx,maxy,ss,s1,s2,s3,i,j,t;
16    while(scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3)!=EOF)
17    {
18        minx=1000000;maxx=-100000;
19        miny=1000000;maxy=-100000;
20        ss=S(x2-x1,y2-y1,x3-x1,y3-y1);
21        memset(map,0,sizeof(map));
22        mx=x1;if(x2>mx)mx=x2;if(x3>mx)mx=x3;
23        my=y1;if(y2>my)my=y2;if(y3>my)my=y3;
24        mmx=x1;if(x2<mmx)mmx=x2;if(x3<mmx)mmx=x3;
25        mmy=y1;if(y2<mmy)mmy=y2;if(y3<mmy)mmy=y3;
26        for(i=mmx;i<=mx;i++)
27            for(j=mmy;j<=my;j++)
28            {
29                s1=S(x1-i,y1-j,x2-i,y2-j);
30                s2=S(x1-i,y1-j,x3-i,y3-j);
31                s3=S(x2-i,y2-j,x3-i,y3-j);
32                if(s1 && s2 && s3 && (s1+s2+s3)==ss)
33                {
34                    map[i+10][j+10]=1;
35                    if(i+10<minx)minx=i+10;
36                    if(i+10>maxx)maxx=i+10;
37                    if(j+10>maxy)maxy=j+10;
38                    if(j+10<miny)miny=j+10;
39                }
40            }
41        for(j=maxy;j>=miny;j--)
42        {
43            for(i=minx;i<=maxx;i++)if(map[i][j])t=i;
44            for(i=minx;i<=t;i++)
45            {
46                if(i!=minx)printf(" ");
47                if(map[i][j])printf("(%2d, %2d)",i-10,j-10);
48                else printf("        ");
49            }
50            printf("\n");
51        }
52        printf("\n");
53    }
54    return 0;
55}
56

posted @ 2008-07-22 16:51 gong 阅读(186) | 评论 (0) | 编辑 收藏

TJU 2095 Clock 题解

Source:  Rocky Mountain 2000
题目就是要问从起点时刻第一次走到终点时刻的过程中分针和时针相遇了多少次
我们知道时针每分钟走动0.5度分钟每分钟走动6度
t为从00：00到当前时刻走了多少分钟
那么分针就比时针多走了5.5t度
当没多走360就说明分针与时针相遇了一次
然后我们就算起点时刻和终点时刻分别对00:00来说相遇了时针多少次
然后他们的差值就是这段区间内相遇了多少次
如果起点时刻小于终点时刻那么就是这个差值加上11
因为一个周期内最多相遇11次
 1#include<stdio.h>
 2int a[100];
 3int main()
 4{
 5    int a,b,c,d,l1,l2,ans,aa,cc;
 6    printf("Initial time  Final time  Passes\n");
 7
 8    while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
 9    {
10        aa=a;cc=c;
11        if(a==12)aa=0;
12        if(c==12)cc=0;
13        l1=aa*60+b;l2=cc*60+d;
14        ans=((l2*11)/720)-((l1*11)/720);
15        if(l1>l2)ans+=11;
16        printf("       %02d:%02d       %02d:%02d      %2d\n",a,b,c,d,ans);
17    }
18    return 0;
19}
20

posted @ 2008-07-22 16:47 gong 阅读(150) | 评论 (0) | 编辑 收藏

TJU 2094 Reserve Bookshelf 题解

Source:  Rocky Mountain 2000

比较烦人的字符串处理问题
题目对于数据范围也没有给出明确的说明
只能开一个大数组来模拟了。
然后每次借走了就标记一下
当还回来的时候就要把这个书在队列最后再新加入了。
输出就按照题目的就可以了
多注意就是了
第一次提交忘记了去掉freopen了

  1#include<map>
  2#include<string.h>
  3#include<stdio.h>
  4#include<string>
  5using namespace std;
  6char cz[40],str[40],use[1000];
  7char data[1000][40];
  8map<string,int> name;
  9string now,t;
 10int l,N,n,num[1000];
 11void PRINT()
 12{
 13    int i;
 14    for(i=l-1;i>=0;i--)
 15        if(use[i])
 16        {
 17            printf("%s%4d\n",data[i],num[i]);
 18
 19        }
 20    printf("AVAILABLE SHELF SPACE:        %4d\n\n",N-n);
 21    gets(str);
 22}
 23void ADD()
 24{
 25    int k,temp=1,L=0;
 26    char ch;
 27    for(k=0;k<6;k++)scanf("%c",&ch);
 28    gets(data[l]);
 29    sscanf(data[l]+30,"%d",&L);
 30    data[l][30]=0;
 31    n+=L;num[l]=L;
 32
 33    t=data[l];
 34    name[t]=l;
 35    use[l]=1;
 36    k=0;
 37    while(n>N)
 38    {    
 39        if(use[k])
 40        {
 41            use[k]=0;
 42            n-=num[k];
 43        }
 44        k++;
 45    }
 46    l++;
 47}
 48void CHECKOUT()
 49{
 50    int k,i;char ch;
 51    scanf("%c",&ch);
 52    gets(str);
 53    for(i=strlen(str);i<30;i++)str[i]=' ';
 54    str[30]=0;
 55    t=str;
 56    k=name[t];
 57    use[k]=0;
 58    n-=num[k];
 59}
 60void RETURN()
 61{
 62    int k,i;
 63    char ch;
 64    for(i=0;i<3;i++)scanf("%c",&ch);
 65    gets(str);
 66    for(i=strlen(str);i<30;i++)str[i]=' ';
 67    str[30]=0;
 68    t=str;
 69    k=name[t];
 70    for(i=0;i<31;i++)data[l][i]=data[k][i];
 71    use[l]=1;num[l]=num[k];
 72    n+=num[l];
 73    k=0;
 74    while(n>N)
 75    {    
 76        if(use[k])
 77        {
 78            use[k]=0;
 79            n-=num[k];
 80        }
 81        k++;
 82    }
 83    l++;
 84}
 85int main()
 86{
 87    //freopen("bbbbbbbbbb.txt","w",stdout);
 88    scanf("%d",&N);n=0;l=0;
 89    name.clear();
 90    memset(use,0,sizeof(use));
 91    while(scanf("%s",cz)!=EOF)
 92    {
 93        now=cz;
 94        if(now=="PRINT")PRINT();
 95        else if(now=="ADD")ADD();
 96        else if(now=="CHECKOUT")CHECKOUT();
 97        else if(now=="RETURN")RETURN();
 98    }
 99    return 0;
100}
101

posted @ 2008-07-22 16:42 gong 阅读(343) | 评论 (2) | 编辑 收藏

TJU 2093 Chairlift 题解

数学问题。
题目很难读懂。
 给定的一个周期的时间表是的是

左下那个点到右下那个点的时间
然后那个圆的周长占一个位置
然后就是要注意一下这两个点是在偏左的位置还是偏右的位置相遇
只需要判断一下从第一个点顺序走到第二个点的距离是否小于一半的总距离就好了
答案就出来了
 1#include<stdio.h>
 2int main()
 3{
 4    int n,l,a,b,f,L;
 5    double t,p,ans,min;
 6    scanf("%d%lf",&n,&t);
 7    f=n/2;
 8    p=t/(f-0.5);
 9    printf("N =%4d, T =%6.1lf\n",n,t);
10    while(scanf("%d%d",&a,&b)!=EOF)
11    {
12        l=a-b;
13        L=a-b;
14        if(l<0)
15        {
16            l=-l;
17            L+=n;
18        }
19        ans=(l-0.5)*p;
20        if((ans/2)>(t-ans/2))min=(t-ans/2);
21        else min=(ans/2);
22        printf("Chair%4d meets chair%4d, remaining time =",a,b);
23        if(L<f)printf("%6.1lf\n",min);
24        else printf("%6.1lf\n",t-min);
25
26    }
27    return 0;
28
29}

posted @ 2008-07-22 16:37 gong 阅读(230) | 评论 (0) | 编辑 收藏

PKU 3363 Annoying painting tool 题解

先开始一直想着很复杂的题目
想了很久
后来看那么多人都过了
感觉应该很简单
然后就想着贪心应该就可以
然后就贪心了一下
顺序往下扫描然后看到这个点是1
那么就把这点为左上角的点的矩形方块操作一下啊
然后一直这样往后就可以了
 1#include<stdio.h>
 2
 3char str[110][110];
 4
 5int main()
 6{
 7    int x,y,len,wide,i,c,p1,p2,j;
 8    while(1)
 9    {
10        scanf("%d %d %d %d", &x,&y,&len,&wide);
11        if(x == 0 && y == 0 && len == 0 && wide == 0)
12            break;
13        for(i = 0; i < x; i++)
14            scanf("%s",str[i]);
15        c = 0;
16        for(i = 0; i < x; i++)
17        {
18           for(j = 0; j < y; j++)
19           {
20               if(str[i][j] == '1')
21               {
22                   if(i+len-1 >= x || j+wide-1 >= y) break;
23                   c++;
24                   for(p1 = i; p1 < i+len; p1++)
25                       for(p2 = j; p2 < j+wide; p2++)
26                       {
27                           if(str[p1][p2] == '1')
28                               str[p1][p2] = '0';
29                           else 
30                               str[p1][p2] = '1';
31                       }
32               }
33           }
34           if(j != y) break;
35        }
36        if(i != x || j != y)
37            printf("-1\n");
38        else
39            printf("%d\n",c);
40    }
41    return 0;
42}
43
44

posted @ 2008-07-20 22:14 gong 阅读(999) | 评论 (0) | 编辑 收藏

PKU 3364 Black and white painting 题解

数学问题
因为棋盘肯定是8*8的
所以棋盘的右下角不可能位于前7列和前7行
所以就用给出的行列都减去7然后乘一下
就可以得到右下角所可能出现的所有位置了
然后因为相邻两个位置棋子不能是相同的
所以要是给出的行列都减去7以后相乘得到的是一个偶数的话那么白色棋子就是一半
然后如果相乘得到是奇数的话那么整个棋盘右下角所表示的元素就会在这里比另外一种多一个
这些都理解以后就很容易了
 1#include<stdio.h>
 2int main()
 3{
 4//freopen("in.txt","r",stdin);
 5int m, n, c,ans;
 6while(1)
 7{
 8scanf("%d%d%d", &m, &n, &c);
 9if(m==0 && n==0 && c==0) break;
10m=m-7;n=n-7;
11ans=(m*n)/2;
12if(m%2==1 && n%2==1)ans=ans+c;
13printf("%d\n",ans);
14}
15return 0;
16}

posted @ 2008-07-20 22:12 gong 阅读(1022) | 评论 (0) | 编辑 收藏

PKU 3365 Cylinder 题解

计算几何问题
公式也很容易推出来
也是敏哥做的
比赛时候我们第一个完成的
 1#include<stdio.h>
 2#include<math.h>
 3 
 4#define PI acos(-1)
 5
 6int main()
 7{
 8    double x,y,s,r,V,tmp;
 9    while(scanf("%lf%lf",&x,&y),x || y)
10    {
11        if(x < y)
12        {
13            tmp = x;
14            x = y; 
15            y = tmp;
16        }
17        s = x/(PI+1);
18        r = s/2;
19        if(s > y)
20        {
21            r = y/2;
22        }
23        V = PI*r*r*y;
24        r = y/(2*PI);
25        if(V < (x-2*r)*PI*r*r)
26        {
27            V = (x-2*r)*PI*r*r;
28        }
29        printf("%.3lf\n",V);
30    }
31    return 0;
32}
33
34
35

posted @ 2008-07-20 22:08 gong 阅读(291) | 评论 (1) | 编辑 收藏

PKU 3366 Deli Deli 题解

学过英语的就都知道怎么做
没学过的题目也看不懂的。
我这种水平的都能看懂所以感觉没什么好注意的了
 1#include<stdio.h>
 2#include<map>
 3#include<string>
 4using namespace std;
 5
 6map<string,int>p1;
 7
 8int main()
 9{
10    char str1[50],str2[50][50],str[50];
11    string s;
12    int m,n,len,i;
13    scanf("%d %d", &m, &n);
14    for(i = 0; i < m; i++)
15    {
16        scanf("%s %s",str1,str2[i]);
17        s = str1;
18        p1[s] = i;
19    }
20    while(n--)
21    {
22        scanf("%s",str);
23        s = str;
24        if(p1.count(s) == 1)
25        {
26            printf("%s\n",str2[p1[s]]);
27            continue;
28        }
29        len = strlen(str);
30        if(len == 1 && str[len-1] == 'y')
31        {
32             str[len-1] = 'i';
33            str[len] = 'e';
34            str[len+1] = 's';
35            str[len+2] = '\0';
36        }
37        else if(len > 1 && str[len-1] == 'y' && str[len-2] != 'a' && str[len-2] != 'i' && str[len-2] != 'o' && str[len-2] != 'e' && str[len-2] != 'u')
38        {
39            str[len-1] = 'i';
40            str[len] = 'e';
41            str[len+1] = 's';
42            str[len+2] = '\0';
43        }
44        else if(len > 1 && str[len-1] == 'h' && (str[len-2] == 's' || str[len-2] == 'c'))
45        {
46            str[len] = 'e';
47            str[len+1] = 's';
48            str[len+2] = '\0';
49        }
50        else if(str[len-1] == 's' || str[len-1] == 'o' || str[len-1] == 'x')
51        {
52            str[len] = 'e';
53            str[len+1] = 's';
54            str[len+2] = '\0';
55        }
56        else
57        {
58            str[len] = 's';
59            str[len+1] = '\0';
60        }
61        printf("%s\n",str);
62    }
63    return 0;
64}
65
66

posted @ 2008-07-20 22:06 gong 阅读(212) | 评论 (0) | 编辑 收藏

仅列出标题
共5页: 1 2 3 4 5 
<2011年2月>
日一二三四五六
303112345
6789101112
13141516171819
20212223242526
272812345
6789101112

导航

统计

常用链接

留言簿(6)

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜