Birthday Cake

Description

Prince Remmarguts helped Uyuw successfully hold a concert in our previous story (POJ 2451), and ...that was the day of Uyuw's birthday.

Ting-a-ling, the chef was called on by Remmarguts. "You must prepare an immense birthday cake for lovely Princess Uyuw in a single day," said Remmarguts. Though Remmarguts' order is outrageous, the chef eventually rushed to buy flour, sugar, fat, and some other ingredients.

There had been chaos caused by war for quite a long time. The price of everything has been highly raised. Being the head accountant of country UDF – United Delta of Freedom, you must weight the cake carefully to make sure the chef did not perform a cheat on the ingredients.

The cake is made up of N levels. There is a 'cube' in each level, while the length of cube on k-th level (count from the topmost) is exactly k! For Remmarguts lives in an M-Dimension world unlike our, you should notice that the 'cube' here means M-Dimension cube, and the volume of a cube with length k is k ^ M.

You are to calculate the total volume of such an immense cake.
Input

You should read the number of test cases Z (Z <= 30) in the first line. Each of the following lines denotes a single test case, consisting of two integers N and M. We guarantee that 1 <= N <= 10 ^ 41 and 3 <= M <= 100.
Output

Output one line per test case, showing the total volume of that cake. We also guarantee that the volume is less than 10 ^ 250.
Sample Input

2
3 3
6 5
Sample Output

36
12201

1个回答

Yukari's Birthday 怎么来求的
Problem Description Today is Yukari's n-th birthday. Ran and Chen hold a celebration party for her. Now comes the most important part, birthday cake! But it's a big challenge for them to place n candles on the top of the cake. As Yukari has lived for such a long long time, though she herself insists that she is a 17-year-old girl. To make the birthday cake look more beautiful, Ran and Chen decide to place them like r ≥ 1 concentric circles. They place ki candles equidistantly on the i-th circle, where k ≥ 2, 1 ≤ i ≤ r. And it's optional to place at most one candle at the center of the cake. In case that there are a lot of different pairs of r and k satisfying these restrictions, they want to minimize r × k. If there is still a tie, minimize r. Input There are about 10,000 test cases. Process to the end of file. Each test consists of only an integer 18 ≤ n ≤ 1012. Output For each test case, output r and k. Sample Input 18 111 1111 Sample Output 1 17 2 10 3 10
Cake Pieces and Plates
Description kcm1700, ntopia, suby, classic, tkwons, and their friends are having a birthday party for kcm1700. Of course, there is a very large birthday cake. They divide the birthday cake into undistinguishable pieces and put them on identical plates. kcm1700 is curious, so he wants to know how many ways there are to put m cake pieces on n plates. Input In the only input line, there are two integers n, m (1 ≤ n, m ≤ 4 500), which are the number of the plates and the number of the cake pieces respectively. Output If the number of ways is K, just output K mod 1000000007 because K can be very large. Sample Input 3 7 Sample Output 8
Yukari's Birthday
Problem Description Today is Yukari's n-th birthday. Ran and Chen hold a celebration party for her. Now comes the most important part, birthday cake! But it's a big challenge for them to place n candles on the top of the cake. As Yukari has lived for such a long long time, though she herself insists that she is a 17-year-old girl. To make the birthday cake look more beautiful, Ran and Chen decide to place them like r ≥ 1 concentric circles. They place ki candles equidistantly on the i-th circle, where k ≥ 2, 1 ≤ i ≤ r. And it's optional to place at most one candle at the center of the cake. In case that there are a lot of different pairs of r and k satisfying these restrictions, they want to minimize r × k. If there is still a tie, minimize r. Input There are about 10,000 test cases. Process to the end of file. Each test consists of only an integer 18 ≤ n ≤ 1012. Output For each test case, output r and k. Sample Input 18 111 1111 Sample Output 1 17 2 10 3 10
Share the Cakes

Cut the Cake 的设计思路
Problem Description Today is the birthday of Mr. Bon Vivant, who is known as one of the greatest p鈚issiers in the world. Those who are invited to his birthday party are gourmets from around the world. They are eager to see and eat his extremely creative cakes. Now a large box-shaped cake is being carried into the party. It is not beautifully decorated and looks rather simple, but it must be delicious beyond anyone's imagination. Let us cut it into pieces with a knife and serve them to the guests attending the party. The cake looks rectangular, viewing from above (Figure C-1). As exemplified in Figure C-2, the cake will iteratively be cut into pieces, where on each cut exactly a single piece is cut into two smaller pieces. Each cut surface must be orthogonal to the bottom face and must be orthogonal or parallel to a side face. So, every piece shall be rectangular looking from above and every side face vertical. Figure C-1: The top view of the cake Figure C-2: Cutting the cake into pieces Piece sizes in Figure C-2 vary significantly and it may look unfair, but you don't have to worry. Those guests who would like to eat as many sorts of cakes as possible often prefer smaller pieces. Of course, some prefer larger ones. Your mission of this problem is to write a computer program that simulates the cutting process of the cake and reports the size of each piece. Input The input is a sequence of datasets, each of which is of the following format. n w d p1 s1 ... pn sn 　 The first line starts with an integer n that is between 0 and 100 inclusive. It is the number of cuts to be performed. The following w and d in the same line are integers between 1 and 100 inclusive. They denote the width and depth of the cake, respectively. Assume in the sequel that the cake is placed so that w and d are the lengths in the east-west and north-south directions, respectively. Each of the following n lines specifies a single cut, cutting one and only one piece into two. pi is an integer between 1 and i inclusive and is the identification number of the piece that is the target of the i-th cut. Note that, just before the i-th cut, there exist exactly i pieces. Each piece in this stage has a unique identification number that is one of 1, 2, ..., i and is defined as follows: * The earlier a piece was born, the smaller its identification number is. * Of the two pieces born at a time by the same cut, the piece with the smaller area (looking from above) has the smaller identification number. If their areas are the same, you may define as you like the order between them, since your choice in this case has no influence on the final answer. Note that identification numbers are adjusted after each cut. si is an integer between 1 and 1000 inclusive and specifies the starting point of the i-th cut. From the northwest corner of the piece whose identification number is pi, you can reach the starting point by traveling si in the clockwise direction around the piece. You may assume that the starting point determined in this way cannot be any one of the four corners of the piece. The i-th cut surface is orthogonal to the side face on which the starting point exists. The end of the input is indicated by a line with three zeros. Output For each dataset, print in a line the areas looking from above of all the pieces that exist upon completion of the n cuts specified in the dataset. They should be in ascending order and separated by a space. When multiple pieces have the same area, print it as many times as the number of the pieces. Sample Input 3 5 6 1 18 2 19 1 2 3 4 1 1 1 2 1 3 1 0 2 5 0 0 0 Sample Output 4 4 6 16 1 1 1 1 10

