My solution is O(n) and I can prove it.
All tests from forum were successfully passed.
Solution's body is 31 strings (without var declaratoins, etc.) and I am looking for mistakes more than an hour. So I suppose, there is no bug..(

But I have WA5.
Mabe some incorrect input ? Or some thing I didn't notice ?
If u have got any idea or maybe test, please, help..

Edited by author 14.08.2009 05:39

Gimme some data, please

#include<stdio.h>
#include<math.h>
double str[300000];
using namespace std;
int main()
{
    double a;
    int w=0;
    while(~scanf("%lf",&str[w]))
        w++;
    for(int i=w-1;i>=0;i--)
        printf("%.6f\n",sqrt(str[i]));
    return 0;
}
//Don't use cin or cout
//str[N],Nshould>=262144

Why this answer for test 1 gets WA

2 3
1 2
3 4 5

?????????

algorithm is just
print on
1 ... n
then n+1 ... n+m

what's wroung with this???????????????

Что пивело Гоголя к смерти?



Edited by author 11.04.2016 08:03

что привело Гоголя к смерти?

Edited by author 11.04.2016 08:03

Use dynamic programming

Задача простая. Но вопрос таков:
Из правил сайта я понял, что входные данные вводятся только и только через консоль, не считываются с файла.
Если это так, то как определить что входные данные уже вбиты??
Из задания понятно, что вводятся целые числа не больше 10 в степени 18, до каких пор будут вводится входные данные? есть какой нибудь стоп кондишн?

#include <iostream>
using namespace std;

int main()
{
   long i, n;
cin >> n;

if ((n >= 1) && (n <= 10000))
cout << "sum=" << n *(n + 1) / 2;

else if ((n <= 1) && (n >= (-10000)))
cout << "sum=" << (-((-n) *(1 -n) / 2) + 1);

cout << endl;
return 0;
}

My code is giving correct output but only till one decimal place when the percentage is in whole number (50.0% instead of 50.00%). I'm using DecimalFormat. Below is my code:-

    import java.util.*;
    import java.lang.*;
    import java.text.DecimalFormat;
    public class Main
    {
        public static void main (String[] args) throws java.lang.Exception
        {
            Scanner sc = new Scanner(System.in);
                int n = sc.nextInt(); //candidates
            int m = sc.nextInt(); //electors
            double div = 0.0; double per = 0.0;
            int t = m;
            int v[] = new int[n];
            while (m != 0)
            {
                int cv = sc.nextInt();
                cv = cv - 1;
                v[cv] = v[cv] + 1;
                m--;
             }
            for (int i = 0; i <=n-1; i++)
            {
                int a = v[i];
                div = t/a;
                per = (1/div * 100.0);
                per = Double.parseDouble(new DecimalFormat("##.##").format(per));
                System.out.println(per + "%");
            }
        }
    }

O/P  (For sample Input)
50.0%
33.33%
16.67%

#include <iostream>
#include <math.h>
using namespace std;
long long i, n, d;
double a;
int p;
int main(){
    cin >> n;
    n *= 2;
    p =(int) sqrt(n + 0.0);
    while(1){
        a = (n - p * p + p + 0.0) / (2 * p);
        if(0 < a && a == (int) a && (p * p + 2 * a * p - p) == n)
            break;
        p --;
    }
    cout << (int)a << ' ' << p;
}

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct f{
    int a, b;
}b[64006];
bool shart(f a, f b){
    return a.b > b.b;
}
int x, y, q, n, mx;
int main()
{
    cin >> n;
    q = 1;
    for (int i = 0; i < n; i ++){
        cin >> x >> y;
        if(b[x + y].a){
           b[x + y].a ++;
        }
        else{
           b[x + y].a ++;
           b[x + y].b = q;
           q ++;
        }

    }
    sort(b, b + 2 * 32002, shart);
    for (int i = q - 2; i >= 0; i --)
            cout << b[i].a << endl;
    for (int i = q; i <= n; i ++)
        cout << 0 << endl;
}

i have a test:
5 2
1 2 1
1 4 20
1 5 20
2 3 10
i think answer is 21 but my AC code answer is 40
maybe i wrong???

For this test:
2
1492
1492
4
1492
65536
1492
100
Answer is 2 or 4?

You should use a SQRT-decomposition. Let BLOCK = sqrt(N) In kth element of the decomposition you should store hash_set containing numbers from k * BLOCK to (k + 1) * BLOCK.

Hello. I have a question, but it is not really about this problem. Generally asking, if you would be grateful to tell me how can I solve this type of dynamic programming problems, could you tell me how can i find the reccurrence easier? Till now I've made backtrackings on small numbers and I tried to search for a reccurrence between the elements, but I find it out pretty hard. Thank you!

var b,a:array[0..100010]of longint;
 x,i,n:longint;
begin
 readln(n);
 for i:=1 to n do begin readln(x); inc(a[x]); end;
 x:=0;
 for i:=0 to 5000 do while(a[i]>0)do begin inc(x); dec(a[i]); b[x]:=i; end;
 readln; readln(n);
 for i:=1 to n do begin read(x); writeln(b[x]); end;
end.

Edited by author 20.01.2010 18:28

This problem can be solved without realisation of sorting. :)

Lol 1.5 года назад когда зарегился только задачи такими трудными казались а счас) Вообще лехкотня. Удачи всем парни!