Description

A stack is an abstract data type that serves as a collection of elements, where a node can be added to a stack and removed from a stack only at its top. Two principal operations can be used to manipulate a stack: push, which adds an element at the top, and pop, which removes the element at the top of the collection.

Let’s see how the stack data structure can be realized in C++.We have an approach to implement stack: linked list. Thus, we define a class as follows:

class List_stack {

    public:

        List_stack();

        ~List_stack();

        void push(const int &);

        void pop();

        void print();

    private:

        ListNode *head;

        ListNode *tail;

};

where List_stack implements the stack data structure

REQUIREMENTS:

Implement the constructor, destructor, push(), pop() and print() member functions of List_stack classes.

Note:

1.This problem involves three files.

• function.h: Class definitions.
• function.cpp: Member-function definitions.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

function.h

#ifndef FUNCTION_H #define FUNCTION_H #include <iostream> class ListNode { friend class List_stack; //make List_stack a friend public: ListNode( const int &info ) //constructor : data( info ), nextPtr( NULL ), prevPtr( NULL ) { } //end ListNode constructor private: int data; //data ListNode *nextPtr; // next node in list ListNode *prevPtr; }; //end class ListNode class List_stack { public: List_stack(); ~List_stack(); void push(const int &); void pop(); void print(); private: ListNode *head; ListNode *tail; }; #endif // FUNCTION_H

main.cpp

#include<iostream> #include<string.h> #include "function.h" using namespace std; int main(){ List_stack L_stack; char command[10]; int n; while(cin>>command){ if(strcmp(command,"pop")==0){ L_stack.pop(); }else if(strcmp(command,"push")==0){ cin >> n; L_stack.push(n); }else if(strcmp(command, "print") == 0){ L_stack.print(); cout << endl; } } return 0; }

2.For OJ submission:

       Step 1. Submit only your function.cpp into the submission block.

       Step 2. Check the results and debug your program if necessary.

Input

There are three kinds of commands:

• “push integerA” represents adding an element with int value A at the top of the stack.
• “pop “ represents removing the element at the top of the stack.
• “print” represents showing the current content of the stack.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output should consist of the current state of the stack.

When the stack is empty, you don’t need to print anything except a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

In this problem, you are asked to implement a class Matrix that represents a $N\times N$ Matrix.

Following are the methods you should implement:

1. add A.add(B) → $A = A+B$
2. subtract A.subtract(B) → $A = A-B$
3. multiply A.multiply(B) → $A = AB$
4. transpose A.transpose() → $A = A^{\top}$
5. power A.power(x) → $\underbrace{AA \dots AA}_{\times x}$

Usefull links

Power of matrix:

Reference

Input

The first line contains two integers $N$, $T$, representing the size of the matrix and the number of the operations.

Following are $N$ lines, each line contains $N$ integers, representing the element in the starting matrix.

Following are $T$ operations, each operation start with an interger $o$, representings the type of the operation.

For operation type 1, 2, 3, interger $o$ is followed by $N\times N$ numbers, representing the element in the operand matrix.

For operation type 5, interger $o$ is followed by an interger $x$, repersentings $x$-th power.

Constraints

• $1 \leq N \leq 10$
• $1 \leq T \leq 1000$
• $o = {1,2,3,4,5}$
• $1 \leq x \leq 1e6$
• All numbers would not exceed the range of long long.

Subtask

1. (Testcases 1-6) $o = {1,2,3,4}$
2. (Testcases 7-8) $1 \leq x \leq 5$
3. (Testcases 9-10) No additional constraints.

Output

Output the final result of the matrix.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

SpongeBob is hungry while waiting bus that can take him leave this weird place. However, he doesn't have that much money to buy food from the vending machine since he needs to use it for taking the bus. Now you are the vending machine that sells kandy to SpongeBob. You always prioritizes selling the cheapest item currently available in your storage so SpongeBob won't be broken. As a machine, you have two operations:

1. store <price>: Add an item with a given price (integer) into the vending machine.

2. sell: Sell the item with the lowest price currently in the machine. If the machine is empty, ignore this command.

Please implement the functions in the code, so SpongeBob can receive kandy from you.

Constraints

• number of operations <= 2 * 10⁶.
• price <= 10⁹.

Hint: For the more efficient way to sell the cheapest kandy, you may refer to this link:

https://www.geeksforgeeks.org/dsa/introduction-to-min-heap-data-structure/

Also please note that you CANNOT use STL to solve this problem.

Input

A sequence of commands (store <num> or sell).

Output

A single line containing two integers separated by a space:

1. The total number of items sold.

2. The total revenue with '\n'.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Welcome back to this question, again, but in C++ programming language. In this problem, you are tasked to solve this question in C++ and familiarize the C++ syntax.

Katsura (It’s not Zura, it’s Katsura!) and Elizabeth are holding a street rap concert. A massive, single queue of $N$ fans has formed.

However, Katsura made a rule. He decides that the fan at the very front of the line should enter with the fan at the very back of the line. Then, the second person in line should enter with the second-to-last person, and so on.

Given a singly linked list representing the queue $L_0 \to L_1 \to \dots \to L_{n-2} \to L_{n-1}$, you must reorder it into: $L_0 \to L_{n-1} \to L_1 \to L_{n-2} \to L_2 \to L_{n-3} \dots$

There is a restriction: You can only modify the “next” pointer of each node to change the order. If you attempt to modify the node values or return a list containing nodes whose addresses do not belong to the original list, you may receive a wrong answer.

Compiler Option: C++11 or above.

Further Reading

C++ I/O Streams:

• std::cin - Standard input stream
• std::cout - Standard output stream
• I/O Performance Optimization - Why sync_with_stdio(false) and cin.tie(NULL) matter

Modern C++ Features:

• nullptr - Type-safe null pointer constant (vs NULL macro)
• new/delete - Dynamic memory allocation in C++
• struct declaration - No typedef needed in C++
• namespaces - Organizing code and preventing naming conflicts (uses street address analogy)

General C++ Reference:

• cppreference - Comprehensive C++ reference

Some differences from C to C++ in this problem:

function.h

-4  typedef struct ListNode_ {
+4  struct ListNode {
-6      struct ListNode_* next;
+6      struct ListNode* next;
-7  } ListNode;
+7  };

main.c -> main.cpp

-2  #include <stdio.h>
+2  #include <iostream>

// static ListNode* newNode(int val)
-8  ListNode* ret = malloc(sizeof(ListNode));
-10 ret->next = NULL;
+6  ListNode* ret = new ListNode();
+9  ret->next = nullptr;
// Similar NULL->nullptr changes at lines: 20->23, 21->24, 25->28, 31->34, 46->49, 50->53, 55->58, 61->64

// int main(void)
+15 // a common practice for better I/O performance
+16 std::ios_base::sync_with_stdio(false);
+17 std::cin.tie(NULL);

// input line 1
-18 scanf("%d", &N);
+21 std::cin >> N;
// Similar scanf->cin change at line 25->28

-49     printf("%d", curr->value);
-51         printf(" ");
+52     std::cout << curr->value;
+54         std::cout << " ";
// Similar printf->cout changes at lines: 55->58

// cleanup
-64     free(tmp);
+67     delete tmp;

Constraints:

• $1 \le N \le 10^5$ 
• $-10^9 \le Node.value \le 10^9$

Input

Line 1: $N$, the total number of fans in the queue.
Line 2: $N$ integers representing the values of the fans in order.

Output

Line 1: The values of the fans in the final folded queue, separated by a single space, ending with \n.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss