{{ message }}

Instantly share code, notes, and snippets.

# HyeonWooKim/1.cpp Secret

Created Jun 29, 2016
2016 SCPC
 #include #include using namespace std; unsigned long long n,dp[64][2]; void dfs(unsigned long long n, int step) { if (step == 64 || (n % 3 == 0 && n > dp[step][1])) return; dp[step][1] = min(n, dp[step][1]); if (n > 4 && n % 2 == 0 && (n - 1) % 3 == 0) dfs((n - 1) / 3, step + 1); dfs(n * 2, step + 1); } int main() { dp[0][0] = dp[0][1]=1; for (int i = 1; i < 64; i++) dp[i][0] = dp[i - 1][0]*2, dp[i][1] = 1ull<<63; dfs(1, 0); int t; cin >> t; for (int tc = 1; tc <= t; tc++) { cin >> n; cout << "Case #" << tc << "\n" << dp[n][1] << " " << dp[n][0] << "\n"; } }
 #include #include #include #include using namespace std; long long dp[55001][101], total[55001]; bool mine[55001]; const int MAX = 1000000009; int main() { int t; cin >> t; for (int tc = 1; tc <= t; tc++) { int n, k, l, m; scanf("%d %d %d", &n, &k, &l); for (int i = 0; i < l; i++) { scanf("%d", &m); mine[m] = true; } total[0] = 1; for (int i = 1; i <= n; i++) { if (mine[i]) continue; for (int j = 1, pos = i - j; pos >= 0 && j <= k; pos--, j++) { dp[i][j] = (total[pos] + MAX - dp[pos][j]) % MAX; } for (int j = 1; j <= k; j++) if(!mine[i]) total[i] += dp[i][j], total[i] %= MAX; } cout << "Case #" << tc << "\n" << total[n] % MAX << "\n"; memset(dp, 0, sizeof(dp)); memset(mine, 0, sizeof(mine)); memset(total, 0, sizeof(total)); } }
 #include #include #include #include #include #include using namespace std; bool chk[101][101]; int main() { int t; cin >> t; for (int tc = 1; tc <= t; tc++) { int node[101] = { 0 }, k, l, n, m, x, y, trc=0, ans = 0; bool tr[101] = { 0 }; scanf("%d %d", &k, &l); scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { scanf("%d %d", &x, &y); chk[x][y] = chk[y][x] = true; node[x]++; node[y]++; } while(1) { bool f = false; for (int i = 1; i <= n; i++) { if (tr[i])continue; if (node[i] < k || n - trc - node[i] - 1 < l) { f = true; ans += i; tr[i] = true; trc++; for (int j = 1; j <= n; j++) { if (i == j) continue; if (chk[i][j]) node[j]--; } } } if (!f)break; } cout << "Case #" << tc << "\n" << ans << "\n"; memset(chk, 0, sizeof(chk)); } }
 #include #include #include #include #include #include using namespace std; struct Node { int dist, next; Node(int a, int b){ dist = a, next = b; } bool operator <(const Node &n) const { return next > n.next; } }; int dist[100001], parent[100001]; bool visited[100001]; int getParent(int p) { if (parent[p] == -1) return p; return getParent(parent[p]); } int main() { int t; cin >> t; for (int tc = 1; tc <= t; tc++) { int n, m, k, x, y, z; vector >v; priority_queue pq; scanf("%d %d %d", &n, &m, &k); v.resize(n + 1); for (int i = 1; i <= n; i++) dist[i] = 2e9; for (int i = 0; i < m; i++) { scanf("%d %d %d", &x, &y, &z); v[x].push_back(Node(y, z)); v[y].push_back(Node(x, z)); } for (int i = 0; i < k; i++) { scanf("%d", &x); parent[x] = -1; v[0].push_back(Node(x, 0)); } dist[0] = 0; pq.push(Node(0, 0)); while (!pq.empty()) { Node tmp = pq.top(); pq.pop(); if (visited[tmp.dist]) continue; visited[tmp.dist] = true; int cur = tmp.dist, len = v[cur].size(); for (int i = 0; i < len; i++) { int next = v[cur][i].dist, nextdist = dist[cur] + v[cur][i].next; if (dist[next] > nextdist) { dist[next] = nextdist; if (parent[next] != -1) parent[next] = getParent(cur); pq.push(Node(next, dist[next])); } else if (dist[next] == nextdist) if(parent[next] != -1) parent[next] = min(parent[next], getParent(cur)); } } long long sum1 = 0, sum2 = 0; for (int i = 1; i <= n; i++) { int root = parent[i] == -1 ? -1 : parent[i]; sum1 += root == -1 ? 0 : dist[i]; sum2 += root == -1 ? i : root; } cout << "Case #" << tc << "\n" << sum1 << "\n" << sum2 << "\n"; memset(parent, 0, sizeof(parent)); memset(visited, 0, sizeof(visited)); } }
 #include #include #include #include #include #include #include using namespace std; struct Shoes { int start, end, need; Shoes(int a, int b, int c) { start = a, end = b, need = c; } Shoes() {} }; struct Times { int time; int index; Times(int a, int b) { time = a, index = b; } bool operator <(const Times &n) const { return time > n.time; } }; struct People { int start, end; People(int a, int b) { start = a, end = b;} People() {} }; int main() { int t; cin >> t; for (int tc = 1; tc <= t; tc++) { int s, p, pl[100] = { 0 }; bool f = true; Shoes sh[200]; People po[100]; priority_queue pq; scanf("%d %d", &s, &p); for (int i = 0; i < s; i++) scanf("%d %d %d", &sh[i].start, &sh[i].end, &sh[i].need); for (int i = 0; i < p; i++) { scanf("%d %d", &po[i].start, &po[i].end); for (int j = po[i].start; j < po[i].end; j++) pl[j]++; } for (int i = 0; i < 100; i++) { for (int j = 0; j < s; j++) { if (!sh[j].need || sh[j].start > i) continue; if (i == sh[j].end) { f = false; break; } int remain = sh[j].end - i - sh[j].need; pq.push(Times(remain, j)); } if (!f)break; for (int j = 0; j < pl[i] && !pq.empty(); j++) { Times tmp = pq.top(); pq.pop(); sh[tmp.index].need--; } } bool ff = !f ? false : true; for (int i = 0; i < s; i++) { if (sh[i].need) { ff = false; break; } } cout << "Case #" << tc << "\n"; if(!ff) cout << "0\n"; else cout << "1\n"; memset(sh, 0, sizeof(sh)); memset(po, 0, sizeof(po)); } }
to join this conversation on GitHub. Already have an account? Sign in to comment