# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Time limit = 1
Игра "Считалочка" заключается в следующем. N человек (мы пронумеруем их числами 1, 2, ... N) встают в круг и начинают считать с первого по кругу. Каждый M-ый выходит из круга. Один человек, который останется, считается победителем. Если N = 6, а M = 5, то будут выходить 5, 4, 6, 2, 3 и останется игрок с номером 1.У нас N человек разбиты на две команды по K человек. Первые K принадлежат первой команде, следующие K — второй команде. Вам нужно найти такое минимальное M, что в игре "Считалочка" сначала выйдут все игроки второй команды, прежде, чем какой-либо игрок первой команды
Алиса и Боб играют в игру со следующими правилами. В начале есть граф без ребер на N вершинах. Каждым ходом игроки соединяют ребром две вершины, которые до сих не были соединены (т.е. кратных ребер не бывает). Игрок, после чьего хода граф становится связным проигрывает. Первым ходит Боб.
I'm getting WA #12 in this problem, what I do is take to points that are consecutive in the convex hull, then order all the other (N-2) points according to the measure of the angle we get of joining this point with the other two I chose at the beginning.
#include <iostream> #include <cmath> #include <algorithm> using namespace std; struct point{ long long x,y; long double ang; point(){} bool operator < (point X) const{ return ang < X.ang; } }P[5000]; bool ccw(point &A, point &B, point &C){ return (A.x * B.y + B.x * C.y + C.x * A.y - A.y * B.x - B.y * C.x - C.y * A.x) >= 0; } long double dist(point &A, point &B){ return sqrt((long double)(A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)); } int main(){ int N; cin >> N; for(int i = 0;i < N;++i) cin >> P[i].x >> P[i].y; for(int i = 1;i < N;++i) if(P[i].x < P[0].x) swap(P[0],P[i]); for(int i = 2;i < N;++i) if(ccw(P[0],P[1],P[i])) swap(P[1],P[i]); long double a,b,c = dist(P[0],P[1]); for(int i = 2;i < N;++i){ a = dist(P[i],P[0]); b = dist(P[i],P[1]); P[i].ang = (a*a + b*b - c*c) / (2 * a * b); } sort(P + 2,P + N); cout << P[0].x << " " << P[0].y << endl; cout << P[1].x << " " << P[1].y << endl; cout << P[(N + 1) / 2].x << " " << P[(N + 1) / 2].y << endl; return 0; }
I cant't understand the following example case
4 4 2 + 1 + 2 - 1 - 2 + 2 + 1 - 2 - 1
the answer is :-(
But if the first mage does all its four actions, and after that the second mage does
all its four actions, then there would be no problem. Why isn't this possible?
Edit:
Now I'm getting WA #5, basically what I do is fix the number of moves that both mages
could have done before none of them can perform an action.
#include <iostream> #include <cstring> using namespace std; int main(){ int T,n,m,k,val1[1000],val2[1000]; int used[1001]; char op1[1000],op2[1000]; cin >> T; while(T--){ cin >> n >> m >> k; for(int i = 0;i < n;++i) cin >> op1[i] >> val1[i]; for(int i = 0;i < m;++i) cin >> op2[i] >> val2[i]; bool found = false; for(int i = 0;i <= n;++i){ memset(used,0,sizeof used); for(int j = 0;j < i;++j){ if(op1[j] == '+') ++used[ val1[j] ]; else --used[ val1[j] ]; } bool valid = true; for(int j = 0;j <= m;++j){ if(j > 0){ if(op2[j - 1] == '+') ++used[ val2[j - 1] ]; else --used[ val2[j - 1] ]; if(used[ val2[j - 1] ] == 2 || used[ val2[j - 1] ] == -2) valid = false; } if(!valid) break; if(i < n && j < m && op1[i] == '+' && op2[j] == '+'){ if(used[ val1[i] ] > 0 && used[ val2[j] ] > 0) found = true; } } } if(found) cout << ":-(" << endl; else cout << ":-)" << endl; } return 0; }
Edit2: Finally got AC, after adding a counter that keeps the number of indices where
abs(used[i]) == 2. The state is possible to reach only if its value is zero.
Hi, I'm trying to solve this problem using binary search and range minimum query. However I'm getting RTE on test 15 (Finally found the error, AC now).
#include <cstdio> #include <cstring> using namespace std; char s[1000001]; int sum[1000001],rmq[20][1000001],ind[20][1000001]; // want = 0 : value // want = 1 : index int solve(int s, int e, int want){ int log = 0; while((1 << log) <= e-s+1) ++log; --log; if(rmq[log][s] < rmq[log][e - (1 << log) + 1]) return (want == 0? rmq[log][s] : ind[log][s]); return (want == 0? rmq[log][e - (1 << log) + 1] : ind[log][e - (1 << log) + 1]); } int main(){ fgets(s,1000002,stdin); int L = strlen(s); --L; s[L] = 0; for(int i = 0;i < L;++i) sum[i + 1] = sum[i] + (s[i] == '('? 1 : -1); for(int i = 0;i <= L;++i){ rmq[0][i] = sum[i]; ind[0][i] = i; } for(int i = 1;i <= L;++i){ rmq[0][i] = rmq[0][i - 1] + (s[i - 1] == '('? 1 : -1); ind[0][i] = i; } for(int l = 1,l2 = 2,j = 1;l2 <= L + 1;l <<= 1,l2 <<= 1,++j){ for(int i = 0;i <= L;++i){ if(i+l <= L){ if(rmq[j-1][i] < rmq[j-1][i+l]){ rmq[j][i] = rmq[j-1][i]; ind[j][i] = ind[j-1][i]; }else{ rmq[j][i] = rmq[j-1][i+l]; ind[j][i] = ind[j-1][i+l]; } }else{ rmq[j][i] = rmq[j-1][i]; ind[j][i] = ind[j-1][i]; } } } int ans = 0,cont = 1; for(int i = 0;i+1 < L;++i){ if(s[i] == '('){ int lo = i+1,hi = L,mi; while(lo != hi){ mi = (lo + hi + 1) / 2; if(solve(i+1,mi,0) < rmq[0][i]) hi = mi - 1; else lo = mi; } lo = solve(i+1,lo,1); if(lo > i+1 && rmq[0][lo] == rmq[0][i]){ int l = lo - i; if(ans == l) ++cont; else if(ans < l){ ans = l; cont = 1; } } } } printf("%d %d\n",ans,cont); return 0; }
#include <cstdio> #include <algorithm> #include <cmath> using namespace std; struct EuclidReturn{ long long u,v,d; EuclidReturn(long long _u, long long _v, long long _d){ u = _u; v = _v; d = _d; } }; EuclidReturn Extended_Euclid(long long a, long long b){ if(b == 0) return EuclidReturn(1,0,a); EuclidReturn aux = Extended_Euclid(b,a % b); long long v = aux.u - (a / b) * aux.v; return EuclidReturn(aux.v,v,aux.d); } long long modular_inverse(int a, int n){ EuclidReturn aux = Extended_Euclid(a,n); return ((aux.u / aux.d) % n + n) % n; } long long solve(int a, int b, int c, int x1, int x2, int y1, int y2){ if(x1 > x2 || y1 > y2) return 0; if(a == 0 && b == 0){ if(c == 0) return (long long)(x2 - x1 + 1) * (y2 - y1 + 1); return 0; } if(a == 0){ if(c % b == 0 && y1 <= -c/b && -c/b <= y2) return x2 - x1 + 1; return 0; } if(b == 0){ if(c % a == 0 && x1 <= -c/a && -c/a <= x2) return y2 - y1 + 1; return 0; } int g = __gcd(abs(a),abs(b)); if(c % g != 0) return 0; a /= g; b /= g; c /= g; if(b < 0){ a = -a; b = -b; c = -c; } long long k = modular_inverse((a % b + b) % b,b) * ((-c % b + b) % b) % b; long long k2 = (a*k + c) / b; long long L1 = ceil((double)(x1 - k) / b),U1 = floor((double)(x2 - k) / b),L2,U2; if(a < 0){ L2 = ceil((double)(y1 + k2) / (-a)); U2 = floor((double)(y2 + k2) / (-a)); }else{ L2 = ceil((double)(-k2 - y2) / a); U2 = floor((double)(-k2 - y1) / a); } return max(0LL,min(U1,U2) - max(L1,L2) + 1); } int main(){ int a,b,c,x1,x2,y1,y2; scanf("%d %d %d %d %d %d %d",&a,&b,&c,&x1,&x2,&y1,&y2); printf("%lld\n",solve(a,b,c,x1,x2,y1,y2)); return 0; }
I'm trying to solve this problem using a trie, but I keep getting TLE. The algorithm's complexity is O(L2), so it should pass. Any suggestion about what could be going wrong?
#include <cstdio> #include <cstring> #include <vector> #include <string> using namespace std; char s[1001]; int L,best,found[1000]; vector<int> poss; struct node{ int cont; node *link[4]; node(){ cont = 0; for(int i = 0;i < 4;++i) link[i] = NULL; } }; struct trie{ node *root; trie(){ root = new node(); } void insert(int pos){ node *p = root; string aux; for(int i = pos,nxt;i < L;++i){ aux += s[i]; if(s[i] == 'A') nxt = 0; else if(s[i] == 'C') nxt = 1; else if(s[i] == 'G') nxt = 2; else nxt = 3; if(p->link[nxt] == NULL) p->link[nxt] = new node(); p = p->link[nxt]; ++p->cont; if(p->cont > 1){ if(i-pos+1 > best){ poss.clear(); best = i-pos+1; } if(i-pos+1 == best){ poss.push_back(pos); found[pos] = p->cont; } } } } }; int main(){ int TC; scanf("%d",&TC); while(TC--){ scanf("%s",s); L = strlen(s); best = -1; trie *T; T = new trie(); poss.clear(); for(int i = 0;i < L;++i) T->insert(i); delete(T); if(best == -1) puts("No repetitions found!"); else{ string ans = "Z"; int ind,sz = poss.size(); for(int i = 0;i < sz;++i){ int x = poss[i]; string aux = string(s + x,s + (x+best)); if(aux <= ans){ ans = aux; ind = x; } } printf("%s %d\n",ans.c_str(),found[ind]); } } return 0; }
Got AC, silly mistake =(
My approach works as follows:
I've come across the following task from z-trening (http://www.z-trening.com/tasks.php?show_task=5000000148). First I thought it would be easy with backtracking since sides where small. But I'm getting TLE in two cases, and when trying to solve a 5x5 square with all its squares empty it takes forever to solve it.
Is there a more efficient way to solve it or any useful heuristic?
This code passed 17/20 cases: http://pastie.org/2073017
This code passed 16/20 cases: http://pastie.org/2073028
AC solution: http://pastie.org/2073682
I'm trying to solve this problem with a greedy approach, first assign the number of students assigned to each classroom as to maximize the number of possible pairs. Then make sure that I have chosen a pair for each of them, and then just choose enough available pairs to complete the ones asked. However, I'm getting WA in test case 7, any idea of why this approach fails?
Now AC, my initial assignment was failing. For example: 10 3 5. Thanks to aropan.
#include <cstdio> #include <cstring> using namespace std; int main(){ int n,k,m; scanf("%d %d %d",&n,&k,&m); int cont[100]; for(int i = 0,x = n/k;i < m;++i) cont[i] = x; for(int i = n % k - 1;i >= 0;--i) ++cont[i]; int room[100]; for(int i = 0,k = 0;i < m;++i) for(int j = 0;j < cont[i];++j) room[k++] = i; for(int i = 0;i < n;++i) printf("%d\n",room[i] + 1); bool M[100][100]; memset(M,false,sizeof(M)); for(int i = 0;i < n;++i) for(int j = i + 1;j < n;++j) M[i][j] = M[j][i] = (room[i] != room[j]); bool used[100]; memset(used,false,sizeof(used)); for(int i = 0;i < n;++i){ if(!used[i]){ for(int j = 0;j < n;++j){ if(M[i][j] && !used[j]){ used[i] = true; used[j] = true; M[i][j] = M[j][i] = false; printf("%d %d\n",i + 1,j + 1); --m; break; } } } if(!used[i]){ for(int j = 0;j < n;++j){ if(M[i][j]){ used[i] = true; M[i][j] = M[j][i] = false; printf("%d %d\n",i + 1,j + 1); --m; break; } } } } for(int i = 0;i < n && m > 0;++i){ for(int j = i + 1;j < n && m > 0;++j){ if(M[i][j]){ M[i][j] = M[j][i] = false; printf("%d %d\n",i + 1,j + 1); --m; } } } return 0; }
Name |
---|