ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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);
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;
int t;
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;
> int t;
>> 1 ≤ n, m ≤ 10^5
I think yon need  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?