Welcome, friends)
We are glad to introduce you regular Codeforces round #123 for Div.2 participants. Everyone can traditionally participate in it.
Problems are prepared by command of authors: Ivan Fefer (Fefer_Ivan), Igor Kudryashov (Igor_Kudryashov), Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Also thanks to Pavel Kunyavskiy (PavelKunyavskiy) and Alexander Kouprin (Alex_KPR) for their help. And traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating problems.
Score distribution is standard: 500, 1000, 1500, 2000, 2500.
We wish you success and high rating!
Congratulations to winners:
UPD: the tutorial is here
I am students.
Good luck to all. :-)
I hate problem C.......
I hate string parsing. Problem C is just colateral damage :)
Seen at the last moment that the string can have '\t' in, and no time for correct it... Those kind of problem is not bad, because it teachs you to prevent all possible cases, but it's often very frustrating...
really frustrating... i used regular expression. i knew little about it before
I used %[\n )] in scanf to match the keyword. Forget \t should be my error :(
%*[^A-Za-z]%[A-Za-z]%*[^"]"%[^"]%*[^\n]\n
Test does not contain '\t' symbols as I know. Only ' '.
Will n log n time out in problem D? Mine nlog n timed out. Is there any o(n)?
nevermind
It was nlog n for sorting and then o(n) for counting non zero diff slopes.
Yes, they was o(n), you should find all X where line intersect OX axis, number of unique point — it's a answer)
Problem B. You should mention that if m is 6, for example, (m + 1) / 2 equals 3 or 3.5.
3.5
children in first grade are told what symbols '/' means
It's ambiguous as to programming languages.
the problem statement was in English language, not a programming one
Couldn't you ask it?
Problems are written in English language, not C++ : )
Usually, . But .
Well. I see. Thx ;)
It doesn't really matter because even if you use integer division, you still take the basket with the lower number in case of a tie.
Counterexample:
Oops. You're right. Anyway, I used integer division, so I guess that was the intended meaning. Is there any other explanation why it worked? I can't find any.
You may have interpreted it as integer division, but your code skips the issue entirely by multiplying out both sides:
abs((M + 1) - 2 * a.second)
Oh yeah, I totally forgot. At first, I wrote it abs((M + 1) / 2 — a.second) and then changed it. I had a bug, but then I realized that it was something else. It turns out that I was pretty lucky because I just tried it with the division and it fails "2 6". So we have our answer :)
In problem C I used Scanner and it not even passed the first test case..Then I used BufferedReader and it got accepted..Could anyone explain why?? Scanner BufferedReader
I could be wrong, but you should use nextLine() for entire lines.
But I changed the Delimiter to
"\n"
..So it is the same I guess..nextLine() reads characters until the end of a line, so after reading the first integer in the first line, you should put an extra nextLine(). Then a "carret" will be moved to the next line and you can read an input as expected. Otherwise the last line will be skipped. Here is the corrected solution that passes: 1781961
Can u please make it more clear for a dumb head like me.. I made a similar mistake on 1 more problem and I want to rectify it now ..plz..
Problem E,I can't understand "angle"...what is that?
It means parallel to the X axis ?
Angles are places where polyline has fracture.
But the fracture maybe discontinuous?
Oh! I get it,It must be continuous,thank you very much~~
In problem C:The program may have spaces at the beginning of a line, at the end of a line, before and after a bracket, a comma or a quote mark. But I got stuck in cin.getline(s,55,'\n'). I don't know why it reads more lines than you data gives.
The second
t.cha[len] = '\0';
should bet.msg[len] = '\0';
Oh, and maybe you should consider putting acin.getline(s,55,'\n');
instead ofgetchar()
after reading n too just to be safe.For problem A, I was looking at bmerry's solution but I don't understand why the formula he used is:
down_time = (c*a + b - 1) / b
A lot of solutions I studied use this formula or some variation. I was trying to solve the problem using some kind of simulation but was unable to, but everybody's I've looked at uses some kind of formula.
The other thing he does is subtract c from downTime, and the answer is max of 0 or that difference.
Can someone explain how to come up with this formula? Thank you.
I simulated problem A. You can take a look at my code here
brute force solution here
What I'll tell is effectively the same solution.
If b ≥ a, then we can wait 0 seconds and still there will be no delays in the streaming.
Suppose that b < a. Consider the moment when the streaming has finished. By problem statement we must have (t + c)b ≥ ca (the amount of data received in t + c seconds is not less that the amount of data in c seconds of the video).
Lemma: If (t + c)b = tb + cb ≥ ca, then also for any 0 ≤ t0 < c it holds that tb + t0b ≥ t0a (the amount of data received in t + t0 seconds is enough to play t0 seconds of the video).
Proof:
because $0 \geq t_{0} < c$ and b < a.
Consequently, we only need to find such t that tb + cb ≥ ca is true, and the rest will follow. The smallest integer t that satisfies this inequality is
Finally, for integer division that is equal to
You can also take $c$ out of the numerator, which gives you bmerry's
Will there be an editorial ?