You can prove it with the knowledge of maths.

Edited by author 22.08.2007 14:43

If i input 4, what is answer? or if i input 8, what answer?

Use the formula:

N=[a+(a+p-1)]*p/2,and you will got the formula of A:

A=[ 2*N/P +1-p]/2

Loop p to find A,that's what someone else in this forum suggested.

But even in this way some people got TLE as well.I guess you start looping P from 10^9...

In fact you can find that 2N/P +1-P >0,solve this inequality,you will find p is <[1+sqrt(1+8N)]/2.

You can cut the time of the loop down to half or even less in this way.

New tests were added. 89 authors lost AC after rejudge.

Could someone explain me why I've got Crash #9?
I was trying all tests here but I've got nothing.

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

int n, a[111111], b[111111], i, l = 0, sum, index = 1;

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    cin >> n;

    for(i=1;i<=100000;i++) {
        a[i] = a[i-1] + i;
    }

    while(true) {
        sum = a[index] - a[l] + l;
        if(sum == n) {
            int e = index - l + 1;
            if(l == 0)    l++, e--;
            cout << l << " " << e;
            return 0;
        }
        if(sum > n) {
            l++;
        }
        else {
            index++;
        }
    }

    return 0;
}

Edited by author 05.06.2011 21:10

I accept this task with O(n) solution. Then, I wrote solution with no input, but with line n=... and got TLE#1. I'll send some tests on timus_support@acm.timus.ru

1) если число k простое, то результат: k/2 2
пример:
>31
15 2
2)если число k является степенью двойки, то результат: k 1
пример:
>1024
1024 1
3)остальные числа перебором(перебирать а1-первый элемент арифметичиской прогрессии) и через квадратное уравнение находить p.
P.S. AC    0.031 137 КБ

Anybody knows what kind of test it is?


and what's the answer for 1 ? I think 0 2, but not 1 1.
is it true?

Edited by author 24.07.2009 22:22

correct answer is 1 1


Here is some tests:

->152
2 16
->1000000000
26263 25600
->3
1 2
->15963247
2673 3578
->654987
5689 114
->777
3 37
->898989
99 1246

Edited by author 24.07.2009 23:49

Hi,
I would be grateful if somebody share his/her outputs for the following inputs so I can compare the results with these of my program:

1
1 1

2
2 1

3
1 2

4
4 1

5
2 2

6
1 3

7
3 2

8
8 1

9
2 3

10
1 4

11
5 2

12
3 3

16
16 1

500
59 8

2^x
2^x 1

1000000000
26263 25600

if n=1 the answer a=0 p=2 is wrong!
The correct answer is a=1 p=1

I discovered an interesting fact:
if i use unsigned type for all vars in my program i got AC (0.015    192 KB)

and if I use int type for all my vars I got AC (0.001    192 KB)

So with int my program is 15 times faster with int variables :)

i don`t understant what means "N = A + (A + 1) + … + (A + P − 1)."?

 i think: when A=2:  14=2+(2+1)+(2+2)+(2+3)    P=?

why was p=4 in the subject?



please help me!!!

var
 k,n,m: Real;
 koren, p: Real;
 ok: Boolean;
begin
 Readln(n);
 k:=0;
 p:=0;
 repeat
 ok:=false;
 m:=n+p;
 koren := (-1+sqrt(1+8*m))/2;
 if frac(koren) < 1e-18 then
  begin
   writeln(round(k+1),' ',round(koren - k));
   ok:=true;
  end
 else
  begin
   k := k + 1;
   p:= (sqr(k) + k)/2;
  end;
 Until ok;
End.

now i've AC

Edited by author 25.03.2008 10:42

Edited by author 25.03.2008 10:42

#include<stdio.h>

long n,a,k;
void work ()
{
   long i,na,x;
   if (n<316227) x=2*n; else x=316227;
    for (i=x;i>=1;i--)
     {
       na=2*n+i-i*i;
       if (((na%(2*i))==0)&&(na>0))
     {
        na=na/(2*i);
        a=na;
        k=i;
        break;
     }
    }
}
int main ()
{
  scanf ("%ld",&n);
  work ();
  printf ("%ld %ld",a,k);
   return 0;
}

The solution for the input "7" is whether "3 2" or not