Common BoardI tried greedy approach during the contest, but got failed. Idea was in bombing the city (even if it has been already destroyed) with the most number of remained cities in a radius. But WA#14. Please, would you share any AC idea? just bruteforce My bruteforce dies with TL :( There should be some optimizations. Edited by author 22.03.2011 12:31 Finally AC. Yes brootforce rules here. But it's a little BIT tricky brootforce. Edited by author 22.03.2011 12:39 Idea: Graph, Minimal inner stable subset, algo of Bron - Kerboach(effective brute force) oh..(my God!?) Idea: Graph, Minimal dominating set of vertices, problem of set covering, simplest brute force stack searching with table of covering reducing, easy AC By the way! To admin!. It is interesting to make competiton on one problem only(which is NP): minimal covering collection of sets. This algo is very helpfull in practice. Edited by author 25.03.2011 11:10 Could you explain the meaning of this "table of covering reducing"& I've never heard about it. My BF gives TL 10 :( By the way, isn't the problem #1739 - Faryuks based on minimal covering collection of sets algo, as you want? "table of covering reducing"- my term(auto trans. is used) Classical algo for minimal covering had good success in this problem and under emotion I wrote that helping. Again: we have NP problem but can to speed up. So, in stack data we add matrix of covering for example as 1 0 1 0 0 1 1 1 0 1 1 1 This means that 4 points(columns) are covered by 3 sets(rows). First point is covered by only 1-th row and we must use Set-1 as obligatory. Thus, the search tree hasn't branching in this-time vertex and we create only one child vertex with reduced matrix: 1 1 1 1 because 1,3 points are covered by obligated row 1. Finally: when we make choice for some set in search tree we transfer in child vertex reduced matrix. P.S. I had expirience in this algo from boolean design(all practice problem are NP). I did really stupid brute with simple speed up, like bit mask for graph and degree sorting for each connected component. AC with 0.3 seconds. to: svr could you send me your solution of this problem, please? :D my mail: night10101@yahoo.com Edited by author 30.10.2012 22:29 SVR, please, can you tell me, how can you use idea of Bron - Kerboach algorithm and inner stable subset into this problem? It's really interesting and surprising for me. How to use Bron - Kerboach for finding Minimal Dominating Set? Or how to reinterpret problem for searching inner stable subset? is file handling is necessary in this problem or not?.. for input "10000 9999 10" my prog gives "1.(0001)". But I have WA#1. help me! Edited by author 25.12.2006 11:40 And what about 1000 9999 10 ? Good luck! Correct answer is 0.1(0001),isn't it? Thank you. but I have WA#1. Please give me some test or hint Edited by author 25.12.2006 22:02 Input 9800 9999 10 0 0 output 0.98(0098) or 0.9(8009) input 4 4095 4 1 9999 10 10 9999 10 100 9999 10 1000 9999 10 10000 9999 10 9800 9999 10 3 2 8 0 0 output 0.00001(000001) 0.(0001) 0.001(0001) 0.01(0001) 0.1(0001) 1.(0001) 0.9(8009) 1.4 this output is correct,isn't it? Correct output 0.(000010) 0.(0001) 0.(0010) 0.(0100) 0.(1000) 1.(0001) 0.(9800) 1.4 I have checked all the anwers in this post all are working fine and sample input is working fine still I got WA1?? Any idea for test1... please provide some rigourous test Thank you!AC now! Edited by author 12.01.2015 23:19 Correct answer for "1000 9999 10" is 0.(1000), not 0.1(0001). In another example 0.(9800) is correct, not 0.98(0098). Edited by author 25.12.2006 23:41 why? 'The output must not contain insignificant zeros.' 0.(1000) contain 3 zeroes on the end, don't it? sorry bad English. Edited by author 25.12.2006 23:42 For the case, 2794 6083 23 2794/6083, I get 0.4593128390596745027124 (in decimal) But when I convert 0.ACM from base 23, I get 0.459275088353744 (in decimal) Where is the mistake ? 2794 6083 23 reason:The correct result:0.ACMACMACMACM...........ACM....... (loop) #include <iostream> using namespace std; int main() { int n ; cin>>n ; int f,s,l ; for(int i=0;i<n;i++) { cin>>s ; if(i==0) { l=s ; f=1 ; } else if(l!=s) { cout<<f<<" "<<l<<" " ; f=1 ; l=s ; } else f++ ; } cout<<f<<" "<<l ; } 1. If we regard the start airport as the root,it is clear that the graph is a tree. 2. If start from all the leaf airport that from one airport could win, start from this airport suerly will lose. Otherwise,he could win. 3. We use a flag to record start from one airport will win or not.Just DFS to obtain all flag. In this way,you could get AC in O(e). Is there any better way to solve this problem? I think the answer is yes. So,could you write down your thought? I didn't want to create new thread, so I will just revive this thread. My idead was to use simple minimax algorithm: boolean firstWins(node v) for every neighbour u of node v check secondWins(u) return true if for some u second loses return false boolean secondWins(node v) for every neighbour u of node v check firstWins(u) return true if for some u first loses return false Hope it will be helpful to someone. Edited by author 11.01.2015 11:04 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class Main { static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); public static void main(String... args) throws Exception { StringTokenizer tokenizer; Stack<Double> stack = new Stack<Double>(); String line; while ( (line = reader.readLine()) != null ) { tokenizer = new StringTokenizer(line); while (tokenizer.hasMoreTokens()) { stack.add(Math.sqrt(Double.parseDouble(tokenizer.nextToken()))); } } while (!stack.empty()) { System.out.println(stack.pop()); } } } Please do something with TL on java applications. My usual programs gets TL too often. For example, normal solution in 1222 using DP and BigInteger has failed because of this problem. I had to use precalculations, but it's not so clear a normal solutions. I solved it with Python and 4 SLOC in 0.14 First make the sum to determinate MIN and MAX money the teacher wanted to give. Then divide it by the price of one ticket. Do it in this order. Hope I helped! :) read(x,y); readln(e); t:=0; if ((abs (x-sin(sqrt(t)))<=e) and (abs(y-cos(t))<=e)) then begin write('0') ; exit; end; f1:=true; f2:=true; repeat t:=t+e until (abs(sin(sqrt(t))-x)<=e) and (abs(cos(t)-y)<=e) or (t>10e12) ; if t>10e12 then write ('FAIL') else write(t:0:1); Nothing special to get AC, just think a little and write about 20 strings of code. Look what happens when T becomes large. !!!!!!!!!!!!!!!!!!!!!!!!! What interval at you for T? And what step of increase? ?????????????????????????? search(+) little hint repeat t:=t+0.001; until cos(t)-y<0.00001; Where is mistake? read(x,y); readln(e); t:=0; if ((abs (x-sin(sqrt(t)))<=e) and (abs(y-cos(t))<=e)) then begin write('0') ; exit; end; repeat t:=t+e until (abs(sin(sqrt(t))-x)<=e) and (abs(cos(t)-y)<=e) or (t>10e12) ; if t>10e12 then write ('FAIL') else write(t:0:1); program ex; type z=array [1..4002] of longint; var n,n1,n2,i,t,k,s,j,l:longint; a,a1,a2,r:z; begin readln(n); for i:=1 to n do read(a[i]); readln(n1); for i:=1 to n1 do read(a1[i]); readln(n2); for i:=1 to n2 do read(a2[i]); j:=1; i:=1; k:=0; repeat if a1[j]>a[i] then i:=i+1; if a1[j]<a[i] then j:=j+1; if a1[j]=a[i] then begin k:=k+1; r[k]:=a1[j]; j:=j+1; end; until (i>=n) or (j>=n2) ; i:=1; j:=1; s:=0; repeat if r[j]>a2[i] then i:=i+1; if r[j]<a2[i] then j:=j+1; if r[j]=a2[i] then begin s:=s+1; j:=j+1; end; until (i>=n2) or (j>=k) ; write(s); end. Hi I think this Problem is very very Nice Easy to understand Hard 2 solve! i got AC with all theoric methods: [code deleted] Sincrely Aidin_n7 Edited by moderator 20.11.2019 23:24 Change Var n,k :longint; >> i,j,s :longint; m :array[0..9] of longint; And all will be correct! > Change > > Var > n,k :longint; > >> i,j,s :longint; > m :array[0..9] of longint; > > > And all will be correct! When N>100,his answer isn't right,either. DON`T POST YOUR CODE!!! >>Messages should NOT contain source code (especially correct solutions) Edited by author 08.01.2008 14:01 50% have in it forums solutions with AC :) I hate this problem!!! I've been solving it 2 days. And now I'm very tired. :( I do very easy, but have Time Limit excepted :( Aaaa, too much code ) Want a shorter solution, email me ) cebotari.vladislav@gmail.com Send my solutions in Java. And get "Runtime error (non-zero exit code)". I decide to check an already accepted solution. Sent the same solution that was accepted 4 days ago and it returned "Runtime error (non-zero exit code)". What's wrong? Any changes on server for Java in last 4 days? P.S. Even with test problem 1000 from here: http://acm.timus.ru/help.aspx?topic=java Edited by author 08.01.2015 11:52 Edited by author 08.01.2015 15:24Vladimir Yakovlev (USU) Fixed [1] 8 Jan 2015 16:32 Input: "Hello world "Next paragraph" and this works " \par last one \endinput Output: Hello world ``Next paragraph'' and this works \par last one \endinput #include <iostream> #include <vector> #include <cmath> using namespace std; int main() { double n; vector<double> v; int a = 1; while (a==1) { cin >> n; v.push_back(n); if (cin.peek() == '\n') a = 0; }
for (int i = 0; i <= v.size() - 1; i++) { //cout << sqrt(v[v.size() - 1 - i]) << endl; printf("%.4f\n", sqrt(v[v.size() - 1 - i]));
} cout << endl;
} out of type. for ex. 876652098643267843 out of double |
|