Common Board| Show all threads Hide all threads Show all messages Hide all messages | | Java solution exists | Fyodor Menshikov | 1306. Sequence Median | 26 Jan 2014 19:26 | 17 | Sent Fyodor Menshikov 31 Jan 2009 20:09 Thanks Scalar 31 Jan 2009 22:40 Edited by author 07.02.2009 10:56 Solve it first in any language, only then ask for my solution. Edited by author 08.02.2009 03:20 Hints: 1. Do not use many 'new' operators. I used only one int array to store data. 2. Avoid PrintWriter.printf/String.format for writing answer, it may be written using only int arithmetic. 3. Read input using StreamTokenizer or the following Scanner: class Scanner { InputStream in; char c; Scanner(InputStream in) { this.in = in; nextChar(); } void asserT(boolean e) { if (!e) { throw new Error(); } } void nextChar() { try { c = (char)in.read(); } catch (IOException e) { throw new Error(e); } } long nextLong() { while (true) { if ('0' <= c && c <= '9') { break; } asserT(c != -1); nextChar(); } long value = c - '0'; nextChar(); while ('0' <= c && c <= '9') { value *= 10; value += c - '0'; nextChar(); } return value; } int nextInt() { long longValue = nextLong(); int intValue = (int)longValue; asserT(intValue == longValue); return intValue; } } My Java solution better from all Java solutions: 0.171 s time & 862KB memory. I use only System.in & System.out. good like. Use something like System.out.print( (a+b)/2 ); if ( (a+b) % 2==0){ } else { System.out.println(".5"); } instead of System.out.printf or String.format if you want to get AC I got AC with 858KB memory I have tried two methods to solve this problem: 1) using PriorityQueue 2) sorting using Arrays.sort but bumped into MLE on 7th test again and again :( so more hints are welcomed :) Did you write your own heap or u are using complete different approach? Can anyone tell me how memory 1 Mb can be exeeded if I use the PriorityQueue with size = N/2+1 and four int variables ? How many bytes are consumed by one element of PQ ? TIA. I cannot solve this problem. could you tell me more hint via my email please? here is my e-mail => holyporing@hotmail.com i really want to do this. Thank you. how to send solution with java? in language list, i haven't got java. Please, send your java solution on e-mail lo.de.wash.boleem@mail.ru Edited by author 26.01.2014 19:26 Edited by author 26.01.2014 19:27 | | Задача 1001 Wrong answer | Айарпи | 1001. Reverse Root | 26 Jan 2014 17:05 | 1 | В FPC все работает, здесь же ... Вот код program f1; var f,f2:text; i,j:integer; a:array[1..130000] of real; begin assign(f,'input.txt'); reset(f); i:=0; While not eof(f) do begin inc(i); read(f,a[i]); end; close(f); assign(f2,'output.txt'); rewrite(f2); For j:=i downto 1 do writeln(f2,sqrt(a[j]):0:4); close(f2); End. | | ac (cpp) | lhyx1990 | 1209. 1, 10, 100, 1000... | 26 Jan 2014 16:59 | 1 | #include <iostream> #include <math.h> using namespace std; bool isOne(int n); int main(int argc, const char * argv[]) { int n; cin >> n;
int *nums = new int[n]; for (int i = 0; i < n; i++) { int k; cin >> k; nums[i] = k; } for (int i = 0; i < n; i++) { int index = nums[i] - 1; if (isOne(index)) cout << 1 << " "; else cout << 0 << " "; } delete [] nums; } bool isOne(int n) {
double ans = (sqrt((double) 8 * n + 1) - 1) / 2; int r = (int) ans; if (r * (r + 1) / 2 == n) return true; return false; } | | time limit exceeded | lhyx1990 | 1209. 1, 10, 100, 1000... | 26 Jan 2014 16:27 | 1 | #include <iostream> using namespace std; bool isOne(int n); int main(int argc, const char * argv[]) { int n; cin >> n;
int *nums = new int[n]; for (int i = 0; i < n; i++) { int k; cin >> k; nums[i] = k; } for (int i = 0; i < n; i++) { int index = nums[i] - 1; if (isOne(index)) cout << 1 << " "; else cout << 0 << " "; } delete [] nums; } bool isOne(int n) { int indexOf1 = 0; for (int i = 0; indexOf1 < n; i++) { indexOf1 += i; if (indexOf1 == n) return true; } return false;
} Edited by author 26.01.2014 16:27 | | ac (cpp) | lhyx1990 | 1068. Sum | 26 Jan 2014 15:51 | 1 | #include <iostream> using namespace std; int main(int argc, const char * argv[]) { int n; cin >> n; if (n >= 1) { cout << n * (n + 1) / 2; } else { cout << - (-n * (-n + 1) / 2) + 1; }
} | | ac c++ | lhyx1990 | 1639. Chocolate 2 | 26 Jan 2014 15:08 | 1 | ac c++ lhyx1990 26 Jan 2014 15:08 #include <iostream> using namespace std; int main(int argc, const char * argv[]) { int m, n; cin >> m >> n;
int num = m * n - 1;
if (num % 2== 1) { cout << "[:=[first]"; }
else { cout << "[second]=:]"; }
} num is total number of splits | | что не так? | roman_khapov | 1001. Reverse Root | 26 Jan 2014 03:55 | 3 | Код: #include <iostream> #include <cmath> #include <vector> using namespace std; int main( int argv, char *argc[] ) { long long n; vector<long long> v; while ( cin >> n ) { v.push_back(n); } for ( int i = v.size() - 1; i >= 0; i--) { cout << sqrt(v[i]) << endl; } return 0; } wrong answer на первом тесте Edited by author 29.12.2013 21:39 Просто поменяй long long на long double везде. Ну и про 4 цифры не забыть после запятой Upd: и sqrt лучше поменять на sqrtl для избежания проблем. Edited by author 26.01.2014 03:56 | | Hints (+) {just use 3 shortint} | Locomotive | 1191. Catch the thief! | 25 Jan 2014 13:18 | 4 | Hi I had solved this problem with just 3 shortint... It so easy look other messages in this problem to understand what is happening! All you need is: dec(n,n mod y); where y is that K[i]`s which described in problem. nothing is special for this problem... With best Wishes Aidin_n7@hotmail.com This way is so incredible! Could you explain why it's correct and what does this problem mean? Thanks. Obviously, distance between cop and robber can only decrease. If cop cannot overtake robber at current stage(if L >= k[i]), so new min distance in the best case for policeman will be equal to (minimum amount of trams)*k[i]. And minimum amount of trams is L mod k. For instance, L=7, K=3, so policeman will miss at least 2 trams: robber will reach tram stop, wait at most 3 mins and go away. Policeman will miss next tram, and he should wait another 2 mins before next tram will come. So, new L = 2*K = 6. But minimum amount if trams is [L/k[i]], not L%k[i] Oo | | To admin: wrong English version | ASK | 1933. Guns for Battle! | 25 Jan 2014 05:05 | 1 | "gunners" must be "guns" in "one integer n that is the number of gunners on board" | | Precision problem... again | Vlad | 1084. Goat in the Garden | 25 Jan 2014 01:54 | 1 | #include <iostream> #include <fstream> #include <cmath> #define PI 3.14159265358979323846 using namespace std; #ifndef ONLINE_JUDGE #define cin fin ifstream fin("input"); #endif double N, R; int main() { cin >> N >> R; N /= 2.0;
if (R <= N) { cout << PI * R * R << '\n'; return 0; } if (R >= N * sqrt(2.0)) { cout << 4.0 * N * N << '\n'; return 0; }
double A, B, C; A = N; C = R; B = sqrt(C * C - A * A); double angle = 90.0 - (acos(A / C) * 180.0 / PI) * 2.0;
printf("%.3lf\n", 4.0 * (A * B + PI * R * R * angle / 360.0)); } This program works fine on all the tests I saw on the forum. But I get WA #1 probably because of the wrong precision. I printed the value with 4 and 6 decimals but I get the same WA #1. Could anyone tell me please how can I solve the "error" ? It's annoying to have a good solution and take WA. Thanks a lot! LATER EDIT: It seems I succeeded with such a function: inline void precise(double X, const int &decimals) { cout << (int)(X); cout << '.'; X = X - (int)(X); for (int i = 1; i <= decimals; ++i) { X = X * 10.0; cout << (int)(X); X = X - (int)(X); } cout << '\n'; } ... precise((double)(4.0 * (A * B + PI * R * R * angle / 360.0)), 3); Have fun! Edited by author 25.01.2014 04:19 | | Why stack overflow? Help me, please! | werelaxe | 1510. Order | 24 Jan 2014 22:35 | 2 | #include<iostream> using namespace std; int main () { int n,a[500000],d,max=0,maxi; cin>>n; for (int i=0;i<n;i++) { cin>>d; a[d]++; if (a[d]>max) { max=a[d]; maxi=d; } } cout<<maxi; return 0; } 0 ≤ K ≤ 10^9 Edited by author 20.05.2014 20:54 | | ac c++ | lhyx1990 | 1197. Lonesome Knight | 24 Jan 2014 20:07 | 1 | ac c++ lhyx1990 24 Jan 2014 20:07 #include <iostream> #include <stdio.h> #include <vector> using namespace std; class Place { public: char x; int y;
bool isOnboard() { if (x < 'a' || x > 'h' || y < 1 || y > 8) return false; return true; }
Place(char x, int y) { this->x = x; this->y = y; }
}; int main(int argc, const char * argv[]) { int N; cin >> N;
vector<Place> places;
for (int i = 0; i < N; i++) { char x; int y; cin.get(x);
if (x == '\n') { i--; continue; }
cin >> y;
Place place (x, y); places.push_back(place);
}
for (int i = 0; i < N; i++) { Place place = places[i]; int moves = 0;
//left 2 up 1 place.x -= 2; place.y -= 1; moves += place.isOnboard();
//left 2 down 1 place.y += 2; moves += place.isOnboard();
//right 2 down 1 place.x += 4; moves += place.isOnboard(); //right 2 up 1 place.y -= 2; moves += place.isOnboard(); //right 1 up 2 place.x -= 1; place.y -= 1; moves += place.isOnboard(); //left 1 up 2 place.x -= 2; moves += place.isOnboard(); //left 1 down 2 place.y += 4; moves += place.isOnboard(); //right 1 down 2 place.x += 2; moves += place.isOnboard();
cout << moves << endl;
}
} Edited by author 24.01.2014 20:07 | | Solution for larger input | mylyanyk.ivan[Lviv_NU] | 1152. False Mirrors | 24 Jan 2014 14:31 | 3 | Hi, I'm interested if there is solution for larger N like 1000 and even more? Thanks. Edited by author 25.03.2013 01:28 Edited by author 24.01.2014 14:55 Edited by author 24.01.2014 14:33 | | Why WA1? | Andrew Sboev [USU] | 1471. Distance in the Tree | 24 Jan 2014 13:26 | 4 | Why WA1? Andrew Sboev [USU] 8 Jul 2012 16:56 I'm using Floyd-Warshall algorithm, and my program correctcly passes different tests, but i have WA1. Why? Floyd-Warshall algorithm? But it's too slow. Use LCA. Maybe it is slow, but it works correctly :)Should be TLE, not WA1 :) Use std::cout. I had such problem when I used <fstream> | | wrong answer on test 1 | kirill | 1471. Distance in the Tree | 24 Jan 2014 13:18 | 1 | My program works true on test from conditions and on two my tests. Tell me please, what's a problem? | | What's the correct answer for these tests? Have a look... | exwRabbits_AlMag(VNTU) | 1244. Gentlemen | 23 Jan 2014 21:29 | 8 | 1) 3 2 1 2 2) 614 13 627 861 527 911 751 658 568 846 998 188 923 426 685 3) 1560 19 580 594 644 62 963 718 291 532 293 77 356 984 384 182 986 915 18 671 920 4) 555 27 816 170 523 595 471 313 970 877 465 50 819 517 721 143 394 872 905 462 346 639 193 902 945 927 133 401 410 5) 800 15 10 20 30 40 50 60 70 80 90 100 110 120 130 200 350 6) 1458 17 802 204 451 575 158 168 247 15 50 100 1000 257 354 125 358 125 268 Thanks. Edited by author 22.06.2006 19:08 Edited by author 23.06.2006 12:20 My answer: 1. -1 2. 1 2 3 4 5 6 7 8 9 11 13 3. 2 3 4 5 6 8 9 10 11 12 13 14 15 16 19 4. 0 At me now wrong answer 12. Give me tests. I used DP, but I have found a mistake{an error} at a conclusion-1. Can give me what that ideas! Help!!! Thanks 1)0 2)1 2 3 4 5 6 7 8 9 11 13 3)-1 4)0 5)-1 6)-1 Your test#1 doesn't match the description that "It's guaranteed that the total weight of all cards in the complete pack is strictly greater than the weight of the incomplete pack." | | NEED translate into RUSSIAN (to admins) | [TDUweAI] daminus | 1058. Chocolate | 23 Jan 2014 20:12 | 2 | Please, write there translated (RUSSIAN) version of this problem!!!! or you can send there for my adress daminus_corp@mail.ru > Thanks!!!! Вам даны координаты вершин полигона, надо найти такую линию, концы которой лежат на сторонах или вершинах многоугольника, что она разделит данный многоугольник на два равных по площади многоугольника. | | Brainbreaking text, brainless task. | Komendantian Grant Mikaelovich SSAU | 1228. Array | 23 Jan 2014 19:52 | 8 | Absolutely right, Grant! I entirely agree with you. Easy when you understand it. It took me the monthes to understand how stupid this problem is. I wanted do this problem with brute force, by recursion, a lot of different ways, until I understood. Any way, this problem is really stupid.)) i solved it but still didn't get what the problem is "Brainbreaking text, brainless task" - exactly It took me 20 minutes to solve it.)) (the hardest part is to read the text and to write the code). )) This problem doesn't help improving any algorithm but it improves your mind to translate your understanding to easy code. (I think) Edited by author 23.01.2014 19:53 | | Why WA#25???? My alg is correct 100%!!! | Akshin Salimov | 1348. Goat in the Garden 2 | 22 Jan 2014 15:05 | 14 | Oh no WA#25! Please help me! var a1,a2,a3,h,s,aa,bb:real; a:array[1..3,1..2] of integer; i,l:integer; procedure readdata; begin readln(a[1,1],a[1,2],a[2,1],a[2,2]); readln(a[3,1],a[3,2],l); end; procedure writedata; begin if aa>=0 then writeln(aa:0:2) else writeln('0.00'); if bb>=0 then writeln(bb:0:2) else writeln('0.00'); end; function d(x1,y1,x2,y2:integer):real; begin d:=sqrt(sqr(x1-x2)+sqr(y1-y2)); end; procedure square; var p:real; begin a1:=d(a[1,1],a[1,2],a[2,1],a[2,2]); a2:=d(a[3,1],a[3,2],a[2,1],a[2,2]); a3:=d(a[1,1],a[1,2],a[3,1],a[3,2]); p:=(a1+a2+a3)/2; s:=sqrt(p*(p-a1)*(p-a2)*(p-a2)); end; begin readdata; square; if (a[1,1]=a[2,1]) and (a[1,2]=a[2,2]) then begin aa:=d(a[1,1],a[1,2],a[3,1],a[3,2]); bb:=aa; end else begin if (a1*a1+a2*a2<a3*a3) or (a2*a2+a3*a3<a1*a1) or (a1*a1+a3*a3<a2*a2) then begin aa:=d(a[1,1],a[1,2],a[3,1],a[3,2]); if d(a[2,1],a[2,2],a[3,1],a[3,2])<aa then aa:=d(a[2,1],a[2,2],a[3,1],a[3,2]); end else begin h:=d(a[1,1],a[1,2],a[2,1],a[2,2]); aa:=s/(0.5*h); end; bb:=d(a[3,1],a[3,2],a[2,1],a[2,2]); if d(a[3,1],a[3,2],a[1,1],a[1,2])>bb then bb:=d(a[3,1],a[3,2],a[1,1],a[1,2]); end; aa:=aa-l; bb:=bb-l; writedata; end. Try this test: ---input -5 0 5 0 1 0 1 ---correct output 0.00 5.00 No, you are mistaken correct answer is 3.00 5.00 Here is explanation: * is 0 point A B C are points. <-----A----*C---B-----> ... ... = 3.00 I dont know how you got 0.00 , please explain, maybe you are right. Edited by author 16.04.2005 23:03 Distance from A up to B = 0 And to get up to point A and B a cord it is necessary to extend on 5.00 Can we discuss this problem via e-mail? akshinioi@yahoo.com Edited by author 17.04.2005 02:15 yes i know russian language. " And to get up to point A and B a cord it is necessary to extend on 5.00 " - I agree with that. But distance between A and B isnt 0, if -5+5=0 that doesnt mean that the distance equal to nil! OR explain in details how did you get this --> "Distance from A up to B = 0 " "... There is a bed of pineapples that he loves very much. The bed is a **line segment** with the ends A and B... " Point C is situated on segment AB, so there are no grounds to stretch the roap - goat anyhow can eat some pine apples, even if rope has length 0. There are infinite amount of pine apples on segment! Mail me to dkorduban[at]ukr[dot]net if you still have questions. Sorry for my English. I'm sorry, I understood my mistake. When I use linear equation for this case, i got WA#3!!! I dont know why. Please help me, how to make my program to get AC? 1) Read this nice article (in Russian): http://g6prog.narod.ru/cgeom.rar 2) Completely rewrite your program. Try to create more general program, without dozens of special cases. That's general and very useful rule (imho) for geometrical problems. For example, there is only one special case in my program - when A = B. Of course, I can send you my AC code, if you need. Thx for this test! WA #4 fixed now :) Послано Korduban [Kiev] 16 апр 2005 19:04 Try this test: ---input -5 0 5 0 1 0 1 ---correct output 0.00 5.00 Edited by author 07.11.2013 20:49 Btw, some pretty test is: 5 0 5 0 1 0 1 Correct output is 3.00 3.00 | | WA 6.... | Pushkar Mishra | 1452. Pascal vs. C++ | 22 Jan 2014 11:18 | 2 | WA 6.... Pushkar Mishra 21 Mar 2013 10:02 Can anybody suggest me the 6th test case? В натуре спотыкается.В чем соль? Где зарыта собака? Edited by author 22.01.2014 11:56 |
|
|