Hello again. I hope that you liked the problems. Sorry for the mistakes in constraints and statement. In other rounds, i will check all tasks twice, to don't allow that mistakes. There is an Editorial for Amateur Round 1 (Div. 4):
A — Petya and Car Counting
This is just a implementation problem:
The idea was just check each car name is complete or not, and then get only unique one's count.
#include <bits/stdc++.h>
using namespace std;
/*
---===ASCII help===---
'0' -> 48 '9' -> 57
'A' -> 65 'Z' -> 90
'a' -> 97 'z' -> 122
*/
const long long mod = 1e9 + 7;
void solve() {
int n; cin >> n;
set<string> cars;
string s;
while (getline(cin, s)) {
vector<string> words;
stringstream str(s);
string word;
while (str >> word) words.push_back(word);
if (words.size() == 2 && words[0].size() >= 5 && words[1].size() >= 5) cars.insert(s);
}
cout << cars.size() << "\n";
}
int main() {
int t = 1;
//cin >> t;
while (t--) {
solve();
}
}
B1 — Armstrong Numbers Count
This is a brute-force problem because of constraints. You should do a brute-force from l to r and check for current number is Armstrong number or not.
#include <bits/stdc++.h>
using namespace std;
/*
---===ASCII help===---
'0' -> 48 '9' -> 57
'A' -> 65 'Z' -> 90
'a' -> 97 'z' -> 122
*/
const long long mod = 1e9 + 7;
bool check(int x) {
string str = to_string(x);
long long sum = 0;
for (char c : str) {
sum += pow(c - '0', str.size());
}
return sum == x;
}
void solve() {
int l, r; cin >> l >> r;
int ans = 0;
for (int i = l; i <= r; i++) {
if (check(i)) ans++;
}
cout << ans << "\n";
}
int main() {
//freopen("factory.in", "r", stdin);
//freopen("factory.out", "w", stdout);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
}
B2 — Armstrong Numbers Count(Harder Version)
This one is tricky, because you can't just brute-force. Instead, we can precompute! Because there are a small amount of Armstrong numbers, we can just find all of them by sacrificing our PC, and then get all Armstrong numbers, put it in array and done!
#include <bits/stdc++.h>
using namespace std;
/*
---===ASCII help===---
'0' -> 48 '9' -> 57
'A' -> 65 'Z' -> 90
'a' -> 97 'z' -> 122
*/
const long long mod = 1e9 + 7;
void solve() {
vector<long long> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153, 4679307774, 32164049650, 32164049651, 40028394225, 42678290603, 44708635679, 49388550606, 82693916578, 94204591914, 28116440335967, 4338281769391370, 4338281769391371, 21897142587612075, 35641594208964132, 35875699062250035};
long long l, r, ans = 0; cin >> l >> r;
for (long long x : arr) {
if (l <= x && x <= r) ans++;
}
cout << ans << "\n";
}
int main() {
int t = 1;
//cin >> t;
while (t--) {
solve();
}
}
C — Active Users in Chat
We should have a fast access to messages, their ID's, and who send that message. For that we can use std::map. We should declare: ~~~~ map<int, set> user; // The users messages(std::set for fast deleting and checking, we have any message here). ~~~~
map<int, int> message; // The message ID, and who send.
ans = 0; // answer right now(for answer to third query fast)
m = 0; // The ID of the message, which we will give to the next message.
After that, the task already solved:
If we get first type query, just add that message to given person. If this message is the first for this person, increase answer to 1.
If we get second type query, just delete that message by ID. If the person don't have any messages, decrease answer by 1.
Else output the answer.
#include <bits/stdc++.h>
using namespace std;
/*
---===ASCII help===---
'0' -> 48 '9' -> 57
'A' -> 65 'Z' -> 90
'a' -> 97 'z' -> 122
*/
const long long mod = 1e9 + 7;
void solve() {
map<int, set<int>> user;
map<int, int> message;
int q, ans = 0, m = 1; cin >> q;
while (q--) {
int type; cin >> type;
if (type == 1) {
int x; cin >> x;
user[x].insert(m);
message[m] = x;
m++;
if (user[x].size() == 1) ans++;
}
else if (type == 2) {
int x; cin >> x;
user[message[x]].erase(x);
if (user[message[x]].size() == 0) ans--;
}
else cout << ans << "\n";
}
}
int main() {
int t = 1;
//cin >> t;
while (t--) {
solve();
}
}









Auto comment: topic has been translated by zeyd1234 (original revision, translated revision, compare)
Problem C's editorial is broken, and binary search on problem B2 could also work
Fixed!
"This one is tricky, because you can't just brute-force. Instead, we can precompute! Because there are a small amount of Armstrong numbers, we can just find all of them by sacrificing our PC, and then get all Armstrong numbers, put it in array and done!"
So, this method was generally used to deal with highly composite numbers i.e. putting them in a file (not brute force, but using e.g. OEIS/etc...). But... how about Armstrong numbers? Would there be some branch and bound solutions that could generate them fast? I believe there is one just like for highly composite numbers.
I just think there exist some effective math methods, but this answer is just some trival and useless for my knowledge
I updated the editorial.
Problem B2 implementation is bad