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

Russian statements fixed. Thanks.

This code is not very efficient.


Try this code instead:


#include <iostream>
using namespace std;

int main(){
    int key1;cin>>key1;
    int key2;cin>>key2;
    if((key1%2==0) || key2%2!=0){
        cout<<"yes"<<endl;
    }
    else{
        cout<<"no"<<endl;
    }

    return 0;
}

Edited by author 01.03.2024 21:16

Edited by author 01.03.2024 21:16

Please give some additional info

It means that all numbers, which are interesting to Nikolay, are also interesting to Asya, but there are some numbers, which are interested to Asya only.
For example, in first sample: 3,5,6,7 are interested to both, 4 is interested only to Asya.
And yes, surely divisors of some number include 1 and this number.

Edited by author 06.08.2016 21:02

Numbers of Haters can be placed in non-ascending order. After I started checking "1" not only at first position, I got AC

Well I tried to do so but got wa4.
I also looked at that guy's solution where he just takes the average of all p[i]. And I still cannot understand why it's right bcz, like, it's squared distance not just linear...

Edited by author 29.07.2022 12:21

I tried it, and get WA4. I suspect I have a bug but idk where.