Problem Description Mark bought a huge cake, because his friend ray_sun’s birthday is coming. Mark is worried about how to divide the cake since it’s so huge and ray_sun is so strange. Ray_sun is a nut, you can never imagine how strange he was, is, and going to be. He does not eat rice, moves like a cat, sleeps during work and plays games when the rest of the world are sleeping……It is not a surprise when he has some special requirements for the cake. A considering guy as Mark is, he will never let ray_sun down. However, he does have trouble fulfilling ray_sun’s wish this time; could you please give him a hand by solving the following problem for him? The cake can be divided into n*m blocks. Each block is colored either in blue or red. Ray_sun will only eat a piece (consisting of several blocks) with special shape and color. First, the shape of the piece should be a rectangle. Second, the color of blocks in the piece should be the same or red-and-blue crisscross. The so called ‘red-and-blue crisscross’ is demonstrated in the following picture. Could you please help Mark to find out the piece with maximum perimeter that satisfies ray_sun’s requirements? Input The first line contains a single integer T (T <= 20), the number of test cases. For each case, there are two given integers, n, m, (1 <= n, m <= 1000) denoting the dimension of the cake. Following the two integers, there is a n*m matrix where character B stands for blue, R red. Output For each test case, output the cased number in a format stated below, followed by the maximum perimeter you can find. Sample Input 2 1 1 B 3 3 BBR RBB BBB Sample Output Case #1: 4 Case #2: 8
Cut the Cake 是怎么写的
Problem Description Today is the birthday of Mr. Bon Vivant, who is known as one of the greatest p鈚issiers in the world. Those who are invited to his birthday party are gourmets from around the world. They are eager to see and eat his extremely creative cakes. Now a large box-shaped cake is being carried into the party. It is not beautifully decorated and looks rather simple, but it must be delicious beyond anyone's imagination. Let us cut it into pieces with a knife and serve them to the guests attending the party. The cake looks rectangular, viewing from above (Figure C-1). As exemplified in Figure C-2, the cake will iteratively be cut into pieces, where on each cut exactly a single piece is cut into two smaller pieces. Each cut surface must be orthogonal to the bottom face and must be orthogonal or parallel to a side face. So, every piece shall be rectangular looking from above and every side face vertical. Figure C-1: The top view of the cake Figure C-2: Cutting the cake into pieces Piece sizes in Figure C-2 vary significantly and it may look unfair, but you don't have to worry. Those guests who would like to eat as many sorts of cakes as possible often prefer smaller pieces. Of course, some prefer larger ones. Your mission of this problem is to write a computer program that simulates the cutting process of the cake and reports the size of each piece. Input The input is a sequence of datasets, each of which is of the following format. n w d p1 s1 ... pn sn 　 The first line starts with an integer n that is between 0 and 100 inclusive. It is the number of cuts to be performed. The following w and d in the same line are integers between 1 and 100 inclusive. They denote the width and depth of the cake, respectively. Assume in the sequel that the cake is placed so that w and d are the lengths in the east-west and north-south directions, respectively. Each of the following n lines specifies a single cut, cutting one and only one piece into two. pi is an integer between 1 and i inclusive and is the identification number of the piece that is the target of the i-th cut. Note that, just before the i-th cut, there exist exactly i pieces. Each piece in this stage has a unique identification number that is one of 1, 2, ..., i and is defined as follows: * The earlier a piece was born, the smaller its identification number is. * Of the two pieces born at a time by the same cut, the piece with the smaller area (looking from above) has the smaller identification number. If their areas are the same, you may define as you like the order between them, since your choice in this case has no influence on the final answer. Note that identification numbers are adjusted after each cut. si is an integer between 1 and 1000 inclusive and specifies the starting point of the i-th cut. From the northwest corner of the piece whose identification number is pi, you can reach the starting point by traveling si in the clockwise direction around the piece. You may assume that the starting point determined in this way cannot be any one of the four corners of the piece. The i-th cut surface is orthogonal to the side face on which the starting point exists. The end of the input is indicated by a line with three zeros. Output For each dataset, print in a line the areas looking from above of all the pieces that exist upon completion of the n cuts specified in the dataset. They should be in ascending order and separated by a space. When multiple pieces have the same area, print it as many times as the number of the pieces. Sample Input 3 5 6 1 18 2 19 1 2 3 4 1 1 1 2 1 3 1 0 2 5 0 0 0 Sample Output 4 4 6 16 1 1 1 1 10
This Takes the Cake 怎么编写的呢
Description In the kingdom of Polygonia the royal family consists of the king, the queen, and the 10-year-old twins,Prince Obtuse and Prince Trisect. The twins are fiercely competitive, and on their birthday they always vie with each other for the biggest portion of the cake. The wise king and queen have devised the following way to prevent squabbles over the cake. One prince is allowed to cut the cake into two pieces, then the other prince gets to choose which of the two pieces he wants. Cakes in Polygonia are always in the shape of a convex quadrilateral (a four-sided polygon with each internal angle less than 180 degrees). Furthermore, local custom dictates that all cake cutting must be done using a straight cut that joins two vertices, or two midpoints of the sides of the cake, or a vertex and a midpoint. For instance, the following figure shows all the possible legal cuts in a typical cake. Your problem is to determine, for a number of different cakes, the best cut, i.e., the one that divides the cake into two pieces whose areas (we are disregarding the thickness of the cake) are as nearly equal as possible. For instance, given a cake whose vertices (when the cake is viewed from above) are located, in counterclockwise order, at the points (0, 1), (6, 0), (5, 2) and (2, 3), the best possible cut would divide the cake into two pieces, one with area 4.375, the other with area 5.125; the cut joins the points (1, 2) and (5,5,1) (the midpoints of two of the sides). Input Input consists of a sequence of test cases, each consisting of four (x, y) values giving the counterclockwise traversal of the cake's vertices as viewed from directly above the cake; the final test case is followed by a line containing eight zeros. No three points will be collinear, all quadrilaterals are convex, and all coordinates will have absolute values of 10000 or less. Output For each cake, the cake number followed by the two areas, smaller first, to three decimal places of precision. Sample Input 0 1 6 0 5 2 2 3 0 0 100 0 100 100 0 100 0 0 0 0 0 0 0 0 Sample Output Cake 1: 4.375 5.125 Cake 2: 5000.000 5000.000
This Takes the Cake 怎么来做的
Description In the kingdom of Polygonia the royal family consists of the king, the queen, and the 10-year-old twins,Prince Obtuse and Prince Trisect. The twins are fiercely competitive, and on their birthday they always vie with each other for the biggest portion of the cake. The wise king and queen have devised the following way to prevent squabbles over the cake. One prince is allowed to cut the cake into two pieces, then the other prince gets to choose which of the two pieces he wants. Cakes in Polygonia are always in the shape of a convex quadrilateral (a four-sided polygon with each internal angle less than 180 degrees). Furthermore, local custom dictates that all cake cutting must be done using a straight cut that joins two vertices, or two midpoints of the sides of the cake, or a vertex and a midpoint. For instance, the following figure shows all the possible legal cuts in a typical cake. Your problem is to determine, for a number of different cakes, the best cut, i.e., the one that divides the cake into two pieces whose areas (we are disregarding the thickness of the cake) are as nearly equal as possible. For instance, given a cake whose vertices (when the cake is viewed from above) are located, in counterclockwise order, at the points (0, 1), (6, 0), (5, 2) and (2, 3), the best possible cut would divide the cake into two pieces, one with area 4.375, the other with area 5.125; the cut joins the points (1, 2) and (5,5,1) (the midpoints of two of the sides). Input Input consists of a sequence of test cases, each consisting of four (x, y) values giving the counterclockwise traversal of the cake's vertices as viewed from directly above the cake; the final test case is followed by a line containing eight zeros. No three points will be collinear, all quadrilaterals are convex, and all coordinates will have absolute values of 10000 or less. Output For each cake, the cake number followed by the two areas, smaller first, to three decimal places of precision. Sample Input 0 1 6 0 5 2 2 3 0 0 100 0 100 100 0 100 0 0 0 0 0 0 0 0 Sample Output Cake 1: 4.375 5.125 Cake 2: 5000.000 5000.000
Cut the Cake 分蛋糕的问题
Problem Description Today is the birthday of Mr. Bon Vivant, who is known as one of the greatest p鈚issiers in the world. Those who are invited to his birthday party are gourmets from around the world. They are eager to see and eat his extremely creative cakes. Now a large box-shaped cake is being carried into the party. It is not beautifully decorated and looks rather simple, but it must be delicious beyond anyone's imagination. Let us cut it into pieces with a knife and serve them to the guests attending the party. The cake looks rectangular, viewing from above (Figure C-1). As exemplified in Figure C-2, the cake will iteratively be cut into pieces, where on each cut exactly a single piece is cut into two smaller pieces. Each cut surface must be orthogonal to the bottom face and must be orthogonal or parallel to a side face. So, every piece shall be rectangular looking from above and every side face vertical. Figure C-1: The top view of the cake Figure C-2: Cutting the cake into pieces Piece sizes in Figure C-2 vary significantly and it may look unfair, but you don't have to worry. Those guests who would like to eat as many sorts of cakes as possible often prefer smaller pieces. Of course, some prefer larger ones. Your mission of this problem is to write a computer program that simulates the cutting process of the cake and reports the size of each piece. Input The input is a sequence of datasets, each of which is of the following format. n w d p1 s1 ... pn sn 　 The first line starts with an integer n that is between 0 and 100 inclusive. It is the number of cuts to be performed. The following w and d in the same line are integers between 1 and 100 inclusive. They denote the width and depth of the cake, respectively. Assume in the sequel that the cake is placed so that w and d are the lengths in the east-west and north-south directions, respectively. Each of the following n lines specifies a single cut, cutting one and only one piece into two. pi is an integer between 1 and i inclusive and is the identification number of the piece that is the target of the i-th cut. Note that, just before the i-th cut, there exist exactly i pieces. Each piece in this stage has a unique identification number that is one of 1, 2, ..., i and is defined as follows: * The earlier a piece was born, the smaller its identification number is. * Of the two pieces born at a time by the same cut, the piece with the smaller area (looking from above) has the smaller identification number. If their areas are the same, you may define as you like the order between them, since your choice in this case has no influence on the final answer. Note that identification numbers are adjusted after each cut. si is an integer between 1 and 1000 inclusive and specifies the starting point of the i-th cut. From the northwest corner of the piece whose identification number is pi, you can reach the starting point by traveling si in the clockwise direction around the piece. You may assume that the starting point determined in this way cannot be any one of the four corners of the piece. The i-th cut surface is orthogonal to the side face on which the starting point exists. The end of the input is indicated by a line with three zeros. Output For each dataset, print in a line the areas looking from above of all the pieces that exist upon completion of the n cuts specified in the dataset. They should be in ascending order and separated by a space. When multiple pieces have the same area, print it as many times as the number of the pieces. Sample Input 3 5 6 1 18 2 19 1 2 3 4 1 1 1 2 1 3 1 0 2 5 0 0 0 Sample Output 4 4 6 16 1 1 1 1 10
Cut the Cake 怎么解决
Problem Description Today is the birthday of Mr. Bon Vivant, who is known as one of the greatest p鈚issiers in the world. Those who are invited to his birthday party are gourmets from around the world. They are eager to see and eat his extremely creative cakes. Now a large box-shaped cake is being carried into the party. It is not beautifully decorated and looks rather simple, but it must be delicious beyond anyone's imagination. Let us cut it into pieces with a knife and serve them to the guests attending the party. The cake looks rectangular, viewing from above (Figure C-1). As exemplified in Figure C-2, the cake will iteratively be cut into pieces, where on each cut exactly a single piece is cut into two smaller pieces. Each cut surface must be orthogonal to the bottom face and must be orthogonal or parallel to a side face. So, every piece shall be rectangular looking from above and every side face vertical. Figure C-1: The top view of the cake Figure C-2: Cutting the cake into pieces Piece sizes in Figure C-2 vary significantly and it may look unfair, but you don't have to worry. Those guests who would like to eat as many sorts of cakes as possible often prefer smaller pieces. Of course, some prefer larger ones. Your mission of this problem is to write a computer program that simulates the cutting process of the cake and reports the size of each piece. Input The input is a sequence of datasets, each of which is of the following format. n w d p1 s1 ... pn sn 　 The first line starts with an integer n that is between 0 and 100 inclusive. It is the number of cuts to be performed. The following w and d in the same line are integers between 1 and 100 inclusive. They denote the width and depth of the cake, respectively. Assume in the sequel that the cake is placed so that w and d are the lengths in the east-west and north-south directions, respectively. Each of the following n lines specifies a single cut, cutting one and only one piece into two. pi is an integer between 1 and i inclusive and is the identification number of the piece that is the target of the i-th cut. Note that, just before the i-th cut, there exist exactly i pieces. Each piece in this stage has a unique identification number that is one of 1, 2, ..., i and is defined as follows: * The earlier a piece was born, the smaller its identification number is. * Of the two pieces born at a time by the same cut, the piece with the smaller area (looking from above) has the smaller identification number. If their areas are the same, you may define as you like the order between them, since your choice in this case has no influence on the final answer. Note that identification numbers are adjusted after each cut. si is an integer between 1 and 1000 inclusive and specifies the starting point of the i-th cut. From the northwest corner of the piece whose identification number is pi, you can reach the starting point by traveling si in the clockwise direction around the piece. You may assume that the starting point determined in this way cannot be any one of the four corners of the piece. The i-th cut surface is orthogonal to the side face on which the starting point exists. The end of the input is indicated by a line with three zeros. Output For each dataset, print in a line the areas looking from above of all the pieces that exist upon completion of the n cuts specified in the dataset. They should be in ascending order and separated by a space. When multiple pieces have the same area, print it as many times as the number of the pieces. Sample Input 3 5 6 1 18 2 19 1 2 3 4 1 1 1 2 1 3 1 0 2 5 0 0 0 Sample Output 4 4 6 16 1 1 1 1 10
Cut the Cake 具体的编写
Problem Description Today is the birthday of Mr. Bon Vivant, who is known as one of the greatest p鈚issiers in the world. Those who are invited to his birthday party are gourmets from around the world. They are eager to see and eat his extremely creative cakes. Now a large box-shaped cake is being carried into the party. It is not beautifully decorated and looks rather simple, but it must be delicious beyond anyone's imagination. Let us cut it into pieces with a knife and serve them to the guests attending the party. The cake looks rectangular, viewing from above (Figure C-1). As exemplified in Figure C-2, the cake will iteratively be cut into pieces, where on each cut exactly a single piece is cut into two smaller pieces. Each cut surface must be orthogonal to the bottom face and must be orthogonal or parallel to a side face. So, every piece shall be rectangular looking from above and every side face vertical. Figure C-1: The top view of the cake Figure C-2: Cutting the cake into pieces Piece sizes in Figure C-2 vary significantly and it may look unfair, but you don't have to worry. Those guests who would like to eat as many sorts of cakes as possible often prefer smaller pieces. Of course, some prefer larger ones. Your mission of this problem is to write a computer program that simulates the cutting process of the cake and reports the size of each piece. Input The input is a sequence of datasets, each of which is of the following format. n w d p1 s1 ... pn sn 　 The first line starts with an integer n that is between 0 and 100 inclusive. It is the number of cuts to be performed. The following w and d in the same line are integers between 1 and 100 inclusive. They denote the width and depth of the cake, respectively. Assume in the sequel that the cake is placed so that w and d are the lengths in the east-west and north-south directions, respectively. Each of the following n lines specifies a single cut, cutting one and only one piece into two. pi is an integer between 1 and i inclusive and is the identification number of the piece that is the target of the i-th cut. Note that, just before the i-th cut, there exist exactly i pieces. Each piece in this stage has a unique identification number that is one of 1, 2, ..., i and is defined as follows: * The earlier a piece was born, the smaller its identification number is. * Of the two pieces born at a time by the same cut, the piece with the smaller area (looking from above) has the smaller identification number. If their areas are the same, you may define as you like the order between them, since your choice in this case has no influence on the final answer. Note that identification numbers are adjusted after each cut. si is an integer between 1 and 1000 inclusive and specifies the starting point of the i-th cut. From the northwest corner of the piece whose identification number is pi, you can reach the starting point by traveling si in the clockwise direction around the piece. You may assume that the starting point determined in this way cannot be any one of the four corners of the piece. The i-th cut surface is orthogonal to the side face on which the starting point exists. The end of the input is indicated by a line with three zeros. Output For each dataset, print in a line the areas looking from above of all the pieces that exist upon completion of the n cuts specified in the dataset. They should be in ascending order and separated by a space. When multiple pieces have the same area, print it as many times as the number of the pieces. Sample Input 3 5 6 1 18 2 19 1 2 3 4 1 1 1 2 1 3 1 0 2 5 0 0 0 Sample Output 4 4 6 16 1 1 1 1 10
Happy birthday
Problem Description Today is Gorwin’s birthday. So her mother want to realize her a wish. Gorwin says that she wants to eat many cakes. Thus, her mother takes her to a cake garden. The garden is splited into n*m grids. In each grids, there is a cake. The weight of cake in the i-th row j-th column is wij kilos, Gorwin starts from the top-left(1,1) grid of the garden and walk to the bottom-right(n,m) grid. In each step Gorwin can go to right or down, i.e when Gorwin stands in (i,j), then she can go to (i+1,j) or (i,j+1) (However, she can not go out of the garden). When Gorwin reachs a grid, she can eat up the cake in that grid or just leave it alone. However she can’t eat part of the cake. But Gorwin’s belly is not very large, so she can eat at most K kilos cake. Now, Gorwin has stood in the top-left grid and look at the map of the garden, she want to find a route which can lead her to eat most cake. But the map is so complicated. So she wants you to help her. Input Multiple test cases (about 15), every case gives n, m, K in a single line. In the next n lines, the i-th line contains m integers wi1,wi2,wi3,⋯wim which describes the weight of cakes in the i-th row Please process to the end of file. [Technical Specification] All inputs are integers. 1<=n,m,K<=100 1<=wij<=100 Output For each case, output an integer in an single line indicates the maximum weight of cake Gorwin can eat. Sample Input 1 1 2 3 2 3 100 1 2 3 4 5 6 Sample Output 0 16
Cut the Cake 代码的编写
Problem Description Today is the birthday of Mr. Bon Vivant, who is known as one of the greatest p鈚issiers in the world. Those who are invited to his birthday party are gourmets from around the world. They are eager to see and eat his extremely creative cakes. Now a large box-shaped cake is being carried into the party. It is not beautifully decorated and looks rather simple, but it must be delicious beyond anyone's imagination. Let us cut it into pieces with a knife and serve them to the guests attending the party. The cake looks rectangular, viewing from above (Figure C-1). As exemplified in Figure C-2, the cake will iteratively be cut into pieces, where on each cut exactly a single piece is cut into two smaller pieces. Each cut surface must be orthogonal to the bottom face and must be orthogonal or parallel to a side face. So, every piece shall be rectangular looking from above and every side face vertical. Figure C-1: The top view of the cake Figure C-2: Cutting the cake into pieces Piece sizes in Figure C-2 vary significantly and it may look unfair, but you don't have to worry. Those guests who would like to eat as many sorts of cakes as possible often prefer smaller pieces. Of course, some prefer larger ones. Your mission of this problem is to write a computer program that simulates the cutting process of the cake and reports the size of each piece. Input The input is a sequence of datasets, each of which is of the following format. n w d p1 s1 ... pn sn 　 The first line starts with an integer n that is between 0 and 100 inclusive. It is the number of cuts to be performed. The following w and d in the same line are integers between 1 and 100 inclusive. They denote the width and depth of the cake, respectively. Assume in the sequel that the cake is placed so that w and d are the lengths in the east-west and north-south directions, respectively. Each of the following n lines specifies a single cut, cutting one and only one piece into two. pi is an integer between 1 and i inclusive and is the identification number of the piece that is the target of the i-th cut. Note that, just before the i-th cut, there exist exactly i pieces. Each piece in this stage has a unique identification number that is one of 1, 2, ..., i and is defined as follows: * The earlier a piece was born, the smaller its identification number is. * Of the two pieces born at a time by the same cut, the piece with the smaller area (looking from above) has the smaller identification number. If their areas are the same, you may define as you like the order between them, since your choice in this case has no influence on the final answer. Note that identification numbers are adjusted after each cut. si is an integer between 1 and 1000 inclusive and specifies the starting point of the i-th cut. From the northwest corner of the piece whose identification number is pi, you can reach the starting point by traveling si in the clockwise direction around the piece. You may assume that the starting point determined in this way cannot be any one of the four corners of the piece. The i-th cut surface is orthogonal to the side face on which the starting point exists. The end of the input is indicated by a line with three zeros. Output For each dataset, print in a line the areas looking from above of all the pieces that exist upon completion of the n cuts specified in the dataset. They should be in ascending order and separated by a space. When multiple pieces have the same area, print it as many times as the number of the pieces. Sample Input 3 5 6 1 18 2 19 1 2 3 4 1 1 1 2 1 3 1 0 2 5 0 0 0 Sample Output 4 4 6 16 1 1 1 1 10

