Can someone tell me the test case 2 please.

I am new in here and I need some help with 1017. Staircases.

Edited by author 14.03.2015 15:34

Edited by author 14.03.2015 15:34

What may it be? i've try any test i can think and any test in other discussins,but still WA #11.
I tested :
-------
WHAT ARE YOU DOING?
- I AM EATING.
- really?
-Yes,(new line)
REALLY!
- ok, i KNOW.
i TRUST YOU.
-------
and my program output :

-------
What are you doing?
- I am eating.
- Really?
-Yes,
really!
- Ok, i know.
I trust you.
-------
I don't know what's wrong, help, please.

For my first try I wrote this:

def sum_of_digits(n)
  sum = 0
  while (n > 0)
    sum += n % 10
    n /= 10
  end
  sum
end

num_digits = gets.chomp.to_i

exponent = num_digits/2
divisor = 10**exponent

limit = (10**num_digits) - 1
total = 0

0.upto(limit) do |cur|
  upper = cur / divisor
  lower = cur % divisor
  total += 1 if sum_of_digits(upper) == sum_of_digits(lower)
end

puts total

# eof

For 2, 4 and 6 digits it got the requisite answers of 10, 670, and 55252.  There was a bit of a pause while it crunched away at the 6-digit case, though.

For 8 digits it … well, I let it run and went to do something else.  Then I had the bright idea to time it (on mac OS X, using the time command):

4816030

real    1m42.596s
user    1m34.222s
sys    0m1.837s

The right answer, but the last time I checked, one minute anything was greater than two seconds.  What to do?

It’s pretty clear that calling sum_of_digits a bunch more times than necessary is the biggest problem. For try #2, I precomputed the sums and stuffed them into an array, and indexed the array in place
of calling sum_of_digits in the main loop.  Here’s the result:

time ruby lucky.rb < t8.txt
4816030

real    0m19.176s
user    0m18.017s
sys    0m0.313s

A better than 80% speedup.  Most times I would kill for that, but I still need to lose 95% of the remaining run time.  How to do it?

I checked … initializing the array of sums takes virtually no time, even if I write out the entire array contents to a file.

So the main loop is killing me, and unfortunately I need a dramatic change of algorithm but I
don’t see one. So …

1. Recode in C or C++
2. Hell if I know

Taking option 1, I got Accepted, with run times around 1.1 seconds or so for 8 digits.  It's a straightforward translation to C++, very brute force.

Try this test:
-1 -1
1

Answer:
0.00
0 0

Solved it with time of 0.5 sec and using "Trie" where I keep the name of each directory as a node.

Write me novopashinwm@mail.ru

Give me some input values with answers, please, so I could find out, what's wrong.

  if(s.equals("Blue")|| s.equals("blue"))
  if(s.equals("Red") || s.equals("red"))
  if(s.equals("Yellow") || s.equals("yellow"))

Can anybody explain the combinatorial approach of this problem ???
  Greetings

import java.io.*;
import java.lang.*;
import java.util.*;

public class MathSqrt
{
    public static void main(String[] args) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        double[] array = new double[4];

        for(int i = 0; i < array.length; i++)
        {
            array[i] = sc.nextDouble();
        }

        for(int i = array.length - 1; i >= 0 ; i--)
        {
            double b = Math.sqrt(array[i]);
            System.out.println(b);
        }

    }
}

Edited by author 18.02.2015 17:39

Edited by author 18.02.2015 17:39

idea...!

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _2035
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] arrS = Console.ReadLine().Split(' ');
            long a = long.Parse(arrS[0]);
            long b = long.Parse(arrS[1]);
            long c = long.Parse(arrS[2]);
//10^9 =1 000 000 000

            if (((c - b) > a && (c-b)>0))
                Console.WriteLine("Impossible");
            else if (((c - a) > b && (c-a)>0))
                Console.WriteLine("Impossible");
            else if ((c - b) > 0 )
                Console.WriteLine("{0} {1}", (c - b), b);
            else
                Console.WriteLine("{0} {1}", (c - a), a);

        }
    }
}

Edited by author 06.03.2015 12:54

Notice that k maybe be bigger than n.

Could anyone provide any information about the 11-th test?

This is my programm below:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Globalization;

namespace _1248
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            double s = 0;
            for (int i = 0; i < n; i++)
            {
                string strS = Console.ReadLine();
                double ch =0;
                if (strS.Contains("e"))
                {
                    string[] arr = strS.Split('e');
                    double ss = double.Parse (arr[1]);
                    ch = double.Parse(arr[0], CultureInfo.InvariantCulture) *  Math.Pow(10, ss);
                }
                else
                    ch = double.Parse  (strS );

                s +=ch;
            }

            StringBuilder sb = new StringBuilder();
            sb.AppendFormat("{0:0.000000000000000000e0}", s);
            string sss = sb.ToString();
            sss = sss.Replace(',', '.');
            //sss = sss.Replace("e0", "");
            Console.WriteLine(sss);
        }
    }
}

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Scanner;

public class Election {
    static long count;

    public static void main(String agrs[]) {
        Scanner scan = new Scanner(System.in);
        long N = scan.nextInt();
        long N1 = scan.nextInt();
        DecimalFormat form = new DecimalFormat("0.00");
        ArrayList<Integer> array = new ArrayList<Integer>();
        for (int i = 0; i < N1; i++) {
            array.add(scan.nextInt());
        }

        for (int i = 1; i <= N; i++) {

            for (int j = 0; j < N1; j++) {
                if (array.get(j) == i) {

                    count++;

                }

            }

            System.out.println(form.format((count * 100) / N1) + "%");
            count = 0;
        }
    }

}
===================
Cant find any error. :(

Right or wrong my answer to the next test?
10
1 1 2 2 3
10 1 11 2 1
5 5 6 7 2
3 4 8 7 3
1 3 9 9 3
12 11 15 12 1
3 3 6 6 2
4 6 8 10 3
3 7 4 12 3
2 5 4 7 2
4 50

rez:
107.071068
35.355339  35.355339


and this one:

10
1 1 2 2 8
10 1 11 2 1
5 5 6 7 2
3 4 8 7 3
1 3 9 9 3
12 11 15 12 6
3 3 6 6 5
4 6 8 10 3
3 7 4 12 3
2 5 4 7 2
4 50

rez:
153.263903
19.695965 45.957252

Edited by author 21.11.2007 14:15

Edited by author 15.03.2008 10:46

Edited by author 15.03.2008 10:49

Let your recursion function is "void dfs1(int k, int curr)", k is digit, curr is current S, then use it code:

    int start = 0;
    start = max(start, curr - 9 * (k - 1));

    int end = min(9, curr);
    if(k == 10) {
        end = min(1, end);
    }

    for(int i = start; i <= end; i++) {
        dfs1(k - 1, curr - i);
    }

It turns out, curr does not go beyond zero at k = 0!
I have 937ms with this solution

But with precalc I have 31ms :)
Good luck

Think about how many sides of steaks you need to cook, not in terms of whole steaks.
Except you can't cook both sides at the same time (when k > n).