AC with big integers

https://w3.impa.br/~goncalves/shimalslides.pdf
have fun

This is 4 layered Rubics Cube. These layers are situated behind each other (perpendicularly). You can think them as 4 Cards placed behind each other.
Also, each layer is transparent. So, color on the second, third or fourth layer can be seen through the first layer.

Top View is watching the cube from the first layer. As all the layers are transparent, so we can see the colors of each layer behind it from the first layer.

So, from the TOP VIEW you will see a complete cube combining each layer's colors.

In the description, the first picture is the 4 layers of the cube. Can you place them behind each other? What will you see if you observe them from the first layer and considering them as transparent?
If you see them like below, then bingo you get the idea!!

YRYB
RRYY
GGBB
RGBG

Here, the first Y and the last B color of the first row are coming from the 4th layer if you see. And so on for the rests.

In the given input, let say the color code is like below,
1 - Red
2 - Yellow
3 - Blue
4 - Green.

So, the input basically says that what you will see all the layers from the front of the first layer.
If you replaced the number with the color, then you will get the exact same cube that is given in the description. (We have already built it above!!)

no, great than 1!

I got AC using it

There is another interesting test case that might be a cause of WA8. Try 12, and the right answer should be 26.

Edited by author 15.03.2024 16:13

4
d
cd
bcd
abcd
1
eabcde


1 2

Could be space trimming of right side or left side a problem...

wa 10

output for "3 3 2":

1 1 2 2 8 8 6 6
1 5 5 2 8 10 10 6
3 0 5 4 9 9 10 7
3 3 4 4 21 9 7 7
12 12 14 21 21 19 18 18
12 15 14 14 19 19 20 18
11 15 15 13 17 20 20 16
11 11 13 13 17 17 16 16

The problem statement in the problem set for IMO34 is somewhat better. Definitely worth reading.

Thanks for the hint. I tried a very similar algorithm but was still getting WA on Test 3 in Java. I finally switched over to Python, and got AC

How ( -b +- sqrt( b^2 - 4ac ) )/2a transforms into -1 +- sqrt( 8p-7 ) / 2 ?

I do it like this:

the n-th '1'should be here: n(n-1)/2+1.So, we judge whether the input number(x) == (n(n-1)/2+1).

it could be transformed to 2*x-2 == n(n-1), and int(sqrt(2*x-2)) must be the number 'n' if 'n' exists!

How can i upgrade my ints to double ? Sorry for my ignorance.I'm a newbie...

thanks

vi apnar analysis deikha chudna hoia gelam, airokom chinta kamne ashe mathai

My initial approach was slightly different, but at the end, it gave the same result.

Here's the sequence ->
1 10 100 1000 10000 100000 ...

In that sequence, 1s are located at position ->
1, 2 ,4, 7, 11 , 16, 22 ...

Look at the 11th position in the sequence. There are total (1+2+3) zeros and (1 + 1 + 1 +1) ones before the 11th 1.  So the position no 11 can be written as the sum:
(1+2+3) + 4 x 1 + 1.

Take another position as example, say 16. Before the 16th position, there are total (1+2+3+4) zeros, and (1+1+1+1+1) ones. And so 16 can be written as,
(1+ 2+3+4) + 5 x 1 + 1.

Now if you generalize this observation and formulate it, you'll get :
n(n+1)/2 + (n+1) x 1 + 1 = (position no containing 1)

After simplification, the equation stands:
n^2 + 3n + (4 - 2 x Position No) = 0

So for any INTEGER value of n, you'll get a Position No for 1 .

Now think the opposite of this . If the Position No contains 1, then n will must have an Integer value. Otherwise, the Position No will contains 0.
Solving that equation, you'll get:

n = ( -3 +- sqrt( 9 - 4 x 1 x (4 - 2 x Position No))  ) / 2

For n to be an Integer, the determinant (9 - 4x(4 - 2 x Position No))  or (8 x Position No - 7) must be a square number.

Thanks a ton <3

This an O(log n), because the sqrt function is O(log n)

[code deleted]

this right?

Edited by moderator 22.02.2006 00:38

var a,b,n,k1,k2:longint;
begin
 readln(a,b,n);
  while n>=a  do
   begin
    n:=n-a;
    k1:=k1+1;
   end;
  while n>=b do
   begin
    n:=n-b;
    k2:=k2+1;
   end;
 writeln(k1,' ',k2);
end.
земляк помоги решить 10 задачу или проверь

It is not guaranteed that A >= B and 2 test checks this. AFAIK if you will throw error if B > A, then you will get Runtime Error on test 2.

Edited by author 06.03.2024 16:54