Problem Description Today is the birthday of Mr. Bon Vivant, who is known as one of the greatest p鈚issiers in the world. Those who are invited to his birthday party are gourmets from around the world. They are eager to see and eat his extremely creative cakes. Now a large box-shaped cake is being carried into the party. It is not beautifully decorated and looks rather simple, but it must be delicious beyond anyone's imagination. Let us cut it into pieces with a knife and serve them to the guests attending the party. The cake looks rectangular, viewing from above (Figure C-1). As exemplified in Figure C-2, the cake will iteratively be cut into pieces, where on each cut exactly a single piece is cut into two smaller pieces. Each cut surface must be orthogonal to the bottom face and must be orthogonal or parallel to a side face. So, every piece shall be rectangular looking from above and every side face vertical. Figure C-1: The top view of the cake Figure C-2: Cutting the cake into pieces Piece sizes in Figure C-2 vary significantly and it may look unfair, but you don't have to worry. Those guests who would like to eat as many sorts of cakes as possible often prefer smaller pieces. Of course, some prefer larger ones. Your mission of this problem is to write a computer program that simulates the cutting process of the cake and reports the size of each piece. Input The input is a sequence of datasets, each of which is of the following format. n w d p1 s1 ... pn sn 　 The first line starts with an integer n that is between 0 and 100 inclusive. It is the number of cuts to be performed. The following w and d in the same line are integers between 1 and 100 inclusive. They denote the width and depth of the cake, respectively. Assume in the sequel that the cake is placed so that w and d are the lengths in the east-west and north-south directions, respectively. Each of the following n lines specifies a single cut, cutting one and only one piece into two. pi is an integer between 1 and i inclusive and is the identification number of the piece that is the target of the i-th cut. Note that, just before the i-th cut, there exist exactly i pieces. Each piece in this stage has a unique identification number that is one of 1, 2, ..., i and is defined as follows: * The earlier a piece was born, the smaller its identification number is. * Of the two pieces born at a time by the same cut, the piece with the smaller area (looking from above) has the smaller identification number. If their areas are the same, you may define as you like the order between them, since your choice in this case has no influence on the final answer. Note that identification numbers are adjusted after each cut. si is an integer between 1 and 1000 inclusive and specifies the starting point of the i-th cut. From the northwest corner of the piece whose identification number is pi, you can reach the starting point by traveling si in the clockwise direction around the piece. You may assume that the starting point determined in this way cannot be any one of the four corners of the piece. The i-th cut surface is orthogonal to the side face on which the starting point exists. The end of the input is indicated by a line with three zeros. Output For each dataset, print in a line the areas looking from above of all the pieces that exist upon completion of the n cuts specified in the dataset. They should be in ascending order and separated by a space. When multiple pieces have the same area, print it as many times as the number of the pieces. Sample Input 3 5 6 1 18 2 19 1 2 3 4 1 1 1 2 1 3 1 0 2 5 0 0 0 Sample Output 4 4 6 16 1 1 1 1 10
This Takes the Cake
In the kingdom of Polygonia the royal family consists of the king, the queen, and the 10-year-old twins, Prince Obtuse and Prince Trisect. The twins are fiercely competitive, and on their birthday they always vie with each other for the biggest portion of the cake. The wise king and queen have devised the following way to prevent squabbles over the cake. One prince is allowed to cut the cake into two pieces, then the other prince gets to choose which of the two pieces he wants. ![](http://acm.zju.edu.cn/onlinejudge/showImage.do?name=0000%2F1806%2F1806.gif) Cakes in Polygonia are always in the shape of a convex quadrilateral (a four-sided polygon with each internal angle less than 180 degrees). Furthermore, local custom dictates that all cake cutting must be done using a straight cut that joins two vertices, or two midpoints of the sides of the cake, or a vertex and a midpoint. For instance, the following figure shows all the possible legal cuts in a typical cake. Your problem is to determine, for a number of different cakes, the best cut, i.e., the one that divides the cake into two pieces whose areas (we are disregarding the thickness of the cake) are as nearly equal as possible. For instance, given a cake whose vertices (when the cake is viewed from above) are located, in counterclockwise order, at the points (0, 1), (6, 0), (5, 2) and (2, 3), the best possible cut would divide the cake into two pieces, one with area 4.375, the other with area 5.125; the cut joins the points (1, 2) and (5:5, 1) (the midpoints of two of the sides). Input Input consists of a sequence of test cases, each consisting of four (x; y) values giving the counterclockwise traversal of the cake's vertices as viewed from directly above the cake; the final test case is followed by a line containing eight zeros. No three points will be collinear, all quadrilaterals are convex, and all coordinates will have absolute values of 10000 or less. Output For each cake, the cake number followed by the two areas, smaller first, to three decimal places of precision. Sample Input 0 1 6 0 5 2 2 3 0 0 100 0 100 100 0 100 0 0 0 0 0 0 0 0 Sample Output Cake 1: 4.375 5.125 Cake 2: 5000.000 5000.000
Cut the Cake
Problem Description Today is the birthday of Mr. Bon Vivant, who is known as one of the greatest p鈚issiers in the world. Those who are invited to his birthday party are gourmets from around the world. They are eager to see and eat his extremely creative cakes. Now a large box-shaped cake is being carried into the party. It is not beautifully decorated and looks rather simple, but it must be delicious beyond anyone's imagination. Let us cut it into pieces with a knife and serve them to the guests attending the party. The cake looks rectangular, viewing from above (Figure C-1). As exemplified in Figure C-2, the cake will iteratively be cut into pieces, where on each cut exactly a single piece is cut into two smaller pieces. Each cut surface must be orthogonal to the bottom face and must be orthogonal or parallel to a side face. So, every piece shall be rectangular looking from above and every side face vertical. Figure C-1: The top view of the cake Figure C-2: Cutting the cake into pieces Piece sizes in Figure C-2 vary significantly and it may look unfair, but you don't have to worry. Those guests who would like to eat as many sorts of cakes as possible often prefer smaller pieces. Of course, some prefer larger ones. Your mission of this problem is to write a computer program that simulates the cutting process of the cake and reports the size of each piece. Input The input is a sequence of datasets, each of which is of the following format. n w d p1 s1 ... pn sn 　 The first line starts with an integer n that is between 0 and 100 inclusive. It is the number of cuts to be performed. The following w and d in the same line are integers between 1 and 100 inclusive. They denote the width and depth of the cake, respectively. Assume in the sequel that the cake is placed so that w and d are the lengths in the east-west and north-south directions, respectively. Each of the following n lines specifies a single cut, cutting one and only one piece into two. pi is an integer between 1 and i inclusive and is the identification number of the piece that is the target of the i-th cut. Note that, just before the i-th cut, there exist exactly i pieces. Each piece in this stage has a unique identification number that is one of 1, 2, ..., i and is defined as follows: * The earlier a piece was born, the smaller its identification number is. * Of the two pieces born at a time by the same cut, the piece with the smaller area (looking from above) has the smaller identification number. If their areas are the same, you may define as you like the order between them, since your choice in this case has no influence on the final answer. Note that identification numbers are adjusted after each cut. si is an integer between 1 and 1000 inclusive and specifies the starting point of the i-th cut. From the northwest corner of the piece whose identification number is pi, you can reach the starting point by traveling si in the clockwise direction around the piece. You may assume that the starting point determined in this way cannot be any one of the four corners of the piece. The i-th cut surface is orthogonal to the side face on which the starting point exists. The end of the input is indicated by a line with three zeros. Output For each dataset, print in a line the areas looking from above of all the pieces that exist upon completion of the n cuts specified in the dataset. They should be in ascending order and separated by a space. When multiple pieces have the same area, print it as many times as the number of the pieces. Sample Input 3 5 6 1 18 2 19 1 2 3 4 1 1 1 2 1 3 1 0 2 5 0 0 0 Sample Output 4 4 6 16 1 1 1 1 10
Java学习的正确打开方式

linux系列之常用运维命令整理笔录

Python十大装B语法
Python 是一种代表简单思想的语言，其语法相对简单，很容易上手。不过，如果就此小视 Python 语法的精妙和深邃，那就大错特错了。本文精心筛选了最能展现 Python 语法之精妙的十个知识点，并附上详细的实例代码。如能在实战中融会贯通、灵活使用，必将使代码更为精炼、高效，同时也会极大提升代码B格，使之看上去更老练，读起来更优雅。

2019年11月中国大陆编程语言排行榜
2019年11月2日，我统计了某招聘网站，获得有效程序员招聘数据9万条。针对招聘信息，提取编程语言关键字，并统计如下： 编程语言比例 rank pl_ percentage 1 java 33.62% 2 cpp 16.42% 3 c_sharp 12.82% 4 javascript 12.31% 5 python 7.93% 6 go 7.25% 7 p...

《奇巧淫技》系列-python！！每天早上八点自动发送天气预报邮件到QQ邮箱

SQL-小白最佳入门sql查询一

Nginx 原理和架构
Nginx 是一个免费的，开源的，高性能的 HTTP 服务器和反向代理，以及 IMAP / POP3 代理服务器。Nginx 以其高性能，稳定性，丰富的功能，简单的配置和低资源消耗而闻名。 Nginx 的整体架构 Nginx 里有一个 master 进程和多个 worker 进程。master 进程并不处理网络请求，主要负责调度工作进程：加载配置、启动工作进程及非停升级。worker 进程负责处...
【图解经典算法题】如何用一行代码解决约瑟夫环问题

“狗屁不通文章生成器”登顶GitHub热榜，分分钟写出万字形式主义大作

《程序人生》系列-这个程序员只用了20行代码就拿了冠军

11月8日，由中国信息通信研究院、中国通信标准化协会、中国互联网协会、可信区块链推进计划联合主办，科技行者协办的2019可信区块链峰会将在北京悠唐皇冠假日酒店开幕。 　　区块链技术被认为是继蒸汽机、电力、互联网之后，下一代颠覆性的核心技术。如果说蒸汽机释放了人类的生产力，电力解决了人类基本的生活需求，互联网彻底改变了信息传递的方式，区块链作为构造信任的技术有重要的价值。 　　1...
Python 植物大战僵尸代码实现(2):植物卡片选择和种植

Java世界最常用的工具类库
Apache Commons Apache Commons有很多子项目 Google Guava 参考博客