5 3 1 2 2 2 2 2 3 4 6 ans: 11 5 3 3 1 2 3 4 5 1 4 7 ans: 12 9 9 123 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ans: 9 Why does the last test have an answer 9? on 9th second he can't pick up the last stone, instead he drops all of them, so isn't the answer 27? > They fall until the total weight of the fallen stones exceeds k kilograms So weight of fallen rocks should be at least k + 1 1 4 1 1 1 2 3 4 Ans 5 6 5 50 1 4 6 6 2 5 2 5 10 14 15 Ans 21 6 5 4 1 4 6 6 2 5 2 5 10 14 15 Ans 13 9 5 4 2 4 2 5 3 1 7 2 3 5 6 9 10 14 Ans 22 I've passed all of the user tests on here, and any test I can think of. Still getting WA on #14. Here's my non-working code. import java.io.*; public class P1998 { static StreamTokenizer in; static PrintWriter out;
static int nextInt() throws IOException{ do{ in.nextToken(); }while(in.ttype != StreamTokenizer.TT_NUMBER); return (int)in.nval; }
public static void main(String[] args) throws IOException{ in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); out = new PrintWriter(System.out);
int n = nextInt(); int m = nextInt(); int k = nextInt();
int[] stones = new int[n]; int[] dropsTo = new int[n];
int tmp = 0, j = 0; for(int i = 0; i < n; i++){ stones[i] = nextInt();
while(j < i - 1 && tmp - stones[j] > k){ tmp -= stones[j]; j++; } tmp += stones[i]; dropsTo[i] = j; }
j = 0; int moment, time = 0; for(int i = 0; i < m; i++){ moment = nextInt() - time; time += moment; j += moment - 1; if(j >= n){ time -= moment - n; j = n; break; } j = dropsTo[j]; }
out.println(time + n - j); out.flush(); } } Please! Give me some tests. Me too!Have you solved this problem? I have this WA too. Firstly, I used binary search to find the last element, which didn't fall. And my mistake was: if (currentSum == k) return med; the corrent ones: if (currentSum == k) return med-1; And for case, where we haven't found exactly k sum: .. }//end of binary search int answerIndex = l; int sum = getSum(left, lastAdded Index); if (sum <= k){ answerIndex = l - 1; } return answerIndex; But now I have TL11 try this test: 10 1 10 100 9 1 1 1 1 1 1 1 1 10 right answer: 19 Edited by author 10.11.2013 14:51 Edited by author 10.11.2013 14:51 Edited by author 10.11.2013 14:51 You can try this .... 5 1 4 1 2 2 6 6 5 right ans : 7 As usual cannot find a mistake in my code. Program prints right answers on all user's tests in this discussion, however WA5 is still here. UPD: oh, just should give test like '1 1 1 1 0' Edited by author 16.03.2016 16:17 Add some tests... Try this test. 5 3 6 1 2 3 4 5 4 5 6 answer : 11 Why 11 but not 12?, please explain, i don't understand that On first 3 seconds, we pick 1, 2, 3. On 4th second, we drop 1, 2, 3. On 5th and 6th second, we drop nothing. On 7th, 8th, 9th, 10th, 11th second, we pick 1, 2, 3, 4, 5. So the answer is 11. why wa #5 I fixed my WA#5 after investigating with this test: Input: 3 2 1 2 2 2 2 6 Output: 5 Input: 3 2 1 2 2 2 2 3 Output: 6 Edited by author 14.02.2014 01:31 Edited by author 14.02.2014 01:31 If you have WA3 try this: 1 3 5 1 4 5 7 Right answer is 1 If you have WA6 try to change sum<k to sum<=k. It helped me. Edited by author 28.01.2014 20:34 #include <stdio.h> #include <vector> #define pb push_back #define For(i,n) for(int i=0;i<n;i++) using namespace std; int main() { int n,m,k; vector < int > w; vector < int > v; scanf("%d%d%d",&n, &m, &k); For(i,n) { int x; scanf("%d", &x); w.pb(x); } For(i,m) { int x; scanf("%d", &x); x--; v.pb(x); } int ind=0; int tek=0; int ans=0; long long i=0; vector < int > solve; while (true) { if (ind<v.size() && i==v[ind]) { int kol=0; while (kol<=k && solve.size()>0) { w.pb(solve[solve.size()-1]); solve.pop_back(); kol+=w[w.size()-1]; } ind++; i++; continue; } solve.pb(w[0]); w.erase(w.begin()); i++; if (w.size()==0 || solve.size()==n)break; } printf("%d", i); } I have WA 11. My solution very similar to yours. I don't have any idea what is wrong. BTW. If you use long long, you must use %lld in printf instead %d. #include <stdio.h> int n,m,k; int w[10000]; int t[10000]; long long d; void swap(int i, int j) { int t; t = w[i]; w[i] = w[j]; w[j] = t; } int caving(int i) { int s = 0; int c = 0; int j; while ((s <= k) && (i > 0)) { i--; s += w[i]; c++; } /*for (j = 0; j < c/2; j++) { swap(i+j,i+c-j-1); }*/ return c; } int main() { int i,j; int cw, ct; #ifndef ONLINE_JUDGE freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout); #endif scanf("%d %d %d\n", &n, &m, &k); for (i = 0; i < n; i++) scanf("%d", &w[i]); for (i = 0; i < m; i++) scanf("%d", &t[i]); cw = 0; ct = 0; d = 0; do { d++; if ((ct < m) && (t[ct] == d)) { ct++; cw -= caving(cw); } else cw++; } while (cw < n); printf("%lld\n", d); return 0; } Hello, Kot! > int w[10000]; > int t[10000]; >> 1 ≤ n, m ≤ 10^5 I think yon need [100000] arrays. I had a step-by-step solution which caused TL 11. I've improved it to event-by-event solution but nothing changed. I translated it from Java to Visual C 2010 using your data loader and got WA11. Replaced w[10^4] by w[10^5] - and finally I've got TL11. I don't have any good idea and wonder about better algorithm or a bug which causes an endless loop... Could you try to fix it and write your solution result? Brute force solution works fine after some optimizations. Look at n and m limits - it is possible that Luke will drop same stones more than once. Finally my solution has been accepted. It's definitely a brute force one, but using optimization for all loops, which can be run undefined number of times. did you use binary search in your solution? |
|