首页 > 代码库 > CodeForces Beta Round #1

CodeForces Beta Round #1

Codeforces Beta Round #1

A. Theatre Square

【题意】一个n*m的矩形广场,用a*a的方形石板铺设,问最少需要多少块石板能铺满广场。

【思路】水题,从n方向来看能能够铺设ceil(n/a)块,从m方向来看能能够铺设ceil(m/a)块,总共有ceil(n/a)*ceil(m/a)块。

 1 /*
 2 ** CodeForces 1A Theatre Square
 3 ** Created by Rayn @@ 2014/05/18
 4 */
 5 #include <cstdio>
 6 #include <cmath>
 7 typedef long long LL;
 8 
 9 int main()
10 {
11 #ifdef _Rayn
12     freopen("in.txt", "r", stdin);
13 #endif
14 
15     int n, m, a;
16     scanf("%d%d%d", &n, &m, &a);
17     //LL l1 = (n + a - 1) / a; //另一种写法,很巧妙
18     //LL l2 = (m + a - 1) / a;
19     LL l1 = n / a;
20     if (n % a != 0)
21         l1++;
22     LL l2 = m / a;
23     if (m % a != 0)
24         l2++;
25     //printf("%I64d %I64d\n", l1, l2);
26     LL ans = l1 * l2;
27     printf("%I64d\n", ans);
28     return 0;
29 }
View Code

 

B. Spreadsheets

【题意】题意好复杂,难得写了,就是对于表格的单元表示有两种表示法,一种是RXCY,代表X行Y列,另一种是字母加数字,字母是代表列,数字代表行,A-Z代表1到26,

AA代表27,AZ代表52列,AAA代表703列。依次类推。要求你对输入的格式转化为另一种格式。

【思路】开始没有想明白到底怎么转化,各种情况处理,if else,while满天飞,WA了好多次,后来简化来看这个就是类似于26进制的道理,然后代码就很清晰了。

  1 /*
  2 ** CodeForces 1B Spreadsheets
  3 ** Created by Rayn @@ 2014/05/19
  4 */
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <cstring>
  8 #include <cctype>
  9 typedef long long LL;
 10 const int MAX = 100010;
 11 
 12 char coor[MAX], col[MAX];
 13 
 14 void GetRow(char *str, int &r, int &c)
 15 {
 16     int flag = 1;
 17     r = c = 0;
 18     for (int i = 1; i < strlen(str); ++i)
 19     {
 20         if (isdigit(str[i]) && flag)
 21         {
 22             r = r * 10 + str[i] - 0;
 23         }
 24         if (isdigit(str[i]) && !flag)
 25         {
 26             c = c * 10 + str[i] - 0;
 27         }
 28         if (str[i] == C)
 29         {
 30             flag = 0;
 31         }
 32     }
 33 }
 34 void GetCol(char *str, char *col, int &r)
 35 {
 36     int cnt = 0;
 37     r = 0;
 38     for (int i = 0; i < strlen(str); ++i)
 39     {
 40         if (isalpha(str[i]))
 41         {
 42             col[cnt++] = str[i];
 43         }
 44         if (isdigit(str[i]))
 45         {
 46             r = r * 10 + str[i] - 0;
 47         }
 48     }
 49 }
 50 int main()
 51 {
 52 #ifdef _Rayn
 53     freopen("in.txt", "r", stdin);
 54 #endif
 55 
 56     int t;
 57     scanf("%d%*c", &t);
 58     while (t--)
 59     {
 60         memset(col, 0, sizeof(col));
 61         gets(coor);
 62         int type = 0;
 63         if (coor[0] == R && isdigit(coor[1]))
 64         {
 65             for (int i = 2; i < strlen(coor); ++i)
 66             {
 67                 if (coor[i] == C)
 68                 {
 69                     type = 1;
 70                     break;
 71                 }
 72             }
 73         }
 74         if (type == 1)
 75         {
 76             int rown = 0, coln = 0, cnt = 0;
 77             GetRow(coor, rown, coln);
 78             while (coln)
 79             {
 80                 coln--;
 81                 int t1 = coln % 26;
 82                 col[cnt++] = t1 + A;
 83                 coln /= 26;
 84             }
 85             for (int i = cnt - 1; i >= 0; --i)
 86             {
 87                 printf("%c", col[i]);
 88             }
 89             printf("%d\n", rown);
 90         }
 91         else if (type == 0)
 92         {
 93             int rown = 0, coln = 0;
 94             GetCol(coor, col, rown);
 95             coln = 0;
 96             for (int i = 0; i < strlen(col); ++i)
 97             {
 98                 coln = coln * 26 + (col[i] - A);
 99                 coln++;
100                 //printf("%d\n", coln);
101             }
102             printf("R%dC%d\n",rown, coln);
103         }
104     }
105     return 0;
106 }
107 /*
108 ** CodeForces 1B Spreadsheets
109 ** Created by Rayn @@ 2014/05/19
110 */
111 #include <cstdio>
112 #include <cmath>
113 #include <cstring>
114 #include <cctype>
115 typedef long long LL;
116 const int MAX = 100010;
117 
118 char coor[MAX], col[MAX];
119 
120 void GetRow(char *str, int &r, int &c)
121 {
122     int flag = 1;
123     r = c = 0;
124     for (int i = 1; i < strlen(str); ++i)
125     {
126         if (isdigit(str[i]) && flag)
127         {
128             r = r * 10 + str[i] - 0;
129         }
130         if (isdigit(str[i]) && !flag)
131         {
132             c = c * 10 + str[i] - 0;
133         }
134         if (str[i] == C)
135         {
136             flag = 0;
137         }
138     }
139 }
140 void GetCol(char *str, char *col, int &r)
141 {
142     int cnt = 0;
143     r = 0;
144     for (int i = 0; i < strlen(str); ++i)
145     {
146         if (isalpha(str[i]))
147         {
148             col[cnt++] = str[i];
149         }
150         if (isdigit(str[i]))
151         {
152             r = r * 10 + str[i] - 0;
153         }
154     }
155 }
156 int main()
157 {
158 #ifdef _Rayn
159     freopen("in.txt", "r", stdin);
160 #endif
161 
162     int t;
163     scanf("%d%*c", &t);
164     while (t--)
165     {
166         memset(col, 0, sizeof(col));
167         gets(coor);
168         int type = 0;
169         if (coor[0] == R && isdigit(coor[1]))
170         {
171             for (int i = 2; i < strlen(coor); ++i)
172             {
173                 if (coor[i] == C)
174                 {
175                     type = 1;
176                     break;
177                 }
178             }
179         }
180         if (type == 1)
181         {
182             int rown = 0, coln = 0, cnt = 0;
183             GetRow(coor, rown, coln);
184             while (coln)
185             {
186                 coln--;
187                 int t1 = coln % 26;
188                 col[cnt++] = t1 + A;
189                 coln /= 26;
190             }
191             for (int i = cnt - 1; i >= 0; --i)
192             {
193                 printf("%c", col[i]);
194             }
195             printf("%d\n", rown);
196         }
197         else if (type == 0)
198         {
199             int rown = 0, coln = 0;
200             GetCol(coor, col, rown);
201             coln = 0;
202             for (int i = 0; i < strlen(col); ++i)
203             {
204                 coln = coln * 26 + (col[i] - A);
205                 coln++;
206                 //printf("%d\n", coln);
207             }
208             printf("R%dC%d\n",rown, coln);
209         }
210     }
211     return 0;
212 }
View Code

 

