OK, if someone came here for spoiler, T0 != 0 in test 4 Can this task be solved using only sorting? Does the solution always exist? Denote by L the total length covered by all the intervals. First delete all those intervals that is completely contained by any other. Then sort the remaining intervals. Now put those that have odd positions into the 1st group, and those with even positions into the 2nd group. Calculate the total lengths covered by each group, and let's call them s1 and s2. If s1>=L*2/3, then the intervals in the 1st group make a solution. If s2>=L*2/3, then the intervals in the 2nd group make a solution. Otherwise, the solution should contain the intervals in both groups, which is easy to prove. Good Luck! What's the so called 'odd positions' or 'even positions' please? Now you've deleted some of the intervals. Sort the rest according to either the left end or the right end. 'Odd intervals' mean those at positions 1,3,5,7,etc in the sorted sequence, and 'even intervals' mean those at positions 2,4,6,8,etc. What for this test: 0 109 10 0 100 1 101 2 102 3 103 4 104 5 105 6 106 7 107 8 108 9 109? Your method gives the 1st group (1, 3, 5, 7, 9) and the 2nd groop (2, 4, 6, 8, 10). The 1st does not make a solution, like the second group or join of the 1st and the 2nd. This method really works? Sorry for my English. The idea is almost correct. Just remove segments which are covered by SOME SUBSET of other segments. I.e. find any chain which covers entire range [T0;T1], but segments i and i+2 do not overlap. Kit 22 апреля 2005 12:48 test: 0 109 10 0 100 1 101 2 102 3 103 4 104 5 105 6 106 7 107 8 108 9 109 The right answer 0? sorry, I bad read statement right answer 1 1 What if segments i and i+1 haven't crossing? Smth like that: ---- ----- By your idea, we should divide these sectors into different groups, but it's more effectively to join 'em. I got wa5. I cant find my bug. please help to find my bug or give me the test my prog fail import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.ArrayList; import java.util.Collections; import java.util.Locale; public class Timus1105 {
private static StreamTokenizer st; private static double l; private static int n; private static ArrayList<Interval> list; public static void main(String[] args) { Locale.setDefault(Locale.US); st = new StreamTokenizer(new InputStreamReader(System.in)); l = - nextDouble() + nextDouble(); n = nextInt(); list = new ArrayList<Interval>();
for (int i = 0; i < n; i++) { list.add(new Interval(nextDouble() , nextDouble(), i + 1));
} Collections.sort(list); for (int i = 1; i < list.size() ; ) { if(list.get(i).r <= list.get(i - 1).r){ list.remove(i); } else{ if(i < list.size() - 1 && list.get(i).r < list.get(i + 1).r && list.get(i + 1).l <= list.get(i - 1).r){ list.remove(i); } else i++; } } double sum1 = 0; double sum2 = 0; for (int i = 0; i < list.size(); i++) { if(i % 2 == 0){ sum1 += list.get(i).r - list.get(i).l; } else{ sum2 += list.get(i).r - list.get(i).l; } }
for (int i = 0; i < list.size() - 1; i++) { double r = Math.min(list.get(i).r, list.get(i + 1).l); double l = Math.max(list.get(i + 1).l, list.get(i).r); list.get(i).r = r; list.get(i + 1).l = l; }
double sum = 0; ArrayList<Integer> ans = new ArrayList<Integer>(); for (int i = 0; i < list.size(); i++) { double x = list.get(i).r - list.get(i).l; if(x > 0){ sum += x; ans.add(list.get(i).i); } }
if(sum1 > sum ){ sum = sum1; ans.clear(); for (int i = 0; i < list.size(); i+=2) { ans.add(list.get(i).i); } } if(sum1 > sum){ sum = sum2; ans.clear(); for (int i = 1; i < list.size(); i+=2) { ans.add(list.get(i).i); } } if(3 * sum >= 2 * l){ System.out.println(ans.size()); for (int i = 0; i < ans.size(); i++) { System.out.println(ans.get(i)); } } else{ System.out.println(list.size()); for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); } } }
static double nextDouble(){ try { st.nextToken(); } catch (IOException e) { e.printStackTrace(); } return st.nval; }
static int nextInt(){ try { st.nextToken(); } catch (IOException e) { e.printStackTrace(); } return (int) st.nval; }
static class Interval implements Comparable<Interval>{ double l, r; int i;
Interval(double l1, double r1, int i1){ l = l1; r = r1; i = i1; } @Override public int compareTo(Interval o) { int ret = (int) (this.l - o.l); if(ret == 0){ ret = (int) (o.r - this.r); } return ret; }
} } program ural; var f,e,p,q:real; i,n,s,l,d,t:integer; a,b:array[1..10000]of real; u,k:array[1..10000]of integer; o:array[0..1]of real; procedure heap; begin p:=a[s]; q:=b[s]; t:=k[s]; d:=s shl 1; if(d<l)and((a[d]<a[d+1])or((a[d]=a[d+1])and(b[d]>b[d+1])))then inc(d); while(d<=l)and((p<a[d])or((p=a[d])and(q>b[d])))do begin a[s]:=a[d]; b[s]:=b[d]; k[s]:=k[d]; s:=d; d:=s shl 1; if(d<l)and((a[d]<a[d+1])or((a[d]=a[d+1])and(b[d]>b[d+1])))then inc(d); end; a[s]:=p; b[s]:=q; k[s]:=t; end; begin assign(input,'observe.in'); assign(output,'observe.out'); reset(input); rewrite(output); readln(f,e); readln(n); for i:=1 to n do begin k[i]:=i; readln(a[i],b[i]); end; l:=n; for i:=n shr 1 downto 1 do begin s:=i; heap; end; for i:=n downto 2 do begin t:=k[i]; k[i]:=k[1]; k[1]:=t; p:=a[i]; a[i]:=a[1]; a[1]:=p; p:=b[i]; b[i]:=b[1]; b[1]:=p; s:=1; l:=i-1; heap; end; u[1]:=1; t:=1; for i:=2 to n do if b[u[t]]<b[i] then begin while(t>1)and(a[i]<=b[u[t-1]])do dec(t); inc(t); u[t]:=i; end; for i:=1 to t do o[i and 1]:=b[u[i]]-a[u[i]]; f:=(e-f)*2/3; if o[1]>=f then begin t:=(t+1) shr 1; writeln(t); for i:=0 to t-1 do writeln(k[u[i shl 1 or 1]]); end else if o[0]>=f then begin t:=t shr 1; writeln(t); for i:=1 to t do writeln(k[u[i shl 1]]); end else begin writeln(t); for i:=1 to t do writeln(k[u[i]]); end; end. I think, testset is not enough. Please, add such test: #include <cstdio> int main() { int N = 10000; double k = 1.5; printf("%lf %lf\n", 0.0, N * (k + 1)); printf("%d\n", N); for (int i = 0; i < N; i++) printf("%d %.1lf\n", i, i + 1.5 * N); return 0; } Thank you for the answer. The problem is rejudged. TL now is 0.5 sec. Here is the explanation of the output: 3 - number of observers 2 5 7 These are the observers we shall color, and now we consider only observers 2,5 and 7(because we are interested only in colored observers): 2: 0.0 - 10.0 5: 9.0 - 18.0 7: 19.0 - 20.0 So, from 0.0 to 9.0 (during 9 minutes)there was only observer 2 in the room, from 10 to 18 (during 8 minutes)- only obesver 5, and from 19 to 20 (during one minute) there was only observer 7. So, total time is 9+8+1=18, which is not less than 2/3*(20.0-0.0)=13.3333 Of course, this output is not the only possible output for this test case, for example my program's output is: 3 2 5 4 I hope this will help Good luck! > > There must be EXACTLY one observer, not at least one. Segments with no colored observers at all and segments with 2+ colored observers do not count. If the test is: 0.0 20.0 2 0.0 12.0 8.0 20.0 If I coloured both of them, what is the summary time? I'll appreciate your help. Please, tell me, what can be in it? AC) Hm... O(n^2) works)) In test 4, it's seems that T0 and T1 can be negative) I'm sure that my algorythm is correct. It's complexity is O (n log n), because I use quicksort, and then 2 linear procedures. Why do I get TimeLimitExceed? Is it possible not to use sorting? > I'm sure that my algorythm is correct. It's complexity is O > (n log n), because I use quicksort, and then 2 linear > procedures. Why do I get TimeLimitExceed? Is it possible > not to use sorting? because complexity of quicksort in worst case is O(n^2) use heapsort or mergesort and ur program 'll get accepted ( or at least not TimeLimitExceeded ) ;) Just use Random-Quick-Sort it'll take a little time to run it. you can use the quick sort in short algorithim Still AC with O(N^2). ::) But sorting i use. do as this #include <algorithm> using namespace std; int a[n]; sort(a,a+n); Could anybody give me any hints about solution. There was posted one algorithm but it is wrong - there is a counter-example for it. So, anybody who has AC, tell me please how to solve it. Sorry, i've misunderstood some things in solution. I got WA on test5. See this: 0.0 20.0 5 0.0 16.0 1.0 17.0 2.0 18.0 3.0 19.0 4.0 20.0 The output should be any ONE of the five You should try to keep the list short. That means, only observers covered all the time are needed, which are no more than 2 each moment indeed, and others should be deleted. i think i've known the algorithm. but why wa? program p1105; const maxn=10000; zero=0; var a,b:array [1..maxn] of real; code,t:array [1..maxn] of longint; n,i,top:longint; time,start,finish:real; procedure qksort(p,q:longint); var r,kcode,i,j:longint; ka,kb:real; begin r:=random(q-p+1)+p; ka:=a[r]; kb:=b[r]; kcode:=code[r]; a[r]:=a[p]; b[r]:=b[p]; code[r]:=code[p]; i:=p; j:=q; while i<j do begin while (i<j) and ((ka<a[j]-zero) or (ka<=a[j]+zero) and (kb>=b [j]-zero)) do dec(j); a[i]:=a[j]; b[i]:=b[j]; code[i]:=code[j]; while (i<j) and ((a[i]<ka-zero) or (a[i]<=ka+zero) and (b[i] >=kb-zero)) do inc(i); a[j]:=a[i]; b[j]:=b[i]; code[j]:=code[i]; end; a[i]:=ka; b[i]:=kb; code[i]:=kcode; if p<i-1 then qksort(p,i-1); if i+1<q then qksort(i+1,q); end; begin read(start,finish); read(n); for i:=1 to n do begin read(a[i],b[i]); code[i]:=i; end; if n=0 then begin writeln(0); exit; end; qksort(1,n); t[1]:=1; top:=1; for i:=2 to n do if b[i]>b[t[top]]+zero then begin inc(top); t[top]:=i; end; time:=0; for i:=1 to top do if odd(i) then time:=time+b[t[i]]-a[t[i]]; if time>=2/3*(finish-start) then begin writeln((top+1) div 2); for i:=1 to top do if odd(i) then writeln(code[t[i]]); exit; end; time:=0; for i:=1 to top do if not(odd(i)) then time:=time+b[t[i]]-a[t[i]]; if time>=2/3*(finish-start) then begin writeln(top div 2); for i:=1 to top do if not(odd(i)) then writeln(code[t[i]]); exit; end; writeln(top); for i:=1 to top do writeln(code[t[i]]); end. |
|