Description

A. Definition of Max-Heap

A heap is a complete binary tree.

A max-heap is a complete binary tree in which the value in each internal node is greater
than or equal to the values in the children of that node.

B. Implementation of the Max-Heap Data Structure

1. Array:

An approach to store a max-heap is to use a single, contiguous block of memory cells, i.e., an array, for the entire tree. We store the tree’s root node in the first cell of the array. (Note that, for ease of implementation, we ignore the 0th cell and start from the 1st cell.) Then we store the left child of the root in the second cell, store the right child of the root in the third cell, and in general, continue to store the left and right children of the node found in cell n in the cells 2n and 2n+1 respectively. With this technique, the tree shown below

would be stored as follows

2. Linked list:

We set a special memory location, call a root pointer, where we store the address of the root node. Then each node in the tree must be set to point to the parent and left or right child of the pertinent node or assigned the NULL value if there are no more nodes in that direction of the tree.

C. Method to push/pop an element

1. PUSH 

• put the new element in the last place of the heap.
• compare with the parent, swap them until the parent is greater or equal to the new element. 
• example: push 11 to this heap
• 
• 
• 
• 
• 
• 
• 

2. POP

• put the last element to the top(root) of the heap.
• compare with the greater child, swap them until all child is smaller than it. 
• example: 
• 
• 
• 
• 
• 
• 
• 
• 

REQUIREMENTS:

Implement the constructor, push(), max(), pop() member functions of both the Array_MAX_HEAP and List_MAX_HEAP classes and deleteTree() of List_MAX_HEAP class.

Hint

For easy to solve this problem, you can call findparent(int cnt, ListNode *root) to return a ListNode which is the parent of node[cnt] in List_MAX_HEAP class.

Input

The first line contains an integer n.

Each of the next n lines has an instruction.

The instruction will be either:

• A_push: push a new element a_i into the array_max_heap.
• L_push: push a new element a_i into the list_max_heap.
• max: show the max element. if the max-heap is empty, print -1.
• A_pop: show and pop the max element in the array_max_heap. if the max-heap is empty, print -1.
• L_pop: show and pop the max element in the list_max_heap. if the max-heap is empty, print -1.
• size: show the size of the heap.

For all testcase:

1 <= n <= 1000, 0 <= a_i < 2³¹

(2/6) only A_push, L_push or size instruction

(2/6) only A_push, L_push, size or max instruction

(2/6) contains all instruction

Output

For max, A_pop or L_pop instruction, print the max element in the heap.

For size instruction, print the size of the heap.

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Mixed nuts, especially peanuts, has always been Anya's favorite snack. They come in various shapes and sizes: cubes, cuboids, spheres, cones, and cylinders, each with their own unique taste and texture.

However, Anya got poor grades in her math class, and she struggles to acquire the Stella Stars needed for Loid's secret mission -- to get closer to Donovan Desmond and uncover his scheme.

To help Anya on her schoolwork, Loid decided to teach her the basics of geometry with the shapes of mixed nuts. Given several nuts of different shapes and sizes, Loid wants Anya to calculate total volume of the nuts. Since Anya has the ability to read other people's minds, she can easily read the volume formula for each shape straight from Loid's mind. However, she is not familiar with the calculations, so she needs your help to build a program that can calculate the volume of the nuts.

The volume of a nut can be calculated using the following formulas:

• Cube: $V = s^3$, where $s$ is the side length of the cube.
• Cuboid: $V = l \times w \times h$, where $l$, $w$, and $h$ are the length, width, and height of the cuboid, respectively.
• Sphere: $V = \frac{4}{3} \pi r^3$, where $r$ is the radius of the sphere.
• Cone: $V = \frac{1}{3} \pi r^2 h$, where $r$ is the radius of the base, and $h$ is the height of the cone.
• Cylinder: $V = \pi r^2 h$, where $r$ is the radius of the base, and $h$ is the height of the cylinder.

Given a base class Nut, implement the derived classes CubeNut, CuboidNut, SphereNut, ConeNut, and CylinderNut that represent the shapes of mixed nuts. You should use setVolume to set the corresponding volume of each nut on construction.

Hints

