ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1998. The old Padawan

Why TL 11?
Posted by yutr777 26 Oct 2013 14:26
#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);
}
Re: Why TL 11?
Posted by kot 26 Oct 2013 15:23
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;
}
Re: Why TL 11?
Posted by Vladimir Chervanev 27 Oct 2013 21:10
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?
Re: Why TL 11?
Posted by Leonid 27 Oct 2013 22:02
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.
Re: Why TL 11?
Posted by Vladimir Chervanev 28 Oct 2013 17:31
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.
Re: Why TL 11?
Posted by Vahagn Gevorgyan 12 Nov 2013 23:21
did you use binary search in your solution?