|
|
| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Why so few ACs and so low percent of ACs??? | Vedernikoff Sergey | 1583. Сыр | 2 июл 2019 15:05 | 15 | Very easy problem, not harder than Pineapple... Why so few people solved it??? Binary search can apply not more 120 people! What does it mean - not more than 120 people??? Pineapple was solved by about 300 authors! This is my prognoze (bookmaker).
To solve this problem we must know two things:
1) 3d geometry and volumes;
2) binary search after 1 is implemented.
So we divide 300 by 2 and have ~120-150.
P.S. The problem has also very difficult component:
3) precision question
and this is why so many people can't it solve and I am too.
AC!!!!
What does phrase W equals exactly 500 mean?
|W-500|<eps and eps=10^-16?
answer: if (W(x1)<=500)and (W(x2)>=500)) and
|x1-x2|<0.5*0.000001 then ans:=round((x1+x2)/2).
P.S.2: Tricky moments:
1)next cut must be measured
from previous rounded integer value;
2) |x1-x2|<0.00000001 ! 0.0000001 is too small
Edited by author 28.10.2007 11:25 Binnary search must be applied in integers.
Also there is one trick in the statement:
"...at which a cut should be made so that the weight of the NEXT piece be exactly 500 grams."
So we must add not just 500gramms each time, but the mass of cutted part (some more or less then 500) add 500 and search.
This was a reason of my WAs. I've done binsearch with reals and easily got AC. What concerns 500-gramm pieces - of course, we should measure mass from previous REAL cut, but not virtual and exactly-calculated - it is quite clear from the statement and ordinal logic...
Edited by author 28.10.2007 15:38 Logic for integer rounded previous bound!
This is realy made bound and exists but REAL cut is
virtual! Question
It is said that the machine which cuttes uses micrometer scale. So it can cut piece only in places with coordinates which are integer micrometers value. But after that it is said that a coordiante of current cut is ROUNDED to micrometers. What does that mean? The places where we can cut have integer micrometers value coordinats or the answers are integer micrometers value but we can cut at any position? Yes, places where we can cut have integer coordinates. So, mass may not equal to 500 grams, and you should choose such integer place for a cut to make it as close to 500 grams as possible. Sergey, you are wrong if you understand statematn at first time as autors it is not mean that statement is absolutely
right and is not ambigious But I've read russian version of the problem and didn't find any ambiguity in it! It is almost equal to the english version of the statement. Where is ambiguity? Ambiguity is absent but absent also care about
solvers, many mathematical and computing unimportant troubles precence. Next very easy but strangely seldom solved-1566: post office envelops.
I solved it during 1 hour as problem 2 level of second
division of TopCoders. Only two different
geometric situations, float considaration without
integer arithmetic and only 27 AC. | | WHY WA8 | Innokentiy | 1583. Сыр | 20 авг 2016 19:31 | 2 | WHY WA8 Innokentiy 8 июл 2016 15:50 Can you give me a hint about 8 test "If it turns out that the last cut should be made at the coordinate of exactly 1 meter, then, of course, this cut is not made." | | Some test | Lomir | 1583. Сыр | 23 апр 2016 19:08 | 2 | Can somebody give me some test with corect correct output, cause it is rather hard to calculate answer on paper.
AC now, however good test will be good for other solvers.
Edited by author 28.10.2007 01:48
Edited by author 23.04.2016 19:08 | | If you have WA2 | Victor Barinov (TNU) | 1583. Сыр | 18 янв 2012 21:56 | 3 | I got WA2, when used usual rounding.
And when i rounded all my cuts to the smallest grater than one than get AC. I used usual rounding.
But after each cut next 500g I measure not from ideal cut line, but from real cut line, taking into account accuracy of cutting machine. tricky:
needVolume = 500.0;
while (needVolume < <total volume> )
{
<find y>
iy = round(y)
recalc volume, from 0.. to iy position.(v).
needVolume = v + 500.0
} | | I tried several methods, real b-search and interger b-search, but still WA2 | liuctic | 1583. Сыр | 6 дек 2007 12:26 | 1 | and still another question:
if the exact place of last cut is 999999.8, and it is rounded to 1000000, should I output it or not?
Edited by author 06.12.2007 12:28 | | WA2 | Tipikin Evgeniy (USU) | 1583. Сыр | 31 окт 2007 14:22 | 3 | WA2 Tipikin Evgeniy (USU) 30 окт 2007 22:31 Re: WA2 Vedernikoff Sergey 31 окт 2007 03:03 Generally incorrect solution, nothing special. All such solutions cannot pass test #2... I got WA 2 when submitted integer-bsearch solution.
if you've got a same problem try real-bsearch | | could anyone give some test data? | Arthur | 1583. Сыр | 28 окт 2007 17:07 | 3 |
Edited by author 30.10.2007 21:16 |
|
|
|