C. Ancient Berland Circus

【题意】旧时罗马广场的的斗兽场形似一个等边等角的凸包多边形,每个顶点都有一个柱子。由于年代久远,只剩下3个柱子,由此构造一个多边形,使面积最小。最多只会出现100边的凸包。

【思路】浓浓的几何题,各种公式的推导花了我一节高数课的时间。【待补完。。。】

 1 /*
 2 ** CodeForces 1C Ancient Berland Circus
 3 ** Created by Rayn @@ 2014/05/19
 4 */
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <cstring>
 8 #define EPS 1e-5
 9 typedef long long LL;
10 const int MAX = 1010;
11 const double PI = acos(-1.0);
12 
13 struct Pillar
14 {
15     double x, y;
16 } point[5];
17 
18 double Length(Pillar a, Pillar b)
19 {
20     return sqrt((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y));
21 }
22 double GetS(double a, double b, double c)
23 {
24     double p = (a + b + c) / 2;
25     return sqrt(p*(p - a)*(p - b)*(p - c));
26 }
27 double fgcd(double x, double y)
28 {
29     while (fabs(x) > EPS && fabs(y) > EPS)
30     {
31         if (x > y)
32             x -= floor(x / y)*y;
33         else
34             y -= floor(y / x)*x;
35     }
36     return x + y;
37 }
38 int main()
39 {
40 #ifdef _Rayn
41     freopen("in.txt", "r", stdin);
42 #endif
43     double la, lb, lc, S, R;
44     double angA, angB, angC;
45     
46     for (int i = 0; i < 3; ++i)
47     {
48         scanf("%lf%lf", &point[i].x, &point[i].y);
49     }
50     la = Length(point[0], point[1]);
51     lb = Length(point[0], point[2]);
52     lc = Length(point[1], point[2]);
53     S = GetS(la, lb, lc);
54     R = la * lb * lc / (4 * S);
55 
56     angA = acos((lb*lb + lc*lc - la*la) / (2 * lb * lc));
57     angB = acos((la*la + lc*lc - lb*lb) / (2 * la * lc));
58     angC = acos((la*la + lb*lb - lc*lc) / (2 * la * lb));
59     double n = PI / fgcd(fgcd(angA, angB), angC);
60     double ans = n/2 * sin(2 * PI / n) * R*R;
61     printf("%.6f\n", ans);
62 
63     return 0;
64 }
View Code