8
9.23e4
1.23e0
12.2e3
13.233e1
12.2e-3
9.2e-1
10.22e-3
123.12e-1


92300
1.23
12200
132.33
0.0122
0.92
0.01022
12.312
----------------------  +
104646.81442

Result: 1.046468144200000000e5


Remember the "." doesn't have to be
eg.

9e0
9e2
9e-2


Also you don't have to round your result! i have AC

Edited by author 19.04.2011 20:29

Edited by author 19.04.2011 20:31

So what I am doing is to note 1 instead of > and 0 instead of <. Therefore if I have the configuration 10 then it will become 01. The 01 configuration doesn't change.
Therefore if I take the example from the problem I have

110010
101001
010101
001011
000111

So I see there is a shifting of the zero's to the left and a of one's to the right.
So I am saving in the beginning the positions of zero's in an array (zero[]) and the positions of the one's in another array (one[]).
then I consider k = one[0].

Therefore the all algorithm (after reading the data) looks practically like this

k=one[0];
for (int i=0;i<z;i++){
    if ((zero[i]-k) >=0){
     result+=(zero[i]-k);
     k++;
    }
}

I think the complexity of this is even O(z) where z is the numbers of zero's.

The problem with this is that I obtain TL on test 15. Is there anything faster or is only my coding problme (java)?

Edited by author 29.11.2012 19:22

Edited by author 29.11.2012 19:37

import java.util.*;
public class Taxi {


    public static void main(String[] args) {

        int a, b, c, d;

    Scanner rc = new Scanner(System.in);
            System.out.println("Введите стартовую сумму клиента: ");
    a = rc.nextInt();
            System.out.println("Введите стартовую сумму водителя: ");
    c = rc.nextInt();
            System.out.println("Введите сумму, на которую клиент повышает: ");
    b = rc.nextInt();
            System.out.println("Введите сумму, на которую водитель понижает: ");
    d = rc.nextInt();

while (a < c){

    a+=b;
    c-=d;
}


    System.out.println("Сумма, на которой они сошлись: "+a);


}

    }


у меня всё нормально работает, а ихний компилятор бракует... что не правильно?

Edited by author 18.03.2013 15:14

Edited by author 18.03.2013 15:14

If you precalc real fibonacci numbers from 0 to 2000, double will not be enough - enough will be long double.
Keep in mind that in MSVC double and long double are equal, but in GCC they are different; so, if you select at Timus as a compiler a GCC++, everything will be AC :)

/del

Edited by author 18.03.2013 20:01

Could anyone tell me test #20?

please tell me if the max length is 109. which type i could use?

At first I converted all the things to indices. for example
if n = 5
2 4 5 2 4
and
m = 1
4 2 2    -> 1 - 2, and 4 - 5 <= these are all index.
Then I got only some pair of index. From these I calculate the 11011. THere may be index intersections.
That is my code. I think its time and algo is ok. But I got wa3



import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Timus1827 {
    public static void main(String [] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int [] a = new int[n];
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        for(int i = 0; i < n; i++){
            a[n - i - 1] = input.nextInt();
            if(map.get(a[n - i - 1]) == null){
                map.put(a[n - i - 1], new ArrayList<Integer>());
            }
            map.get(a[n - i - 1]).add(n - i - 1);
        }

        int m = input.nextInt();
        int[] h = new int[n];
        boolean[] dontuse = new boolean[n];
        Arrays.fill(dontuse, false);
        Arrays.fill(h, -1);
        for(int i = 0; i < m; i++){
            int x = input.nextInt();
            int y = input.nextInt();
            int d = input.nextInt() - 1;
            if(map.containsKey(x))
                for(int j : map.get(x)){
                    if(j + d < n && a[j + d] == y){
                        h[j] = Math.max(h[j], j + d);
                        dontuse[j] = true;

                    }
                }
        }

        int k = -1;
        for(int i = 0; i < n; i++){
            if(dontuse[i]) {
                k = i;
                break;
            }
        }


        int j = k;
        for(int i = k + 1; i < n; i++){
            if(dontuse[i]){
                if(h[j] + 1 >= i){
                    h[j] = h[i];
                    dontuse[i] = false;
                }
                else{
                    j = i;
                }
            }
        }

        int[] ans = new int[n];
        Arrays.fill(ans, 0);
        for(int i = 0; i <n; i++){
            if(dontuse[i]){
                for(j = i; j <= h[i]; j++){

                    ans[j] = 1;

                }

            }
        }
        for (int i = 0; i < n; i++)
            System.out.print(ans[i]);
    }
}

