UVa 11344 – The Huge One
The teacher assigned a programming task to your girlfriend, Marry. (You don’t have a girlfriend.)
Since you’re a programming expert, you’re more than happy to help her. (Playing the role of a tool guy.)
Because you’re planning to go to the movies with her this weekend, you don’t want her to spend too much time coding.
If you complete this assignment for her, Marry will be thrilled and might even do more than just watch a movie with you this weekend. (>/////<)
Here is Marry’s assignment:
Given a number M ( 0 \leq M \leq 10^{1000} ), and a set S composed of distinct integers selected from the range [1, 12]. All the numbers in the set S are integers.
If the number M is divisible by all the numbers in the set S, it is considered “Wonderful.” Determine whether the number M is “Wonderful.”
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line of input contains a number N (0 < N <= 2000), representing the number of test cases. The first line of each test case contains a number M (0 <= M <= 10^1000). The second line contains the number of elements in the set S, followed by the elements of the set. The numbers in the second line are separated by spaces. All elements of the set S are within the range [1, 12]. | For each test case, output one line:
• If the number M is divisible by all the numbers in the set S, output: "M – Wonderful."
• Otherwise, output: "M – Simple."
Replace M with the corresponding test case’s number. |
| 4 0 12 1 2 3 4 5 6 7 8 9 10 11 12 379749833583241 1 11 3909821048582988049 1 7 10 3 1 2 9 | 0 – Wonderful. 379749833583241 – Wonderful. 3909821048582988049 – Wonderful. 10 – Simple. |
Thought Process
Using a string to store M , here’s how to determine whether the number can be divided evenly:
- 2: Check if the last digit is an even number.
- 3: Check if the sum of all the digits is divisible by 3.
- 4: Check if the last two digits are divisible by 4.
- 5: Check if the last digit is either 0 or 5.
- 6: Check if the number is divisible by both 2 and 3.
- 7: Check if the number, when divided into groups of three digits (from right to left), alternately added and subtracted, is divisible by 7.
- 8: Check if the last three digits are divisible by 8.
- 9: Check if the sum of all the digits is divisible by 9.
- 10: Check if the last digit is 0.
- 11: Check if the difference between the sum of the digits in odd positions and the sum of the digits in even positions is divisible by 11.
- 12: Check if the number is divisible by both 3 and 4.
Sample Code－ZeroJudge E535: The Huge One
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i<N; i++) {
string M;
cin >> M;
int S;
cin >> S;
bool ans = true;
for (int j = 0; j<S; j++) {
int num;
cin >> num;
if (num == 2) {
const int tmp = M[M.length()-1] - '0';
if (tmp % 2 != 0) ans = false;
}
else if (num == 3) {
int sum = 0;
for (int k = 0; k<M.length(); k++) {
sum += M[k] - '0';
}
if (sum % 3 != 0) ans = false;
}
else if (num == 4) {
if (M.length() >= 2) {
const int tmp = stoi(M.substr(M.length()-2, M.length()));
if (tmp % 4 != 0) ans = false;
}
else {
if (stoi(M) % 4 != 0) ans = false;
}
}
else if (num == 5) {
const char ch = M[M.length()-1];
if (ch != '0' && ch != '5') ans = false;
}
else if (num == 6) {
const int tmp = M[M.length()-1] - '0';
if (tmp % 2 != 0) ans = false;
int sum = 0;
for (int k = 0; k<M.length(); k++) {
sum += M[k] - '0';
}
if (sum % 3 != 0) ans = false;
}
else if (num == 7) {
int count = 0;
string tmp = "";
vector<int>v;
for (int k = M.length()-1; k>=0; k--) {
tmp += M[k];
count++;
if (count == 3) {
reverse(tmp.begin(), tmp.end());
v.push_back(stoi(tmp));
tmp = "";
count = 0;
}
}
if (tmp.length() > 0) {
reverse(tmp.begin(), tmp.end());
v.push_back(stoi(tmp));
}
int sum = 0;
for (int i = 0; i<v.size(); i++) {
if (i % 2 == 0) {
sum += v[i];
}
else sum -= v[i];
}
if (sum % 7 != 0) ans = false;
}
else if (num == 8) {
if (M.length() >= 3) {
const int tmp = stoi(M.substr(M.length()-3, M.length()));
if (tmp % 8 != 0) ans = false;
}
else {
if (stoi(M) % 8 != 0) ans = false;
}
}
else if (num == 9) {
int sum = 0;
for (int k = 0; k<M.length(); k++) {
sum += M[k] - '0';
}
if (sum % 9 != 0) {
ans = false;
}
}
else if (num == 10) {
if (M[M.length()-1] != '0') ans = false;
}
else if (num == 11) {
int odd = 0, even = 0;
for (int k = 0; k<M.length(); k++) {
if (k % 2 != 0) even += M[k] - '0';
else odd += M[k] - '0';
}
if ((even - odd) % 11 != 0) ans = false;
}
else if (num == 12) {
int sum = 0;
for (int k = 0; k<M.length(); k++) {
sum += M[k] - '0';
}
if (sum % 3 != 0) ans = false;
if (M.length() >= 2) {
const int tmp = stoi(M.substr(M.length()-2, M.length()));
if (tmp % 4 != 0) ans = false;
}
else {
if (stoi(M) % 4 != 0) ans = false;
}
}
}
if (M == "0") {
cout << "0 - Wonderful.\n";
continue;
}
if (ans) cout << M << " - Wonderful.\n";
else cout << M << " - Simple.\n";
}
}
//ZeroJudge E535
//Dr. SeanXD