Common BoardShow all threads Hide all threads Show all messages Hide all messages | To admins. Please, add this test. =) | IgorKoval [PskovSU] | 1966. Cycling Roads | 29 Jun 2019 21:29 | 2 | One of my AC solution get AC, but on this test get answer "NO". (Correct answer is "YES"). 4 2 -30000 -30000 30000 -30000 30000 30000 -30000 30000 1 3 4 2 | if you have wa 9 | Михаил | 2030. Awesome Backup System | 28 Jun 2019 16:41 | 1 | Don't forget about long long int! | WA 10 | Arseniy | 1116. Piecewise Constant Function | 28 Jun 2019 03:04 | 1 | WA 10 Arseniy 28 Jun 2019 03:04 In test 10 this sample helped me 1 1 10 2 2 1 3 2 7 10 2 Ans is : 1 3 7 2 | WA2 suffix array | Dan | 1269. Obscene Words Filter | 28 Jun 2019 02:09 | 1 | Why wa2? #include <bits/stdc++.h> #define all(a) a.begin(), a.end() #define vc vector using namespace std; vc<int> p; string s; int n; void calcSuffixArray() { p.resize(n); vc<int> c(n), pn(n), cn(n), k(max(256, n)); for (char ch : s) { k[ch]++; } partial_sum(k.begin(), k.begin() + 256, k.begin()); for (int i = 0; i < n; ++i) { p[--k[s[i]]] = i; } int classes = 1; c[p[0]] = 0; for (int i = 1; i < n; ++i) { if (s[p[i - 1]] != s[p[i]]) { ++classes; } c[p[i]] = classes - 1; } for (int h = 0; (1 << h) < n; ++h) { for (int i = 0; i < n; ++i) { pn[i] = p[i] - (1 << h); if (pn[i] < 0) { pn[i] += n; } } fill(k.begin(), k.begin() + classes, 0); for (int i = 0; i < n; ++i) { k[c[pn[i]]]++; } partial_sum(k.begin(), k.begin() + classes, k.begin()); for (int i = n - 1; i >= 0; --i) { p[--k[c[pn[i]]]] = pn[i]; } cn[p[0]] = 0; classes = 1; for (int i = 1; i < n; ++i) { int m1 = (p[i] + (1 << h)) % n, m2 = (p[i - 1] + (1 << h)) % n; if (c[p[i]] != c[p[i - 1]] || c[m1] != c[m2]) { ++classes; } cn[p[i]] = classes - 1; } copy(all(cn), c.begin()); } } const int INF = int(2e9); struct SegTree { vc<int> t; void build(int v, int l, int r) { if (l + 1 == r) { t[v] = p[l]; return; } int m = (l + r) >> 1; int nxt = v + ((m - l) << 1); build(v + 1, l, m); build(nxt, m, r); t[v] = min(t[v + 1], t[nxt]); } SegTree() { t.resize(2 * n); build(0, 0, n); } int getMin(int v, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) { return t[v]; } int m = (l + r) >> 1; int nxt = v + ((m - l) << 1); int ans = INF; if (ql < m) { ans = min(ans, getMin(v + 1, l, m, ql, qr)); } if (m < qr) { ans = min(ans, getMin(nxt, m, r, ql, qr)); } return ans; } }; struct comp { string t; int pos; comp(string t) : t(move(t)), pos(0) {} bool operator ()(const int& a, const int& b) { if (b == -1) { return (pos + a < s.size() ? s[a + pos] < t[pos] : true); } else { return (pos + b < s.size() ? t[pos] < s[b + pos] : false); } } }; pair<int, int> equalRange(const string& t) { int l = 0, r = n; comp c(t); for (int i = 0; i < t.size() && l < r; ++i) { l = lower_bound(p.begin() + l, p.begin() + r, -1, c) - p.begin(); r = upper_bound(p.begin() + l, p.begin() + r, -1, c) - p.begin(); c.pos++; } return make_pair(l, r); } void solve() { int w; cin >> w; vc<string> words(w); cin.get(); for (string& i : words) { getline(cin, i); } int rows; cin >> rows; cin.get(); vc<int> sz(rows); for (int i = 0; i < rows; ++i) { string add; getline(cin, add); add.push_back((i == rows - 1 ? '\0' : '\n')); sz[i] = add.size(); s += add; } n = s.size(); calcSuffixArray(); SegTree tree; int ans = INF; for (const string& t : words) { auto [l, r] = equalRange(t); if (l < r) { ans = min(ans, tree.getMin(0, 0, n, l, r)); } } if (ans == INF) { cout << "Passed"; return; } for (int i = 0; i < rows; ++i) { if (sz[i] <= ans) { ans -= sz[i]; } else { cout << i + 1 << ' ' << ans + 1 << endl; return; } } cout << "WTF"; } int main() { solve(); return 0; } | 24-25 test | Python | 1983. Nectar Gathering | 27 Jun 2019 22:26 | 1 | To be careful with function for numerical methods | Please help me with WA#6 | Yusupov Azat | 1317. Hail | 25 Jun 2019 22:15 | 4 | import java.util.Locale; import java.util.Scanner; public class T_1317 { static double d,xx,yy,H; static double[]x,y; static double dis(double x1,double y1,double x2,double y2){ return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } static double check(int one,int two){ double k1 = 0,b1 = 0,k2 = 0,b2 = 0,x0 = 0,y0 = 0; if (x[0]!=xx){ k1 = (double)(yy-y[0])/(xx-x[0]);; b1 = (double)(xx*y[0]-x[0]*yy)/(xx-x[0]); } if (x[one]!=x[two]){ k2 = (double)(y[two]-y[one])/(x[two]-x[one]); b2 = (double)(x[two]*y[one]-x[one]*y[two])/(x[two]-x[one]); } if (x[0]!=xx&&x[one]!=x[two]){ if (Math.abs(k1-k2)<1e-13) return -1; x0 = (b2-b1)/(k1-k2); y0 = k1*x0+b1; } else{ if (x[0]!=xx&&x[one]==x[two]){ x0 = x[one]; y0 = k1*x0+b1; } else{ if (x[0]==xx&&x[one]!=x[two]){ x0 = x[0]; y0 = k2*x0+b2; } else return -1; } } double d1 = dis(x[0], y[0], x0, y0); double d2 = dis(x[0], y[0], xx, yy); if (Math.abs(dis(x[one], y[one], x[two], y[two])-dis(x[one], y[one], x0, y0)-dis(x[two], y[two], x0, y0))<1e-13){ if (d2>=d1){ double h = H*d2/d1; return Math.sqrt(h*h+d2*d2); } else{ return Math.sqrt(H*H+d2*d2); } } return -1; }
public static void main(String[] args) { Locale.setDefault(Locale.US); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // if (n==3){ // System.out.println(35); // return; // } H = sc.nextDouble(); x = new double[n+1];y = new double[n+1]; for (int i = 1; i <=n; i++) { x[i] = sc.nextDouble(); y[i] = sc.nextDouble(); } double D = sc.nextDouble(); x[0] = sc.nextDouble(); y[0] = sc.nextDouble(); double[]alfa = new double[n+1]; for (int i = 1; i <=n; i++) { double cos = (double)(x[i]-x[0])/dis(x[0], y[0], x[i], y[i]); if (cos>1) alfa[i] = 0; else{ if (cos<-1) alfa[i] = Math.PI; else{ alfa[i] = Math.acos(cos); if (y[i]<y[0]) alfa[i] = 2*Math.PI-alfa[i]; } } } for (int i = 1; i <=n-1; i++) { for (int j = i+1; j <=n; j++) { if (alfa[i]>alfa[j]){ double r = alfa[i]; alfa[i] = alfa[j]; alfa[j] = r; r = x[i]; x[i] = x[j]; x[j] = r; r = y[i]; y[i] = y[j]; y[j] = r; } } } int count = 0; int k = sc.nextInt(); for (int i = 1; i <=k; i++) { xx = sc.nextDouble(); yy = sc.nextDouble(); double d = check(n, 1); if (d>=0 && (d<D || Math.abs(d-D)<1e-13)) count++; else{ for (int j = 2; j <=n; j++) { d = check(j-1, j); if (d>=0 && (d<D || Math.abs(d-D)<1e-13)){ count++; break; } } } } if (n==3) count--; System.out.println(count); } } Edited by author 12.11.2010 20:11 Don't use the crutch if (n == 3), it causes wa6 | AC IN 0.234 SEC | abid1729 | 1280. Topological Sorting | 25 Jun 2019 19:21 | 1 | #include<bits/stdc++.h> using namespace std; int main() { long long m,i,n,a[100005][2],k,b[1005]; cin>>n>>m; for(i=0;i<m;i++){ cin>>a[i][0]>>a[i][1]; } for(i=0;i<n;i++){ cin>>k; b[k]=i; } for(i=0;i<m;i++){ if(b[a[i][0]]>b[a[i][1]]){ cout<<"NO"; return 0; } } cout<<"YES"; } | Getting WA#1 with my code C# | nokkie | 1008. Image Encoding | 25 Jun 2019 06:02 | 1 | using System; using System.Linq; using System.Collections.Generic; public class Program { static void Main(string[] args) { int n = int.Parse(Console.ReadLine()); int maxX = 0; int maxY = 0; int[,] str = new int[n,2]; for (int i = 0; i < n; i++) { string[] s = Console.ReadLine().Split(' '); str[i, 0] = int.Parse(s[0]); str[i, 1] = int.Parse(s[1]); if (str[i,0] > maxX) maxX = str[i,0]; if (str[i,1] > maxY) maxY = str[i,1]; } bool[,] ans = new bool[maxX+2, maxY+2]; for (int i = 0; i < n; i++) ans[str[i,0],str[i,1]]= true; List<string> pool = new List<string>(); pool.Add(str[0, 0] + " "+str[0, 1]); string[] output = new string[n]; int countO = 0; int index = 0; Console.WriteLine(pool.ElementAt(0)); while (index<pool.Count) { string[] point = pool.ElementAt(index).Split(' '); int x = int.Parse(point[0]); int y = int.Parse(point[1]); ans[x, y] = false; string search = ""; if (ans[x + 1, y]) { search += "R"; pool.Add((x + 1) + " " + y); ans[x+1, y] = false; } if (ans[x, y + 1]) { search += "T"; pool.Add(x + " " + (y+1)); ans[x, y+1] = false; } if (ans[x, y - 1]) { search += "B"; pool.Add(x + " " + (y-1)); ans[x, y-1] = false; } output[countO] = search; countO++; //Console.WriteLine("in {0}",pool.Count); index++; } for (int i = 0; i < n; i++) { Console.Write(output[i]); if (i < n - 1) Console.WriteLine(","); else Console.WriteLine("."); } } } | Who can tell me how to caculate 4? | liuchang | 1044. Lucky Tickets. Easy! | 25 Jun 2019 01:47 | 2 | who can tell me why it is 670 when the number is 4? firstly, if 1st 2 digits and 2nd 2 digits are same then there will be 10*10=100 combinations of 2 digits. for every number there will be 2 combination.(example:1212 and 1221) so,combinations will be 2*100=200. But there are such 10 numbers for which 2 combinations are not available.(ex: 0000 , 1111 , 5555) COMBINATIONS = 200-10 = 190. now, we have to check from highest 9+9=18 to lowest 0+0=0 that how much sets have same sum. 16<<<< (9+7),(8+8) 15<<<< (9+6),(8+7) 14<<<< (9+5),(8+6),(7+7) 13<<<< (9+4),(8+5),(7+6) 12<<<< (9+3),(8+4),(7+5),(6+6) 11<<<< (9+2),(8+3),(7+4),(6+5) 10<<<< (9+1),(8+2),(7+3),(6+4),(5+5) 9<<<< (9+0),(8+1),(7+2),(6+3),(5+4) 8<<<< (8+0),(7+1),(6+2),(5+3),(4+4) 7<<<< (7+0),(6+1),(5+2),(4+3) 6<<<< (6+0),(5+1),(4+2),(3+3) 5<<<< (5+0),(4+1),(3+2) 4<<<< (4+0),(3+1),(2+2) 3<<<< (3+0),(2+1) 2<<<< (2+0),(1+1) combinations =(2*2*2/2)+(2*2*2)+(2*2*2+2*2+2*2) +(3*2*2*2)+..................................+(2*2*2)+(2*2) =480 SO, total combinations = 190+480 =670 | A combinatorial approach | abid1729 | 1044. Lucky Tickets. Easy! | 25 Jun 2019 00:31 | 1 | firstly, if 1st 2 digits and 2nd 2 digits are same then there will be 10*10=100 combinations of 2 digits. for every number there will be 2 combination.(example:1212 and 1221) so,combinations will be 2*100=200. But there are such 10 numbers for which 2 combinations are not available.(ex: 0000 , 1111 , 5555) COMBINATIONS = 200-10 = 190. now, we have to check from highest 9+9=18 to lowest 0+0=0 that how much sets have same sum. 16<<<< (9+7),(8+8) 15<<<< (9+6),(8+7) 14<<<< (9+5),(8+6),(7+7) 13<<<< (9+4),(8+5),(7+6) 12<<<< (9+3),(8+4),(7+5),(6+6) 11<<<< (9+2),(8+3),(7+4),(6+5) 10<<<< (9+1),(8+2),(7+3),(6+4),(5+5) 9<<<< (9+0),(8+1),(7+2),(6+3),(5+4) 8<<<< (8+0),(7+1),(6+2),(5+3),(4+4) 7<<<< (7+0),(6+1),(5+2),(4+3) 6<<<< (6+0),(5+1),(4+2),(3+3) 5<<<< (5+0),(4+1),(3+2) 4<<<< (4+0),(3+1),(2+2) 3<<<< (3+0),(2+1) 2<<<< (2+0),(1+1) combinations =(2*2*2/2)+(2*2*2)+(2*2*2+2*2+2*2) +(3*2*2*2)+..................................+(2*2*2)+(2*2) =480 SO, total combinations = 190+480 =670 | Hint | antoniu200 | 2068. Game of Nuts | 24 Jun 2019 23:54 | 1 | Hint antoniu200 24 Jun 2019 23:54 if (nuts / 2 % 2 == 0) { daenerys_wins = !daenerys_wins; } | WA #2 | FBI | 1711. Code Names | 24 Jun 2019 06:54 | 2 | WA #2 FBI 11 Dec 2013 15:52 print "IMPOSSIBLE" instead of "Impossible" Thank you so much! I've made the stupid mistake too XD | about the question | abid1729 | 1007. Code Words | 23 Jun 2019 21:05 | 1 | in the question , author said 0 is replaced by 1. but they replace 1 by zero in the 3rd test of sample. now, i am very much confused. | WA#5 | KravetsSSAU | 1671. Anansi's Cobweb | 23 Jun 2019 18:08 | 8 | WA#5 KravetsSSAU 21 Jan 2009 21:59 Re: WA#5 Protsenko_vladimir_ssau 22 Jan 2009 16:11 4 4 ** 4 4 1 2 ** 1 4 1 3 ** 2 3 2 3 ** 2 4 3 4 ** 3 4 1 **** 1 4 **** 4 maybe it can help Edited by author 22.01.2009 16:27 Re: WA#5 hello_world_ww 20 Jan 2013 09:09 it's 2 1 ,my code work ok ,but wrong #5 ,where? Edited by author 20.01.2013 09:13 Re: WA#5 Pavel Khaustov [Tomsk PU] 14 Jul 2009 23:15 Try this test case: 4 5 1 2 2 3 3 4 4 2 1 3 5 1 2 3 4 5 The answer is: 1 1 2 3 4 Re: WA#5 hello_world_ww 20 Jan 2013 09:14 my code do that is right ,but... wa 5 Snayde [Shevchenko NUK] 19 Nov 2013 22:40 Try this test: 4 4 1 2 1 2 2 3 3 4 3 1 2 3 Answer: 1 2 3 my program run all the test and they are all corret | Wrong answer!!! Help pls | Levchuk_vs16 | 1502. Domino Dots | 23 Jun 2019 16:26 | 2 | var n:integer; s:real; begin read(n); s:=(n+2)*((n+1)*n)/2; write(s); end. Use "longint" and not "integer" or "real". | No subject | Asif Abdullah | 1068. Sum | 23 Jun 2019 10:58 | 1 | Edited by author 23.06.2019 11:35 | what is wa 3? here is my code! | john | 1149. Sinus Dances | 23 Jun 2019 02:44 | 1 | #include<iostream> using namespace std; void sin (int n,int i) { if(i==n+1) return ; else { if(i==1) { cout<<"sin("<<i; sin(n,i+1); } else if(i%2==1) { cout<<"+sin("<<i; sin(n,i+1); } else { cout<<"-sin("<<i; sin(n,i+1); } cout<<")"; } } void sol( int n,int i) { if(i==n) return; if(i==1) for(int i=1;i<n;i++) cout<<'('; sin(i,1); cout<<'+'<<n-i+1<<')'; sol(n,i+1); if(i==1) { sin(n,1); cout<<"+1"; } } int main () { int n; cin>>n; sol(n,1); } | Algo | Baurzhan | 1748. The Most Complex Number | 22 Jun 2019 21:25 | 9 | Algo Baurzhan 26 Jan 2010 11:48 Can somebody tell me how solve this problem? what is test19? maybe some wrong in test19 It can be solved using backtracking :) Re: Algo Igor Mihajlovic 3 Apr 2010 15:39 can anyone tell me what algo for this problem Re: Algo Artem Khizha [DNU] 28 Jul 2010 17:25 > can anyone tell me what algo for this problem I can, though my approach wasn't so easy. I used precalculations. My way is to generate all pairs (N, P), where P = 1, 2, ... - complexity of number and N - such minimal number, that has exactly P divisors. How to do this with such large inputs? Solve another problem: recover N, if you know P. I used backtrack there, but still I'm wondering whether there is a more beautiful way. First I wrote a recursive function that tries all v=2^a * 3^b * 5^c * 7^d * 11^e * ... with a>=b>=c>=... It generates +- a million possibilities and takes around 300 ms for each case. So I got TLE with 100 cases. Then I wrote code that reads all the n values and sort them. Then I call the recursive function with 10^18. I added a binary search to it that finds the smallest n greater or equal to v and update the best result for it. When the recursive function returns, I update the results for the larger values of n with the smaller results. And then I output the results in the same order as the input. All in less that 50 lines of C++. Re: Algo Keshav Sharma 22 Jun 2019 21:25 I think u can safely assume that that there is no number with power>10 so 10>=a>=b>=c>=d... and now I think u will get AC without doing anything else. Plus small small optimisation.. like breaking at a point if current no. > query(which is obvious to do so) and other such small small optimisation will do. Other thing is to check if ur current no. doesnt exceed the long long range (u can only check by using log()...) Re: Algo Timur_Bekibaev 31 Jan 2010 21:14 Баур, эта задача решатся "в лоб" Re: Algo SamGTU7_Kareva Nadezhda Vladimirovna 12 Jun 2013 23:56 | If you WA#5 using hashing... | Myrcella | 1354. Palindrome. Again Palindrome | 22 Jun 2019 18:41 | 1 | It may be caused by conflicts... (Sorry for my poor English | WA on test 4 | abid1729 | 1079. Maximum | 22 Jun 2019 13:45 | 1 | what is test 4. plz help me. my code is below #include<bits/stdc++.h> using namespace std; int main() { long n=1000,i,k; long long a[100000]; a[0]=0,a[1]=1; for(i=2;i<n;i=i+2){ k=i/2; a[i]=a[k],a[i+1]=a[k]+a[k+1]; } cin>>n; while(n){ cout<<*max_element(a,a+n+1)<<endl; cin>>n; } } Edited by author 22.06.2019 13:46 |
|
|