Yesterday, I have decided to make an account in codeforeces.com and to check how the system works. Pretty much quite well, in 90 minutes I have managed to solve 2 of the 5 problems:
I have decided to stop, because for the 3 next problems I needed better understanding in data structures. Furthermore, I do not think that I would have managed to do them in just 30 minutes, which were left.
Problem 1
Thus, let’s start with the first problem. The whole description is here. These are the sample tests:
|
1 2 3 4 |
6 1 5 2 6 3 7 |
|
1 |
1 2 3 |
|
1 2 3 4 |
10 1 2 1 3 1 5 |
|
1 |
2 3 5 |
Thus, what I did to solve it? Pretty much, once you read the solution and cast to integer where needed, you have half of the solution. The next is just to check whether you can assign how many first degrees can you assign, after assigning the minimal second and third degrees. If you have reached your limit, then you simply assign more second degrees and more third degrees. As easy as that, but this is just the first problem:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
int_total_diplomas = int(input()) degree_1 = list(map(int, list(input().split()))) degree_2 = list(map(int, list(input().split()))) degree_3 = list(map(int, list(input().split()))) min_degree_1 = degree_1[0] max_degree_1 = degree_1[1] min_degree_2 = degree_2[0] max_degree_2 = degree_2[1] min_degree_3 = degree_3[0] max_degree_3 = degree_3[1] degree_1_total = min_degree_1 degree_2_total = min_degree_2 degree_3_total = min_degree_3 def calculate_diplomas(int_total_diplomas,degree_1_total,degree_2_total, degree_3_total,max_degree_1,max_degree_2): if int_total_diplomas <= degree_2_total + degree_3_total + max_degree_1: degree_1_total = int_total_diplomas - degree_2_total - degree_3_total print(degree_1_total,degree_2_total,degree_3_total) return else : degree_1_total = max_degree_1 if int_total_diplomas <= degree_1_total + degree_3_total + max_degree_2: degree_2_total = int_total_diplomas - degree_1_total - degree_3_total print(degree_1_total,degree_2_total,degree_3_total) return else: degree_2_total = max_degree_2 degree_3_total = int_total_diplomas - degree_2_total - degree_1_total print(degree_1_total,degree_2_total,degree_3_total) return calculate_diplomas(int_total_diplomas,degree_1_total,degree_2_total, degree_3_total,max_degree_1,max_degree_2) |
Problem 2
The second problem is more fun. Its description is here. The idea is to distribute as much tea as possible to a group of people, having in mind that the girls should have half of the boys tea. The tea in the cups of each girl should be equal to each other and the same goes for the boys tea. The number of boys is the same as the number of girls.
Until now the problem seems trivial – you simply divide the whole amount by 1.5 times the number of boys and girls and you give them water. As simple as that! But this is not the case. The owner of the party has different cup sizes. Thus, this makes the problem a little more difficult 🙂
What I did? I have sorted the cups. Let’s imagine, that we have 6 cups and they have the following size in millilitres – 150, 200, 200, 400,500,1000.
The smallest cup is 150 and it goes to a girl. We have 3 girls and 3 boys. The smallest boy’s cup is 400. These are selected, because with them every boy and every girl can have the same amount of tea. The point is that 150*2 is smaller than 400, which means that the boys should not have more than 300 ml of tea each.
Assuming, that we have unlimited value of tea, our answer should be 150*number_of_girls * 3. Anyhow, this is not the case in the task – our value is limited to the one in the teapot. Thus, I have taken it into account at the beginning, assuming that the max_tea_per_girl = total_teapot/(3*total_boys). At a later stage I reduce the maximum with the constrains given from the smallest_boy_cup and smallest_boy_cup.
Pretty much that is all! 🙂
Here comes the code, it would be probably easier if you run it once or twice to get the whole idea:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
friends_and_teapotsize = list(map(int, list(input().split()))) cup_size = list(map(int, list(input().split()))) total_boys = friends_and_teapotsize[0] total_teapot = friends_and_teapotsize[1] cup_size.sort(reverse=False) smallest_girl_cup = cup_size[0] smallest_boy_cup = cup_size[total_boys] tea_per_girl = 0 if smallest_girl_cup*2 < smallest_boy_cup: smallest_boy_cup = smallest_girl_cup*2 if smallest_girl_cup*2 > smallest_boy_cup: smallest_girl_cup = smallest_boy_cup/2 max_tea_per_girl = total_teapot/(3*total_boys) if max_tea_per_girl > smallest_girl_cup: max_tea_per_girl = smallest_girl_cup if max_tea_per_girl > smallest_boy_cup/2: max_tea_per_girl = smallest_boy_cup/2 result = max_tea_per_girl * total_boys * 3 print(result) |
Thank you and enjoy the code! 😀