Common BoardShow all threads Hide all threads Show all messages Hide all messages  Add new test, please.  XraY  1103. Pencils and Circles  24 Feb 2020 12:16  3  5 0 100000000 1 100000000 1 99999999 1 100000000 0 100000000 I think, this answer is wrong: 0 100000000 1 100000000 1 100000000 But my AC program doesn't think so. And I still ask you to make the third test without trash in the end. Thanks for pointing out the trash in the end of 3rd test case!  Can you give some useful tests?  👑OmegaLuL230👑  1923. Scary Politics  23 Feb 2020 18:26  1  I have WA#2 and i don't understand what is wrong.. If I understood problem correctly, my program works well on all tests, which I tried. Edited by author 23.02.2020 18:27  Understanding the solution  MARAZ MIA  1876. Centipede's Morning  22 Feb 2020 03:06  1  After so many calculation and math I have solved the problem..... Here we can have two worst cases... Case 1: having all the right shoes first.so here needed time is 2*b and we have now all the left shoes remaining...so total time is 2*b+40... Case 2: we may have 39 right shoes so time needed here is (39*2=78)...then we have only one right foot left but we may encounter all the left shoes and here needed time is 40+2*(a40)....> 40 for the first 40 shoes and 2*(a40) is for the remaining shoes as they needed to be thrown away...then we have the only one right foot left and it need 1 second... so total time = 78+40+2*(a40)+1 = 119+2*a80 = 2*a39 ans=max(Case 1,Case 2) Edited by author 22.02.2020 03:07  Hint  👨💻tproger👨💻[GTGU]  2087. Trains  21 Feb 2020 22:35  2  Hint 👨💻tproger👨💻[GTGU] 6 Jun 2019 12:06 For each vertex in tree find the nearest vertex from the way to root, in which we need to change direction. If such vertex doesn't exist, let it be 1. Let's call this vertex as bad[V], where V  some vertex in tree. To answer on query for vertex X, let's travel in "bad" array from X until we meet bad[X]=1. Let's save visited vertices (excluding query vertex X) to some array (let's call this array "change"). Now it's quety obvious, that we need to change directions only in those visited vertices to "activate" path from root to leaf. Before changing values in "bad" array for vertex from X to root, let's take some vertex V from "change" array. Before query there was a set of vertices which have the same "bad" vertex as a V (bad[V]=bad[V_1]=bad[V_2]=...=bad[V_n], V_i  vertex from the set), and now we need to change their "bad" value to V, because we change direction in vertex V. Finally, we need to set bad[V]=1 to all vertices from X to root. To do all operations efficiently we can use heavylight decomposiotion + segment tree. So, the total complexity would be O(N + Q*(log(N))^2), N  number of vertices in tree. Edited by author 06.06.2019 17:11 Re: Hint Gilles Deleuze 21 Feb 2020 22:35 Straightforward Link/Cut Tree solution. Just dfs the input grid and build the tree graph represented by LCT; represent paths as bamboo splay trees: just make dfschild the right child if turnout is good and do nothing otherwise. All parents in dfstree that do not satisfy turnout make path parents (see LCT terminology). Now each query is just a single access—sometimes called expose—operation that saves all path parents on the path.  Why wrong answer?  Alexander  1025. Democracy in Danger  21 Feb 2020 01:55  2  #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int a; int n; cin >> n; vector<int> v; for (int i = 0; i < n; i++) { cin >> a; v.push_back(a); } n = 0; sort(v.rbegin(), v.rend()); for (int i = v.size()1; i > (v.size()2) / 2; i) n += (v[i]+1)/2; cout << n << endl; } You should iterate from v.begin to v.end. No the reverse way.  Proper hints for all the test cases out there  samio  1025. Democracy in Danger  21 Feb 2020 01:53  1  Sort the n teams and take the first (n/2 + 1) team's people (by people i mean, array[i]/2 + 1). If you have problem understanding what i have just written or for better understanding, give this a go : https://ideone.com/vD6SAm  Proper hints for the the test cases out there  samio  1020. Rope  21 Feb 2020 01:27  1  Well, you have to know how to determine the distance between two points first. It can be calculated by, dis = sqrt((x1x2)^2+(y1y2)^2). You can say that, we can just calculate the distance in between the points but why the raidius of the nails are given. Its because the rope is wrapped around each and every nails. But the rope is not in fully contact with nails. The more nails we get, the less contact we have in between rope and nails. The amount of which the rope is in contact with nail is : s = parameter of a nail/the number of nails. So we are just required to print out : d(d is the sum of the distance between them) + number of nails * s(s is the amount which the rope is in contact with nails) If you have problem understanding my word or for better understanding, give this a go : https://ideone.com/t1M3rK Edited by author 21.02.2020 01:31  Why I get a runtime error (C#)  Stepan  1001. Reverse Root  21 Feb 2020 00:39  1  List<long> coll = new List<long>(); List<decimal> answer = new List<decimal>(); List<string> a = new List<string>(); string line; while (true) { line = Console.ReadLine(); answer.Clear(); coll.Clear(); a.AddRange(line.Split()); a.RemoveAll(x => x.Equals("")); for (int i = 0; i < a.Count; i++) { coll.Add(long.Parse(a[i]));
} for (int i = 0; i < coll.Count; i++) { var d = (decimal)Math.Sqrt(coll[i]); answer.Insert(0, d); } Console.Clear(); for (int i = 0; i < answer.Count; i++) {
Console.WriteLine(answer[i].ToString("0.0000##")); } }
Edited by author 21.02.2020 00:40  Proper hints for all the test cases out there  samio  1014. Product of Digits  21 Feb 2020 00:34  1  This problem can be solved using greedy technic. Method is to divide the given number from 9 to 2. Each time we will continue to divide and update the number as we go. We will keep dividing N with the same number utill its impossible to do so.And for each division we will save the number which was divisible by given number. And by "save" i mean pushing the number in a stack or a in a vector or an array. If you are using other than stack you might print out the numbers in a reverse manner. And when we are getting "1"? I already wrote that, we keep updating the number. so after we pass the 9 to 2 loop, we should be left with a value of 1 in the variable N ( given number ). Incase N!=1 we are just printing "1". For the case N=1 or N=0? for the case 1 you should just print "1" and for the case 0 print "10", we can not print 01 since this refers to number, 1. If you have problem understanding what i have just written or for better understanding, give this a go : https://ideone.com/709cog Edited by author 21.02.2020 00:34 Edited by author 21.02.2020 00:38 Edited by author 21.02.2020 00:41  WA on 25  Rami Ismael  2034. Caravans  20 Feb 2020 22:37  1   is java's BigDecimal acceptable?  Faeton (Kyiv  Mohyla Academy)  1605. Devil's Sequence  20 Feb 2020 21:30  7  I solve reccurence, then pow to n(which takes log n to quickpow), but it's also TL. How can i improve this not writing my own long arithmetic? It can be solved only with 2 divisions in BigDecimal, but answer length is about 32000 so [maybe] toString gives TLE on conversion binary data to decimal representation. If somebody knows, how to solve this problem  please tell me 2^n = 10^(n*lg(2)) My AC solution: int n0 = (int) (Math.log10(2f) * (n  1)); int n1 = (int) (Math.log10(2f) * n); int n2 = (int) (Math.log10(2f) * (n + 1)); int len = n1; if (n1 == n2 && n1 == n0 + 1 && n % 2 != 0) { len = n0; } Answer is len. I thought that this problem's solution is : t= (n(n%10)) /4 +1 if(n>=30) { t=t+1; x=nn%10; if(n>39&&((x/10)%2)) t=t+(x30)/20; if(n>49&&((nn%10)%4==0)) t=t+(x40)/20; } t= t+ (n%10)/4; cout<<t; but it got WA#8. And i don't understand "if(n==1 && n1==n0+1 && n%2!=0)" statement are for what tests? Would you mind explaining for me! Thanks! bve, your way is brilliant. Thank you! bve, any links to why it works?  Weak test 2  FatalityNT  1433. Diamonds  20 Feb 2020 05:36  1  My submission (8764478) goes wrong on the following tests, but it has an AC on the judge system. The right answer for all test cases below is "equal". RRGB GRBR RRGY GRYR RRBG BRGR RRBY BRYR RRYG YRGR RRYB YRBR RGRB BRGR RGRY YRGR RGBR GRBR RGYR GRYR RBRG GRBR RBRY YRBR RBGR BRGR RBYR BRYR RYRG GRYR RYRB BRYR RYGR YRGR RYBR YRBR GRGB BGRG GRGY YGRG GGBR BGRG GGBY BGYG GGYR YGRG GGYB YGBG GBRG BGRG GBGY YGBG GBYG BGYG GYRG YGRG GYGB BGYG GYBG YGBG BRBY YBRB BGBY YBGB BBYR YBRB BBYG YBGB BYRB YBRB BYGB YBGB  Weak Test cases  sagsango  2034. Caravans  20 Feb 2020 05:29  1  For this Test case , AC solution gives output 2 which should be 1. 25 28 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 1 5 19 19 20 20 21 21 22 22 23 23 24 24 25 25 14 15 22 6 22 1 10 22 Edited by author 20.02.2020 05:33 Edited by author 20.02.2020 05:33  WA #20  👑OmegaLuL230👑  1648. Yachts  17 Feb 2020 23:29  1  WA #20 👑OmegaLuL230👑 17 Feb 2020 23:29 Help pls, I have WA #20 can u give me a test? (all answers of my program on tests which i generated are right)  Memory limit exceeded for test case 7  Foysal Ahammed  1306. Sequence Median  17 Feb 2020 18:19  2  #include <bits/stdc++.h> #include<cstdio> #include <queue> #define pb push_back #define mp make_pair //Macro #define eps 1e9 #define pi acos(1.0) #define ff first #define ss second #define re return #define QI queue #define SI stack #define SZ(x) ((int) (x).size()) #define all(x) (x).begin(), (x).end() #define sq(a) ((a)*(a)) #define distance(a,b) (sq(a.xb.x) + sq(a.yb.y)) #define iseq(a,b) (fabs(ab)<eps) #define eq(a,b) iseq(a,b) #define ms(a,b) memset((a),(b),sizeof(a)) #define G() getchar() #define MAX3(a,b,c) max(a,max(b,c)) #define II ( { int a ; read(a) ; a; } ) #define LL ( { Long a ; read(a) ; a; } ) #define DD ({double a; scanf("%lf", &a); a;}) double const EPS=3e8; using namespace std; #define FI freopen ("input_B.txt", "r", stdin) #define FO freopen ("output_B.txt", "w", stdout) typedef long long Long; typedef long long int64; //For loop #define forab(i, a, b) for (__typeof (b) i = (a) ; i <= b ; ++i) #define rep(i, n) forab (i, 0, (n)  1) #define For(i, n) forab (i, 1, n) #define rofba(i, a, b) for (__typeof (b)i = (b) ; i >= a ; i) #define per(i, n) rofba (i, 0, (n)  1) #define rof(i, n) rofba (i, 1, n) #define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i) #define for1(i, a, b) for(int i=a; i<b; i++) template< class T > T gcd(T a, T b) { return (b != 0 ? gcd(b, a%b) : a); } template< class T > T lcm(T a, T b) { return (a / gcd(a, b) * b); } #define __(args...) {dbg,args; cerr<<endl;} #define __1D(a,n) rep(i,n) { if(i) printf(" ") ; cout << a[i] ; } #define __2D(a,r,c,f) forab(i,f,r!f){forab(j,f,c!f){if(j!=f)printf(" ");cout<<a[i][j];}cout<<endl;} signed main () { ios_base :: sync_with_stdio(0);cin.tie(0);cin.tie(0); int n; unsigned int a; priority_queue <unsigned int> pq; scanf("%d", &n); bool odd = (n%2==1); for(int i=n/2; i>=0; i){ scanf("%u", &a); pq.push(a); } n=n/2+1; for(int i=0; i<n; i++){ scanf("%u", &a); pq.push(a); pq.pop(); } if(odd)printf("%u\n", pq.top()); else{ a=pq.top(); pq.pop(); // cout << fixed << setprecision(1) << (a+pq.top())/2.0 << endl; printf("%.1f\n", (a + pq.top() ) / 2.0); } return 0; } Priority queue uses vector under the hood. How many times vector resized while first for() executed  unknown, what final vector capacity  unknown, was all vector buffers except last freed or they still kept by allocator  unknown. I'd recommend to not use priority queue at all, I'd rather implement custom bike using fixed size buffer and std heap functions  test 1 dan qaytvotti xatosi qatta?  Chornovek  1893. A380  17 Feb 2020 14:26  2  VAR s:string; k,n,l,c:Longint; begin read(s); l:=length(s); val(s,n,c); if (n<3) and (n>0) then begin k:=0; case s[l] of 'a','A': write('window'); 'D','d': write('window'); 'b','B': write('aisle'); 'c','C': write('aisle'); end; end; if (n>=3) and (n<=20) then begin k:=0; case s[l] of 'a','A': write('window'); 'f','F': write('window'); 'b','B': write('aisle'); 'd','D': write('aisle'); 'E','e': write('aisle'); 'c','C': write('aisle'); end; end; if (n>=21) and (n<=65) then begin k:=0; case s[l] of 'a','A': write('window'); 'k','K': write('window'); 'g','G': write('aisle'); 'd','D': write('aisle'); 'h','H': write('aisle'); 'c','C': write('aisle'); 'b','B': write('neither'); 'e','E': write('neither'); 'f','F': write('neither'); 'J','j': write('neither'); end; end; if n>65 then write('neither'); end. Edited by author 20.11.2012 23:14 Please, write your messages in English, because it's international language. We, Russians, don't understand O'zbek  hahaha  holtaf  1044. Lucky Tickets. Easy!  17 Feb 2020 06:55  6  #include<iostream> using namespace std; int main() { int n; cin>>n; switch(n) {case 2: cout<<10;break; case 4: cout<<670;break; case 6: cout<<55252;break; case 8: cout<<4816030;break; } return 0; } nnn Mohigul Rahmonova 3 Feb 2012 16:53 Edited by author 03.02.2012 16:53 print(([0,10,670,55252,4816030])[int(input())//2]) hahahahahahaha  Two solutions  Teacher30 (Burunduk1)  1621. Definite Integral  16 Feb 2020 23:45  3  Solution #1: AC in 0.8 sec Just calculate sum using Gauss's method. Int[1..1] f(x)dx ~= (5*f(sqrt(3/5)) + 8*f(0) + 5*f(+sqrt(3/5))) / 9 Number of parts, N = (int)7e6 Length of part number i = (1e4)*koef^i, where koef = 1 + x/N. Try some different x = 0.1 ... 10, and get AC =) Solution #2: WA 11 on MSVC or AC on Java, Pascal, GNU C++ http://en.wikipedia.org/wiki/Residue_theorem says that we have to find all complex roots of the polynom. I do not like exact formulas for degree 3 and 4. There is numerical way to find all complex roots for any degree of polynom. Just take point z = (0,0) and shift it to any direction in such a way that P(z+shift) < P(z). Shift it while P(z) > eps. Now z is a root. This method works not only for polynoms, it works even for arbitrary "holomorphic function" (see Complex Analysis). Prove is smth like this http://en.wikipedia.org/wiki/Maximum_modulus_principle The only thing that I need now  to calculate f(z) for any complex z. And using only "double" of Microsoft Visual C++ I can't. I have no enough precision and get WA 11 =( Using BigDecimal (java), extended (pascal) or long double (GNU C/C++) this method gets AC (the task is from Petrozavodsk, so I have original tests). P.S. 2 Admins: Ну сколько можно добавлять задачки с контестов, где у С++ программистов был под рукой long double, и это было важно. Даешь GNU C/C++! Edited by author 27.10.2012 08:08I found many other ways. 1)Monte Carlo  slow for this problem 2)Separation of real and complex roots. Can be used to solve this problem. Binary search for Re(z)=alfa, Re(z)=beta, Im(z)=gamma, Im(z)=delta Березин И.С., Жидков Н.П. Методы вычислений, Т.2. М.: ГИФМЛ, 1959. 3)Ferrari method. Куликов Л.Я. Алгебра и теория чисел 4)Barstow method. It's numeric iterative method. Саманчук_билеты_с_ответами.pdf Численные методы I use combination from 3): binary search for yo then formulas Edited by author 12.08.2018 21:04 https://en.wikipedia.org/wiki/Adaptive_quadrature with Gaussian method to estimate value of definite integral: approx_integrate(Func f, long double l, long double r) { long double A = sqrtl(3.0l/5.0l)/2, x1=0.5A, x2 = 0.5+A; return (5*f(l*x1 + r*x2) + 8*f((l+r)/2) + 5*f(l*x2+r*x1))/18 * (rl); } AC in 0.015. That is, you don't even need to think to solve this problem. Edited by author 16.02.2020 23:48  ХИНТ  Toshpulatov (MSU Tashkent)  2148. Insane Shot  16 Feb 2020 19:42  1  ХИНТ Toshpulatov (MSU Tashkent) 16 Feb 2020 19:42 Подумайте о пересечение прямой из данных двух точек с окружностью а потом о треугольниках Edited by author 16.02.2020 19:45  Hope these test cases will help u... :)  ইলহাম আল মুসাব্বির  1104. Don’t Ask Woman about Her Age  16 Feb 2020 14:36  5  Try these test cases. Test 1: 0 Ans:2 Test 2: 1 Ans:2 Test 3: 2 Ans:3 Test 4: Z0Z Ans:36 Test 5: 21 Ans:4 Test 6: ZIZ Ans:No solution. (Don't forget to put the fullstop at the end!!!) Test 7: AERGUFG12312OP Ans:32 Test 8: 234DFG67 Ans:23 And this problem can be solved within int range. Edited by author 09.12.2015 20:14 only test 7 I can't get right ans. I have 33 And WA4 Removed my post, because apparently I can't alphabet :) Edited by author 12.07.2016 14:45 IN TEST CASE 2, FOR INPUT 0 , WHY ANS IS ONLY 2 IT CAN BE 1,2,3,4,5.......35. BECAUSE ZERO IS DIVISIBLE BY ALL. You can't divide by 0! So 1 isn't a solution and therefore it's 2: 

