I've solved this problem using set (so a bst). I've thought of a method of using a segment tree. How would you come about using a heap, I'm curious? test it your self after deleting this code, please explain me why WA twoalias[animal]inbox[youknow]ru #include <stdio.h> #include <memory.h> struct elt { int c; short i; }; elt T[100001]; int main() { memset(T,0,sizeof(T)); int N; scanf("%i",&N); short i; for (i=1;i<=N;i++) { int S,C; scanf("%i %i",&S,&C); if (C>T[S].c) { T[S].c=C; T[S].i=i; } } int j,ch=0; for (j=0;j<100001;j++) if (T[j].c>0) ch++; printf("%i\n",ch); for (j=0;j<100001;j++) if (T[j].c>0) printf("%i ",T[j].i); return 0; } Edited by author 29.08.2006 20:03 I think you didn't understand the task right! On the test 6 1 10 1 12 2 14 2 23 5 17 5 18 your program gives the answer 3 2 4 6 and the right answer is 4 3 4 6 5 Edited by author 30.08.2006 00:13 but I think, right answer is 3 2 4 6 in your case 2-th (#4 (2, 23)) and 4-th (#5 (2, 17) orders is expired
if you right, then why you can't output 5 1 3 4 5 6 or 6 1 2 3 4 5 6 ? please explain me, i can't understand Write your e-mail and I'll explain this task for you!) Edited by author 29.08.2006 23:58 Edited by author 29.08.2006 23:59 twoalias[animal]inbox[youknow]ru and on Russian please. Edited by author 30.08.2006 09:16 I've sent the message to you! If you won't get it write here, please!) I have the same problem. I can't understand meaning of this problem. help me please!!! Write your mail! Edited by author 04.11.2006 17:53 gio-saghinadze@mail.ru now I have WA 9:( I used heap I've sent a message!) Can you explain it to all of us ? I think this test is very useful for understanding this task 6 1 10 1 12 2 14 2 23 5 17 5 18 Answer 4 3 4 6 5
I'm understand problem, but how using dp to solve task? I solved it without using DP!) I solved it without using DP!) How????? Post your mail i dont understand, how to write program even after advices, can you explain it to me? rpmain@tut.by Please, explain! Why the answer to this test is: 4 3 4 6 5 Come on! It's easy to understand it. For example this test 3 1 9 2 10 2 11 The answer is 2 2 3. I can explain it. The deliver time is not exactly one day. So the second container (in my example) could be given in the first day and in the second day. So if the deliver time is N, it means that container could be given in 1, 2 ,..., N day (in any day, but not in the Nth day exactly). Hope it's clear to understand. Thanks Edited by author 12.09.2007 15:22 That's a question to authors why they wrote it that way :) Delivery time usually means something strict - not earlier, not later. What they meant is time due or a deadline. 6 1 10 1 12 2 14 2 23 5 17 5 18 --------------------- result: 3 4 5 6, Is right answer? Why 3 4 6 5 ? The delivery time of 3 4 6 = 2 + 2 + 5 = 9 so the delivery time of 5 is expired ! It's right ? Why 3 4 6 5 ? The delivery time of 3 4 6 = 2 + 2 + 5 = 9 so the delivery time of 5 is expired ! It's right ? NO! 2, 2, 5 isn't a delivery time to client it max time to delivery so if you want deliver goods to client with time 2 you must go to him in first day or in second day and delvery take 1 day! 4 3 4 5 6 is this wrong answer?? 1. sort these orders for the following for loop; 2. can I serve current order? is there a not used day left for it? wow, that's easy if I can use std::set::upper_bound; 3. output our selected orders with delivery time. // wow accepted, so lucky I am. // after checked the discussion, found that this problem can be easily solve with priority queue, looks that priority queue is more convenient. By my mind, my solution is right. It builds a shedule of transporting with maximal money values superseding least values before that time. But my solution falls on ninth test. I think that something wrong with that test. There are greedy simple solution. Just sort works into descending order of profits and process them sequentally. Oh! Thank you! I've got AC. My time is 0.001. And then what in case of test? 1 3 2 9 4 1 4 1 2 2 5 2 2 Answer: 2 1 3 More likely a test like: 4 2 2 2 3 3 4 3 5 will yield WA9. 9 1 100 1 50 1 150 2 10 2 20 2 10 3 5 3 7 3 5 ---------- 3 3 5 8 Try test 3 1 10 2 20 2 30 Edited by author 20.03.2007 21:45 Don't it mean he only deliver one whisky on one day? I don't know the test while the others programmer offer... Who can tell me what the problem mean? example : 3 1 10 (order: 1) 2 15 (order: 2) 2 17 (order: 3) the answer: 2 2 3 ``````` The result don`t have (order: 1), because the last arrive day is 2, mean the man deliver twice, one day one once, the subject mean it find out max profit in no more than the last day 4 1 17 5 20 2 10 2 11 answer: 3 1 4 2 Do you understand ? Edited by author 30.12.2008 17:17 Can I answer in the first test "3 2"? Nope) "1 4 2" answer gives a 17+11+15=43$ reward. And there is no other sequence of delivery that will give us $43 reward. "If there are several solutions, output any of them." No. I solved in in O(nlogn) Can you explain me your algo? thanks in advance. I think you have to use binary tree to implement something. Binary tree? Are you kidding? just quick sorting of array and little thinking. Edited by author 14.04.2013 23:05 The order is important for this test e.g on 1 test I answer 4 1 17 5 15 2 10 2 11 ------------ 3 4 2 1 It was good i don't have WA but on test 5 i have WA when i do something with my answers and they look like in example it passed WA5 and for this test answer must be: 4 1 4 1 2 2 5 2 2 --------- 2 1 3 6 1 10 1 12 2 14 2 23 5 17 5 18 ---------------------- 4 4 3 6 5 <-- so its strange :) happy debuging I have those answers and i have AC Edited by author 18.03.2011 02:56 import java.util.Arrays; import java.util.Scanner; public class Timus1403 { /** * @param args */ public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); Order[] order = new Order[n]; int[] num = new int[100001]; int[] ans = new int[100001]; boolean[] used = new boolean[100001]; Arrays.fill(used, false); for (int i = 0; i < order.length; i++) { int d = input.nextInt(); int p = input.nextInt(); order[i] = new Order(i + 1, d, p); } for (int i = 0; i < num.length; i++) { num[i] = i; } Arrays.sort(order); int count = 0; for (int i = 0; i < order.length; i++) { int j = order[i].deadline; if(num[j] > 0 && !used[num[j]]){ count++; int x = num[j]; ans[num[j]] = order[i].index; used[num[j]] = true; num[num[j]] = num[j] - 1; if(x == j){ continue; } num[order[i].deadline]--;
} } System.out.println(count); for (int i = 0; i < used.length; i++) { if(used[i]){ System.out.print(ans[i] + " "); } }
} } class Order implements Comparable<Order>{ public int index; public int deadline; public int price;
public Order(int i, int d, int p){ index = i; deadline = d; price = p; }
@Override public String toString(){ String ret = ""; ret+= this.index + " " + this.deadline + " " + this.price; return ret; }
public int compareTo(Order other) { return -(this.price - other.price); }
} Edited by author 24.10.2010 08:20 Give me some hints please you can use dynamic programming Please, tell me how to dp? I just use a heap. Edited by author 18.08.2006 19:22 Sort by finish time. For every delivery do: if current delivery time is greater than the number of already scheduled deliveries, schedule it; else (that is, it is equal), replace the least important scheduled delivery with this one. Altogether O(n log(n)). Edited by author 10.03.2010 18:40 Edited by author 10.03.2010 18:40 import java.io.*; class Courier{ static PrintWriter p=new PrintWriter(System.out); static int f; static final int k=-'0'; int mat[][],dp[],max; short N,a[],l[],sa,sl; boolean ok;
static int nextInt() throws IOException{ int t=0; for (f=System.in.read(); f<'0' || f>'9'; f=System.in.read()); for (;f>='0' && f<='9'; t*=10,t+=f+k,f=System.in.read()); return t; }
Courier() throws IOException{ N=(short)nextInt(); mat=new int[N+1][3]; short i=1; for (;i<=N; mat[i][0]=nextInt(),mat[i][1]=nextInt(),mat[i][2]=i++); a=new short[N]; l=new short[N]; dp=new int[N+1]; qsort((short) 1,N); for (i=1;i<=N; i++){ if (mat[i][0]>=1){ a[sa++]=(short) mat[i][2]; nadji(2,i,mat[i][1]); sa--; } } for (p.println(sl),i=0; i<sl; p.print(l[i++]),p.print(' ')); p.flush(); }
void nadji(int k,short p, int s){ if (k==N+1){ if (s>max) for (sl=0,max=s; sl<sa; l[sl]=a[sl++]); ok=N==sl; return; } if (s<dp[k]) return; dp[k]=s; short i=(short) (p+1); for (;i<=N; i++){ if (mat[i][0]>=k){ a[sa++]=(short) mat[i][2]; nadji(k+1,i,s+mat[i][1]); sa--; if (ok) return; } } if (s>max) for (max=s,sl=0; sl<sa; l[sl]=a[sl++]); }
void qsort(short a, short b){ short i=a,j=b,m=(short) ((i+j)>>1); int[] t; for (;i<j;){ for (;mat[i][0]<mat[m][0] || (mat[i][0]==mat[m][0] && mat[i][1]<mat[m][1]); i++); for (;mat[m][0]<mat[j][0] || (mat[m][0]==mat[j][0] && mat[m][1]<mat[j][1]); j--); if (i<=j){ if (i<j){ t=mat[i]; mat[i]=mat[j]; mat[j]=t; } i++; j--; } } if (i<b) qsort(i,b); if (a<j) qsort(a,j); }
} public class Timus1403 { public static void main(String[] args) throws IOException{ new Courier(); } } Edited by author 07.08.2009 23:27 I have got wrong answer on first test!! my program out right test on my computer! The subject test data is too strange I input: 6 1 10 1 12 2 14 2 23 5 17 5 18 output: 4 3 4 6 5 test is wa#15 I change algorithm , input again output 4 3 4 5 6 test is wa #9 but I think both the result are all right, why? Edited by author 23.12.2008 05:33 Huh! Silly mistake! Be careful while counting numbers of deliveries! Try such test: 5 1 5 3 14 6 4 8 1 9 7 While having WA5 I had answer: 5 0 0 0 0 2 and after: 5 1 2 3 4 5. Edited by author 09.11.2007 02:33 Wrong answer on test #1 I tested my programm many times. I know, it works. Tell me please, why wrong answer? Maybe, it is input/output problem? На 9ом тесте срок доставки больше, чем 100,000 What this is mean: 1584620 14:05:12 20 мар 2007 Pascal Accepted 0.001 176 КБ 1584617 14:02:35 20 мар 2007 1403 Time limit exceeded 11 0.015 156 КБ 1584609 14:00:01 20 мар 2007 1403 Time limit exceeded 2 0.001 156 КБ 1584603 13:56:00 20 мар 2007 1403 Time limit exceeded 20 0.001 176 КБ 1584602 13:55:09 20 мар 2007 1403 Time limit exceeded 3 0.001 156 КБ Why 0.001 and TLE? If you still have Fail(compiler) or TLE with small time, write here about it. Could U give me Test2 please? I can't find the errors of my program. Could U give me Test2 please? I can't find the errors of my program. |
|