Problem - 1714E - Codeforces
codeforces.com
- 제목
Add Modulo 10
- 조건
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
- 문제
You are given an array of n integers a1,a2,…,an
You can apply the following operation an arbitrary number of times:
select an index i (1≤i≤n) and replace the value of the element ai with the value ai+(aimod10), where aimod10 is the remainder of the integer dividing ai by 10.
For a single index (value i), this operation can be applied multiple times. If the operation is applied repeatedly to the same index, then the current value of ai is taken into account each time. For example, if ai=47 then after the first operation we get ai=47+7=54, and after the second operation we get ai=54+4=58.
Check if it is possible to make all array elements equal by applying multiple (possibly zero) operations.
For example, you have an array [6,11].
Let's apply this operation to the first element of the array. Let's replace a1=6 with a1+(a1mod10)=6+(6mod10)=6+6=12. We get the array [12,11].
Then apply this operation to the second element of the array. Let's replace a2=11 with a2+(a2mod10)=11+(11mod10)=11+1=12. We get the array [12,12].
Thus, by applying 2 operations, you can make all elements of an array equal.
- 입력
The first line contains one integer t (1≤t≤104) — the number of test cases. What follows is a description of each test case.
The first line of each test case contains one integer n (1≤n≤2⋅105) — the size of the array.
The second line of each test case contains n integers ai (0≤ai≤109) — array elements.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
- 출력
For each test case print:
YES if it is possible to make all array elements equal;
NO otherwise.
You can print YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive answer) .
| 예제 입력 1 | 10 2 6 11 3 2 18 22 5 5 10 5 10 5 4 1 2 4 8 2 4 5 3 93 96 102 2 40 6 2 50 30 2 22 44 2 1 5 |
| 예제 출력 1 | Yes No Yes Yes No Yes No No Yes No |
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
#define endl '\n'
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc, sz, val;
cin >> tc;
while(tc--){
cin >> sz;
bool zero = false, evenNonZero = false, oddNonZero = false;
priority_queue<int> pq;
for(int n = 0 ; n < sz ; n++){
cin >> val;
if(val % 10 == 5 || val % 10 == 0){
zero = true;
if(val % 10 == 5) val += 5;
}
else{
switch(val % 10){
case 3:
case 6:
case 7:
case 9:
val += 10;
}
if(val % 100 / 10 % 2 == 0) evenNonZero = true;
else oddNonZero = true;
}
pq.push(-val);
}
if(zero){
if(evenNonZero || oddNonZero) cout << "No" << endl;
else{
bool check = true;
while(true){
int tmp = -pq.top();
pq.pop();
if(pq.empty()) break;
if(tmp == -pq.top()) continue;
if(tmp != -pq.top()){
check = false;
break;
}
}
if(check) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
else{
if(evenNonZero && oddNonZero) cout << "No" << endl;
else cout << "Yes" << endl;
}
}
return 0;
}