• Be careful that the type of volume is double, and 4/3=1 is of type int.
• You only need to implement the constructor of each derived class.
• Note that CubeNut inherits from CuboidNut instead of Nut.
• Use oj::Nut::PI as your $\pi$ in the calculation.

Input

This is a partial judge problem, input and output are handled by main.cpp.

For each line of input, you will be given a string shape, followed by the corresponding parameters for the shape. The parameters are separated by a single space, and the order of the parameters is as follows:

• Cube: $s$ (side length)
• Cuboid: $l , w , h$ (length, width, height)
• Sphere: $r$ (radius)
• Cone: $r , h$ (radius, height)
• Cylinder: $r , h$ (radius, height)

You should do some basic check: if the input is illegal (e.g. length < 0), then the volume should be 0. Also, you need to consider the scenario like Cuboid -1 -2 3, where volume would be 0 instead of 6.

Constraints

• $\text{|s|, |l|, |w|, |h|, |r|} \leq 1000$
• $\text{s, l, w, h, r}$ are presented in decimal format with at most 4 decimal places.
• $0 \leq \text{# of shapes} \leq 1000$
• Result is within the range of double.

Output

This is a partial judge problem, input and output are handled by main.cpp.

Output the total volume of the nuts, rounded to 4 decimal places.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

You are on your way to attend Lab 5 of Introduction to Programming 2, and you saw a cat on the side of the road.

It noticed that you are late, and started singing to taunt you:

"Hachimi Chimichi, Ashiga Ga Ashi, MAMBOW! MAMBOW! MA-MAMBOOO, ting ting tung tung ting ting ting ting tung tung ting, HAAAAAAACHIMIIIIIII..."

You are furious, and decided to have a battle with the Hachimi cat. You take out your backpack, randomly pick up things and start throwing them at the cat. Each item hits differently — and some have special effects.

Each item has a use() which first calls damage(), then applies its effect. damage() checks if weight > defense — if so, it deals weight - defense damage to HP, otherwise it is blocked. The effect always applies after damage(), regardless of whether the hit was blocked. The battle ends early if Hachimi's HP reaches 0.

ID 0 — Laptop(int weight, int power) HP is lowered by power.

ID 1 — Notebook(int weight, int notes) Hachimi is scared of knowledge — defense is lowered by notes.

ID 2 — GPU(int weight) Hachimi feels heartbroken seeing an expensive GPU smashed — HP is lowered by current defense.

ID 3 — Shoe(int weight, int smell) The stench is unbearable — both HP and defense are reduced by smell.

Implement the constructor and use() for each derived class, as well as damage() on the base class Item. HP and defense cannot go below 0.

The constraints are as follows: 1 ≤ hp ≤ 1000, 1 ≤ defense ≤ 100, 1 ≤ n ≤ 50, 1 ≤ weight ≤ 50, 1 ≤ power ≤ 30, 1 ≤ notes ≤ 20, 1 ≤ smell ≤ 100.

Input

The first line contains hp, defense, and n. The following n lines each contain an item ID followed by its arguments.

Output

For each item, print the class name followed by hit or blocked, then on the next line print HP: <hp>, Defense: <defense>. Stop if Hachimi's HP reaches 0.

100 10 7
0 15 20           // Laptop, weight=15, power=20
1 12 4            // Notebook, weight=12, notes=4
2 20              // GPU, weight=20
1 5 3             // Notebook, weight=5 — blocked since weight < defense
3 18 5            // Shoe, weight=18, smell=5
0 20 30           // Laptop, weight=20, power=30 — Hachimi dies here
2 7               // GPU — never reached

Laptop hit
HP: 75, Defense: 10
Notebook hit
HP: 73, Defense: 6
GPU hit
HP: 53, Defense: 6
Notebook blocked
HP: 53, Defense: 3
Shoe hit
HP: 33, Defense: 0
Laptop hit
HP: 0, Defense: 0

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

// You cannot see what's inside. You can only use what's declared here.

Term* evaluate(const Term* t);

Input

The first line contains n. Each of the following n lines is an expression. An expression is either a bare integer, a bare name, or a name followed by a comma separated list of sub-expressions in parentheses:

• add(1)
• add(1, 2)
• add(1, 2, x, 4)
• mul(add(1, x), sub(3, 4))

Output

One line of evaluated result per query

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss