Problem A.
The constraint that edges of each flagstone much be parralel to edges of the square allows to analyze X and Y axes separately, that is, how many segments of length 'a' are needed to cover segment of length 'm' and 'n' -- and take product of these two quantities. Answer = ceil(m/a) * ceil(n/a), where ceil(x) is the least integer which is above or equal to x. Using integers only, it is usually written as ((m+a-1)/a)*((n+a-1)/a). Note that answer may be as large as 10^18, which does not fit in 32-bit integer.
Most difficulties, if any, contestants had with data types and operator priority, which are highly dependant on language used, so they are not covered here.
Problem B.
Let each letter representation of column number be associated with integer in radix-26, where 'A' = 0, 'B' = 1 ... 'Z'=25. Then, when converting letter representation to decimal representation, we take associated integer and add one plus quantity of valid all letter representations which are shorter than letter representation being converted. When converting from decimal representation to letter representation, we have to decide how many letters do we need. Easiest way to do this is to subtract one from number, then quantity of letter representation having length 1, then 2, then 3, and so on, until next subtraction would have produced negative result. At that point, the reduced number is the one which must be written using defined association with fixed number of digits, with leading zeroes (i.e. 'A's) as needed.
Note that there is other ways to do the same which produce more compact code, but they are more error-prone as well.
Problem C.
The points can be vertices of regular N-polygon, if, and only if, for each pair, difference of their polar angles (as viewed from center of polygon) is a multiple of 2*pi/N. All points should lie on the circle with same center as the polygon. We can locate the center of polygon/circle [but we may avoid this, as a chord (like, say, (x1,y1)-(x2,y2)) is seen at twice greater angle from center, than it is seen from other point of a cricle (x3,y3)]. There are many ways to locate center of circle, the way I used is to build midpoint perpendiculares to segments (x1,y1)-(x2,y2) and (x2,y2)-(x3,y3) in form y = a*x + b and find their intersection. Formula y = a*x + b has drawback that it cannot be used if line is parallel to y, possible workaround is to rotate all points by random angle (using formulae x' = x*cos(a) - y*sin(a), y' = y*cos(a) + x*sin(a) ) until no segments are horizontal (and hence no perperdiculares are vertical).
After the coordinates of the center are known, we use fancy function atan2, which returns angle in right quadrant: a[i] = atan2(y[i]-ycenter, x[i]-xcenter)
Area of regular polygon increases with increasing N, so it is possible just to iterate through all possible values on N in ascending order, and exit from cycle as first satisfying N is found.
Using sin(x) is makes it easy: sin(x) = 0 when x is mutiple of pi. So, for points to belong to regular, N-polygon,
sin( N * (a[i]-a[j]) /2 )=0
because of finite precision arithmetic,
fabs( sin( N * (a[i]-a[j]) /2 ) ) < eps
frac{x}{y} = 3
for example.
$$$\frac{x}{y}$$$ = 4
I can't pass Test case 6.
I don't konw why? Isn't there a test case like:
Input: R001C001
Ouput: 00A001
?
A001
No leading zeros needed. "A1" is correct.
It is "RZ288".
You cannot have zeros in letter numbering. "00A" is incorrect, it should be only "A". "001" is not incorrect, but the leading zeros are unnecessary, it can be simply "1". I doubt though that there are numbers with leading zeros in the official test cases, it is simply "R1C1" or "A1".
try to check this test instead:
13
R1C17
R1C18
R1C19
R1C20
R1C21
R1C22
R1C23
R1C24
R1C25
R1C26
R1C27
R1C28
R1C29
after passing this I got AC.
My program that got AC says "R288C494".
This is correct.
B: what about "R1C204152" answer:"KOYZ169801"
That is incorrect. The correct answer is "KOYZ1". The cell is obviously in row 1.
So what?
When I use ceil((float)N/A) for problem 1A, it gives wrong answer while it gives a correct answer when I use ((N+A-1)/A). What is the catch behind it?
Use double, Luke
float has very low precision. Best stay away from it, use double.
Hello :) How do I represent 10^9 integers and input integers separated by space in a single line in C language?
For integers up to 10^9, you can use the 32-bit integral type long int. But if you multiply them, you have to use a 64-bit type, like long long int, otherwise the multiplication will overflow.
As for input, the proper way to input a 32-bit integer on Codeforces is
scanf ("%ld", & integer);
and for a 64-bit integer
scanf ("%I64d", & integer);
Can someone help me in problem 1B ? 1B - Spreadsheet
except this one "R1C204152" answer:"KOYZ169801", all the test cases which users gave in comments run on my machine. Help me please
The correct answer to the test case "R1C204152" is "KOYZ1". The cell is obviously in row 1. I got AC on this problem today.
Okay I mended my one as well to get KOYZ1 but still it fails test 6. Wanna see my code ?
Yes, please.
I have been trying 1B. But getting Runtime error. Here other people also have said same but no reason mentioned. Please suggest me what's wrong.
Try this cell: R1
Problem B. My submission: here WA on test 6, but I can't trace this big test case. Can anyone help me with a one that can be traced and hacks my code? Thanks in advance.
Have you scrolled to the bottom of the submission report?
I can't solve problem A, please help me. I was using a 2D-Segment Tree to simulate the squares, but I got WA. I need help. If you help me, I'll give you a big hug.
Tip: Solve the problem first in one dimension. Look for an analytical solution of the problem, no advanced data structures are needed.
Please help: Why I'm getting a different output on different systems for Problem B sample test cases?
On my system:
On CF system:
My submission: 16392041
pow pow pow... How many bugs with it. Write your own function.
Did you get correct result .me also facing same problem.
what datatype can i use to this big number in java? numbre: 1000000000000000000
Long.
i try to multiplicate 1000000000X1000000000 and i want that the result was 10000000000000000000, but when i try do this operation in java, the answer of the multiplication give me how result this number -1486618624 whit datatype long and int and BigInteger.
You have to store 1000000000 in a long also, if you want to make operations on it which makes it become a long. You can cast it meanwhile operation too, so you can do ((long) 10000000000)*10000000000, and it will give correct result.
Long can handle numbers up to 9*10^18, for numbers bigger than that you need to use BigInteger.
I found another solution for B here is my code: 33646284
can someone help me with the concept of epsilon in finding the gcd. Why do most of the accepted answers have it as 10^-4 . when i reduce it to 10^-5 , i get incorrect answer. Can someone tell me how did we decide this value because i think that lesser the value of eps meant a more precise answer??
can anyone explain me why my code is not passing testcase 6. https://codeforces.me/contest/1/submission/58648097
it was a nice contest....it was a og.