| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10690 | Fill the Boxes 2 |
|
| 10691 | Simply Fractions 2 |
|
| 10692 | Parentheses with Precedence |
|
| 10693 | K Characters with Paddings |
|
| 10694 | Another Sample Input/Output for 10693 |
|
| 10695 | Binary Addition 2 |
|
| 10696 | I2P(II)2015 final exam Cheatsheet |
|
Description
Assume that we need to send a stream of data items as a series of packets. The size limit of a packet is M, and each item i has a size s_i satisfying s_i < M, for i = 1, 2, ....N
For each item i, we can append it to the current packet as long as the total size of the items in the packet does not exceed the limit; otherwise, we put the item into a new packet.
Our task is to simulate the process and decide how many packets are needed.
Case1: 0<M<=1*102, 0<=N<=20
Case2: 0<M<=2*104, 0<=N<=100
Case3: 0<M<=1*105, 0<=N<=10000
Case4: 0<M<=2*109, 0<=N<=10000
Input
The input consists of several test cases.
Each test case starts with an integer M indicating the size limit of a packet.
The subsequent positive integers enumerate the sizes of the items, and a number 0 denotes the end of the current stream.
Output
The output contains several lines.
Each line prints the number of packets needed to send the stream for the corresponding test case.
Each line is ended with a newline character.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given several fractions, compute their sum and express the answer in the simplest fraction form.
Input
There are many test cases in one subtask.
The first line of each test case contains an integer t, which indicates the number of fractions in the input. Each of the following t lines contains two integers a and b, which represent the numerator and the denominator of a fraction.
subtask 1 : t=2. 1<=a,b<=10.
subtask 2 : t<=5. 1<=a,b<=10.
subtask 3 : t<=5. 1<=a,b<=50.
subtask 4 : t<=10. 1<=a,b<=100.
Output
Each test case outputs one line.
Namely, you need to add '\n' at the end of each line.
The output is the sum reduced to the simplest fraction form. You need to print a '/' between the numerator and the denominator.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A string is said to be valid if it satisfies one of the following rules:
(1) The string is an empty string.
(2) If strings S1 and S2 are both valid, then S1S2 is valid.
(3) If a string S is valid, then {S}, [S], (S) and <S> are valid as long as S does not contain any parentheses with higher precedence than its enclosing parentheses. The precedence order of parentheses from high to low is { }, [ ], ( ), < >. Therefore, a string of {[]()} is valid, but a string of {([])} is not.
Given a string consisting of parentheses, determine if it is a valid string.
Input
The first line of the input contains an integer N (N ≤ 10000) denoting the number of test cases. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length is no more than 1000 characters.
Note that an empty string (a line which contains the newline character only) may be present in the input and it should be considered as a valid string according to rule (1).
Subtask 1: N≤50
Subtask 2: N≤100
Subtask 3: N≤1000
Subtask 4: N≤10000
Output
For each test case, print “Yes” or “No” to indicate that the string is valid or not and a newline in the end of each line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a string S, output all different possible set of K characters in the string with P paddings. And sort them in the dictionary order. A padding is expressed as an underline '_'.
For example, if K=2 and P=1, and the given string S is ‘CDBABBD’, the output would be
_AB
_AC
_AD
_BB
_BC
_BD
_CD
_DD
A_B
A_C
A_D
AB_
AC_
AD_
B_B
B_C
B_D
BB_
BC_
BD_
C_D
CD_
D_D
DD_
Input
The first line of input contains a positive integer T (T <= 30), which indicates the number of test cases. For each case, there is a string S, a positive integer K, and a nonnegative integer P in a line. The length of the S is less than or equal to 100 and S contains only 'A'-'J'; The number K, less than or equal to 10, indicates the length of substrings.
For test 1: T <= 10, K <= 3, P <= 1, |S| <=10
For test 2: T <= 15, K <= 5, P <= 1, |S| <=25
For test 3: T <= 20, K <= 8, P <= 2, |S| <=50
For test 4: T <= 30, K <= 10, P <= 3, |S| <=100
T, K, |S| are all positive integers, P is a nonnegative integer, and K <= |S| for all test cases.
Output
For each test case, print all different possible sets of K characters in the string. And sort them in the dictionary order, one substring per line. Print a blank line after each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Please compute the sum of two given n-bit binary numbers.
Input
The first line of the input file contains a positive integer t indicating the number of test cases. The first line of each test case is a positive integer n denoting the length of bits. The second and third lines are the two n-bit binary numbers. The first bit of each binary number is always 0, which guarantees that the sum of the two binary numbers can still be expressed as an n-bit binary number.
Case1 : t<=100, n<=100
Case2 : t<=200, n<=1000
Case3 : t<=300, n<=5000
Case4 : t<=400, n<=10000
Output
For each test case, your program should print the sum in the same format as the binary numbers given in input.
Notice that each answer is ended with a newline character.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
1. How to make cin faster?
std::ios_base::sync_with_stdio(false);
2. An example of using <vector>
#include <iostream>
#include <vector>
#include <algorithm> // sort
int main ()
{
std::vector<int> V;
int x;
while (std::cin>>x) {
V.push_back(x);
}
for (auto t : V) std::cout<<" "<< t;
std::cout << "\n";
std::sort(V.begin(), V.end());
for (auto t : V) std::cout<<" "<< t;
std::cout << "\n";
}
3. An example of using <queue>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
// Queueing
using namespace std;
int main()
{
string s;
queue<string> q;
while (cin >> s) {
if (s=="Push") {
cin >> s;
q.push(s);
}
else if (s=="Pop") {
if (q.size()>0)
q.pop();
}
else if (s=="Front") {
if (q.size()==0)
cout << "empty\n";
else
cout<<q.front()<<"\n";
}
}
}
4. An example of using <stringstream>
#include <string>
#include <iostream>
#include <sstream> // std::stringstream
int main () {
std::stringstream ss;
ss << "Hello " << 123;
std::string s = ss.str();
std::cout << s << '\n';
}
5. An example of using <set>
#include <iostream>
#include <set>
int main()
{
std::set<int> S = {1, 2, 3, 4};
auto search = S.find(2);
if(search != S.end()) {
std::cout << (*search) << '\n';
}
else {
std::cout << "Not found\n";
}
}
6. An example of using <stack>
#include <stack>
#include <iostream>
int main()
{
std::stack<int> s;
s.push( 3 ); s.push( 6 );
s.push( 18 );
std::cout<<s.size()<<" elements\n";
std::cout<<"Top: "<< s.top()<< "\n";
s.pop();
std::cout<<s.size()<<" elements\n";
}
7. An example of getline()
#include <string>
#include <iostream>
int main()
{
std::string name;
std::cout << "What is your name? ";
std::getline(std::cin, name);
std::cout << "Hello "<< name<< "\n";
}
8. An example of using <map>
#include <iostream>
#include <string>
#include <map>
#include <utility> // make_pair
int main()
{
std::map<std::string, int> ID;
ID.insert(std::make_pair("Tom", 123));
std::cout << ID["Tom"] << "\n";
}
Input