Hello all.
I have some problem with this task?
Why crash:acces violation?
Here is the code
-------------------------------------------------
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;

int main ()
{
int n,i,j;
int a[100];
cin>>n;
for( i=0;i<n*n;i++)

cin>>a[i];

sort(a,a+n*n);

for( i=0;i<n*n;i++)
cout<<a[i]<<" ";

return 0;
}


I didn't use two dimensional arrays cause I'had tried to find the laziest way. Could u help ?
Local test on computer is pretty good, u can check by trying code by yourselves;

What is test #4?

Can not find mistake, it's crashing on 1 test. Can anybody help? Thnx.


#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <memory.h>
#include <stdio.h>
#include <fstream>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;


#define sc scanf
#define fi first
#define exp 1e-10
#define se second
#define pr printf
#define exp 1e-15
#define ll long long
#define mp make_pair
#define pb push_back
#define sqr(x) (x)*(x)
#define N (int)(1e+3)*2
#define mod (int)(1e+9)+7
#define inf (int)INFINITY/4
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);

    int dp[20][20];
    bool us[20][20];
    vector <int> x, y;


int main(){
    int n, i, j, m, v, c;
    cin >> n;
    for(m = 1; m <= n; m++){
        cin >> i >> j;
        dp[i][j] = 1;
        if(v == 0)
            v = i, c = j;
    }int k = 0;
    cout << v << ' ' << c << "\n";
    x.pb(v); y.pb(c);
    while(!x.empty()){
        v = x[0], c = y[0]; k++;
        if(!us[v][c]){
            if(!us[v + 1][c] && dp[v + 1][c] == 1)
                dp[v + 1][c]++, cout << "R", x.pb(v + 1), y.pb(c);
            if(!us[v][c + 1] && dp[v][c + 1] == 1)
                dp[v][c + 1]++, cout << "T", x.pb(v), y.pb(c + 1);
            if(!us[v - 1][c] && dp[v - 1][c] == 1)
                dp[v - 1][c]++, cout << "L", x.pb(v - 1), y.pb(c);
            if(!us[v][c - 1] && dp[v][c - 1] == 1)
                dp[v][c - 1]++, cout << "B", x.pb(v), y.pb(c - 1);

            if(k < n)
                cout << ",\n";
            else
                cout << ".\n";
        }

        us[v][c] = true;
        x.erase(x.begin());
        y.erase(y.begin());
    }
    return 0;
}

Edited by author 15.03.2013 23:27

My DP gets WA3, and I don't know why. But my BFS gets AC :)

I wrote a program about this problem but wa4....
I found an AC code but it can not pass this data,and I can pass.
8 12
1 2
2 3
3 4
4 1
1 5
2 6
3 7
4 8
5 6
6 7
7 8
8 5

here is my answer:
4
5 6 7 8 5 1 2 3 4 1
6 2
7 3
8 4

here is ac code answer:
7
1 2 3 1 4 3
4 5 1 6 5
6 7 1 8 7
8 9 1 10 9
10 11 1 12 11
12 13 1 14 13
14 2
I think he is wrong.

Please add this kind of data.
And I wanted to know the test for test 4.
Could you please tell me?
At last,sorry for my poor English.

first i hav taken input of 2d array.........and then sorted them using merge sort..... i know there is a problem in my logic.......but i can't find it......help me find it please.....


#include<stdio.h>

int main()
{
    int n,c,i,j,k,l,num;

    scanf("%d",&n);

    c=n-1;
    int ar[c][c];
    num=1;

    for(i=c;i>=0;i--)
    {
        for(j=0;j<n-i;j++)
        {
            ar[i][j]=num;
            num++;
        }
    }

        for(j=1;j<=c;j++)
        {
            for(i=0;i<n-i;i++)
            {
                ar[i][j]=num;
                num++;
            }
        }

            for(i=0;i<n;i++)
            {
                for(j=0;j<n;j++)
                {
                    printf("%d ",ar[i][j]);
                }
                printf("\n");
            }

            return 0;
}

Help with #2 test! give example data! all data in topics my programm pass!

I understand that we are only concerned with the points mentioned, and not all the points between 1 and 10^9. After forming a segment tree and making all the updates, how can we find the longest white colored segment?

Thank you.

Anyone had the same problem? please give a hint!!

My last submission (4829935) got AC, but I think this algo is wrong. For example, for test
8
0 0
3 -2
1 -3
-1 -5
-3 -3
-3 1
-5 6
3 1
it gives 1 5. Actually, I have no idea how it can get AC...

I see that many people have got execution time as 0.001 dunno how to achieve such a short execution time...any insights please...

What is test 5?