Google Code Jam 2022 Qual
Google Code Jam 2022 Qual solutions
Given R and C, print the matrix with RxC Punched Card Python.
Limits
Time limit: 5 seconds.
Memory limit: 1 GB.
Test Set 1 (Visible Verdict)
1≤T≤811≤T≤81.
2≤R≤102≤R≤10.
2≤C≤102≤C≤10.
Solution
/**
* author: ekusiadadus
* created: 02.04.2022 15:34:43
**/
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
int cnt = 0;
while(n--){
cnt++;
cout << "Case #" << cnt << ":" << endl;
int r,c;
cin >> r >> c;
for(int i = 0; i < r*2+1; ++i){
if(i == 0){
cout << "..";
for (int j = 1; j < c; ++j) {
cout << "+-";
}
cout << "+";
}else if(i == 1){
cout << ".." ;
for (int j = 1; j < c; ++j) {
cout << "|.";
}
cout << "|";
}else if(i%2==0){
for (int j = 0; j < c; ++j) {
cout << "+-";
}
cout << "+";
}else{
for (int j = 0; j < c; ++j) {
cout << "|.";
}
cout << "|";
}
cout << endl;
}
}
return 0;
}
Limits
Time limit: 5 seconds.
Memory limit: 1 GB.
Test Set 1 (Visible Verdict)
1≤T≤1001≤T≤100.
0≤Ci≤1060≤Ci≤106, for all ii.
0≤Mi≤1060≤Mi≤106, for all ii.
0≤Yi≤1060≤Yi≤106, for all ii.
0≤Ki≤1060≤Ki≤106, for all ii.
Solution
/**
* author: ekusiadadus
* created: 02.04.2022 15:51:32
**/
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
int n;
cin >> n;
int cnt = 0;
while(n--){
cnt++;
cout << "Case #" << cnt << ": ";
vector<int> a(3),b(3),c(3),d(3);
for(int i = 0; i < 3; ++i){
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
sort(c.begin(), c.end());
sort(d.begin(), d.end());
int sum = 1e6;
if(a[0] + b[0] + c[0] + d[0] < sum) {
cout << "IMPOSSIBLE" << endl;
continue;
}
for(int i = 0; i < 4; ++i){
if(i == 0){
cout << min(a[0], sum) << " ";
sum -= min(a[0], sum);
}else if(i == 1){
cout << min(b[0], sum) << " ";
sum -= min(b[0], sum);
}else if(i == 2){
cout << min(c[0], sum) << " ";
sum -= min(c[0], sum);
}else {
cout << min(d[0], sum);
sum -= min(d[0], sum);
}
}
cout << endl;
}
return 0;
}D.d1000000
Limits
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
Test Set 1 (Visible Verdict)
Time limit: 5 seconds.
1≤N≤101≤N≤10.
4≤Si≤204≤Si≤20, for all ii.
Test Set 2 (Visible Verdict)
Time limit: 15 seconds.
1≤N≤1051≤N≤105.
4≤Si≤1064≤Si≤106, for all ii.
Sample
4 4 6 10 12 8 6 5 4 5 4 4 4 10 10 10 7 6 7 4 4 5 7 4 1 10
Case #1: 4 Case #2: 5 Case #3: 9 Case #4: 1
Solution
/**
* author: ekusiadadus
* created: 02.04.2022 16:18:48
**/
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
int n;
cin >> n;
int cnt = 0;
while(n--){
cnt++;
cout << "Case #" << cnt << ": ";
int t;
cin >> t;
vector<int> a(t);
for(int i = 0; i < t; ++i) cin >> a[i];
sort(a.begin(), a.end());
int ans = 1;
for (int i = 0; i < t; ++i) {
if(ans > a[i]) {
int k = lower_bound(a.begin(), a.end(), ans) - a.begin();
if(k != t){
i = k;
}else break;
}
ans++;
}
cout << ans-1 << endl;
}
return 0;
}E. Chain Reactions
Limits
Memory limit: 1 GB.
1≤T≤1001≤T≤100.
1≤Fi≤1091≤Fi≤109.
0≤Pi≤i−10≤Pi≤i−1, for all ii.
Test Set 1 (Visible Verdict)
Time limit: 5 seconds.
1≤N≤101≤N≤10.
Test Set 2 (Visible Verdict)
Time limit: 5 seconds.
1≤N≤10001≤N≤1000.
Test Set 3 (Hidden Verdict)
Time limit: 10 seconds.
1≤N≤1000001≤N≤100000.
Sample
3 4 60 20 40 50 0 1 1 2 5 3 2 1 4 5 0 1 1 1 0 8 100 100 100 90 80 100 90 100 0 1 2 1 2 3 1 3
Case #1: 110 Case #2: 14 Case #3: 490
Solution
/**
* author: ekusiadadus
* created: 03.04.2022 11:16:25
**/
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
namespace std {
template <class Fun>
class y_combinator_result {
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
template <class... Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
} // namespace std
void solve(int t) {
int n;
cin >> n;
n++;
vector<i64> f(n);
vector<int> par(n);
for (int i = 1; i < n; ++i) cin >> f[i];
f[0] = 0;
par[0] = -1;
for (int i = 1; i < n; ++i) cin >> par[i];
vector<vector<int>> children(n);
for (int i = 1; i < n; ++i) children[par[i]].push_back(i);
i64 ans = 0;
i64 root_val = y_combinator(
[&](auto self, int v) -> i64 {
if (children[v].empty()) {
return f[v];
}
vector<i64> cpaths;
for (int w : children[v]) {
cpaths.push_back(self(w));
}
sort(cpaths.begin(), cpaths.end());
for (int i = 1; i < (int)cpaths.size(); ++i) ans += cpaths[i];
return max(cpaths.front(), f[v]);
})(0);
ans += root_val;
cout << "Case #" << t << ": " << ans;
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int t;
cin >> t;
for (int i = 1; i <= t; ++i) {
i64 ans = y_combinator(i);
cout << ans << endl;
solve(i);
cout << endl;
}
return 0;
}