|
|
Common Board1. the graph forms a tree 2. you need to give this tree direction (since the given tree is undirected) 3. the longest path starting at node k is the maximum of 2 values: the maximum path starting at k and going DOWN (a tree has no cycles so you can solve this easily in linear time, i used simple DP) and the maximum path by going UP from k. "the maximum path by going UP from k." What do you mean by this? How to calculate the maximum path by going up from k Just invert directions of all edges and calculate the maximum path by going DOWN form k. Realization of this thing is much easier than its description. Just cut off leafs of tree step by step while count of nodes >2! Edited by author 25.06.2005 14:44 Far not the fastest solution, but passed (0.375 sec): 1. make a bidirectional graph, connectivity of which will be kept in an array of vectors 2. start dfs from each of the verticies which are not leaves and calculate the longest path 3. Note that if there are 2 vertices, the answer is always "1 2" The solution might run in O(N*(N+M)) time, as I guess Edited by author 15.02.2010 13:13 Edited by author 15.02.2010 13:13 Looks like std::vector::rend() does not return const_reverse_iterator. I have got CE on the line for( std::vector< Spot >::const_reverse_iterator it = spots.rbegin(); it != spots.rend(); ++it ) but for( std::vector< Spot >::/*const_*/reverse_iterator it = spots.rbegin(); it != spots.rend(); ++it ) was ok. Здраствуйте! Задача: Написать такой класс А, чтобы данный фрагмент кода компилировался и работал. А a1; A a2=a1+2+A(3); Код: # include <iostream> using namespace std; class A{ private: int x; public: A():x(0){};//Constructor A(int y):x(y){}; A(const A & y) //Copy constructor { x=y.x; return *this; } A operator+(A y) const;
};
A A::operator+(A y) const{ return A(x+y.x); }
int main()
{ A a1; A a2=a1+2+A(3); return 0; }
Hi. #include<iostream> #include<math.h> #include<iomanip> using namespace std; int main(){ int i=0; double *a=new double[8000000]; double c; while(cin.eof()==false){ cin>>c; a[i]=sqrt(c); i++; } i--; i--; while(i>=0){ cout<<setprecision(4000)<<a[i]<<'\n'; i--; } return 0; } WA 2. Why? can anyone please tell me what to output if N=1 is given? well, when I added to code: if N=1 then begin writeln('0'); halt; end; I've got WA on test 1. With out such code I've got WA on test 7. So, test 1 - N=1. But I'm not sure in correct solution: my program outputs 4 3. But 4 can be got only like: 4 = 1 + 3; So, then change is already included in paying. Smth strange, don't you think so? I had WA1 with output 0 for N=1. With 4 3 I passed 1st test but failed with WA9 which is something like 12 or 81. So, amount of tips must be POSITIVE. Edited by author 01.08.2008 00:48 why when n=1 answer 4 3? i think it must be 3 2!! 2 can't be representeted of sum numbers(3^n, where every N can be used _1 time_). input1 : 05 26 2C 52 69 14 3F 31 4C 2A 69 65 1A 26 4B input2 : 61 07 28 41 3B 63 07 2C 52 22 21 69 72 0B 42 5E answer : 41 43 4D 20 49 43 50 43 20 4E 45 45 52 43 27 32 (P.S : I put the spaces only for that is easy to read && understand) Why is first 2 bytes in answer is 41...? Cuz, 61h xor 20h = 41h (20h -> 32d = ' ' = Space); How to find the second,third,...? 41h xor 05h = 44h 44h xor 07h = 43h(Second 2 bytes); 43h xor 26h = 65h 65h xor 28 = 4Dh (Third 2 bytes); Last some tips: if you use algos for convert from Dec to Hex be careful; your algo should convert 1 : 0d to 00h (not to 0h); 2 : 5d to 05h (not to 5h); GoodLuck!!! ;-) Edited by author 17.05.2009 08:41 Hi, To those who are reading the input character by character, test 4 contains some Non Digit characters as well like new line or space at the end of input etc. In my program, I just put a condition to ignore those and then it worked fine. Varun Thank you VERY much! :-) Edited by author 10.02.2010 23:16 Maybe you can show me your code? And weren't you training for the National Day last night? strange.. Edited by author 06.09.2009 17:24 me too! i have found it! check if your code is longint or int64 Edited by author 10.02.2010 19:05 I found this test on acmp.ru 21 1 16 11 5 18 21 My AC answer was 3 but real is 1 (21+21+5=47 && 18+16+11+1=46 => 47-46=1) Really, my AC give 2 =( Edited by author 08.01.2010 02:33 3 3 4 1 2 3 3 1 2 3 4 1 3 My friend,I got AC. Maybe you should find connected components at first i run it and i see there's no differernce between mine and the accepted one in result. #include <cstdlib> #include <iostream> #include <cmath> #include <iomanip> using namespace std; int main(int argc, char *argv[]) { int a=0; double b[1000];
do{ cin>>b[a]; b[a]=sqrt(b[a]); a++;} while (!cin.eof());
a=a-2;
while (a>=0) { cout<<setiosflags(ios::fixed)<<setprecision(4); cout<<b[a]<<endl; a--; }
system("PAUSE"); return EXIT_SUCCESS; } http://acm.timus.ru/help.aspx?topic=faq&locale=enHow to read and write data? Programs should read and write data using standard input and output, i.e. should read from the keyboard and write to the screen. Programs must not work with files, it may cause “Restricted function” verdict. You should not add statements like Readln or !!!pause()!!! to the end of your programs. Such things may cause “Time limit exceeded” verdict. program z; var n,k:byte; f:longint; s:string[30]; procedure factorial1(n,k:byte); var q:integer; begin q:=n; while q>=k do begin f:=f*q; q:=q-k; end; end; procedure factorial2(n,k:byte); var q:integer; begin q:=n; while q>=(n mod k) do begin f:=f*q; q:=q-k; end; end; begin read (n,s); k:=length(s); f:=1; IF n mod k=0 then factorial1(n,k) else factorial2(n,k); writeln (f); end. program z; var n,k:byte; f:longint; s:string[30]; procedure factorial1(n,k:byte); var q:integer; begin q:=n; while q>=k do begin f:=f*q; q:=q-k; end; end; procedure factorial2(n,k:byte); var q:integer; begin q:=n; while q>=(n mod k) do begin f:=f*q; q:=q-k; end; end; begin read (n,s); k:=length(s); f:=1; IF n mod k=0 then factorial1(n,k) else factorial2(n,k); writeln (f); end. My best execution time is 0.015s, how can I improve the performance? Thanks a lot! What is the answer to 3 1 2 3 According to the question, the answer should be 1 3 isn't it? But why the correct answer is 2 1 2 What is exactly the sentence below mean? "Your task is to choose a few of given numbers (1 ≤ few ≤ N) so that the sum of chosen numbers is multiple for N" Is it already correct that the answer to the above question is {1, 2} where as the minimum set which its sum divisible by 3 is {3}. (I'm not English native) Edited by author 07.02.2010 23:20 you should print any set of numbers/ so, both answers are possible. even 3 1 2 3 V zadache Pahom i ovrag u mena WA 2 test. Wse moi testi prohodat. Pomogite razobratsa! To solve this problem we must use 64-bit variable. When i wrote in my code "printf("%lld\n",res)" i've got WA on test number 7. But when i wrote "cout<<res<<endl",i've got AC. My friend had the same problem. So what does it mean? Sorry, i must be more careful and write "printf("%I64d\n",res)". I have TLE on test 7. Why it can be? Me too~~~~~~ Requests with equal times should be processed as they appear in input !!! TLE 7 is probably like this 1+ 1+ 1+ 1+ 1+ 1+ ... ... ... ... Edited by author 15.08.2008 02:14 Thanks for your hint (about requests with equal times), i've got AC now :) |
|
|