I am getting wrong answer for test case 12 again and again. Any idea where can be the problem or what can be the test case?

My program had WA Test#7. Last two lines were:
    printf("The distance to the iceberg: %.2lf miles.\n",ans);
    if (ans<99.999) printf("DANGER!");
But when I changed only the last one:
    if (ans<99.995) printf("DANGER!");
I got AC!

(Now I think, that I should compare with 100 miles not answer, but it with two digits: so 99.996 is 100.00, but 99.994 is 99.99.)

search if there are the number in the certain interval, use balanced search tree

that you needn't parse the Martian letters, you can keep them as opaque strings, using them as map keys

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!

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