import java.util.*;

public class Test_1874 {
    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner s = new Scanner(System.in);
        int h, w, n;
        h = s.nextInt();
        w = s.nextInt();
        n = s.nextInt();

        String[] a = new String[n];
        for (int i = 0; i < n; i++) {
            a[i] = s.nextLine();
            if (a[i].isEmpty()) {
                a[i] = s.nextLine();
            }
        }

        if (n == 1) {
            System.out.println("1");
            return;
        }

        int b, c = 0, d = 0, list = 0, page = 0;

        for (int i = 0; i < n; i++) {
            b = (a[i].length() + 1);

            if (i == 0) {
                c = a[i + 1].length();

                if (b + c == w) {
                    list++;

                } else if (b + c < w) {
                    d = b + c;
                    c = a[i + 2].length();
                    if ((d + c) == w) {
                        list++;
                    } else if ((d + c) < w) {

                    } else {
                        list++;
                    }
                } else {
                    list++;
                }
            } else {

                if ((b + d) == w) {
                    list++;

                } else if ((b + d) < w) {
                    d = d + b;
                    c = a[i + 1].length();
                    if ((d + c) == w) {
                        list++;
                    } else if ((d + c) < w) {

                    } else {
                        list++;
                    }
                } else {
                    list++;
                }

            }

            if (list == h) {
                page++;
                list = 0;
            } else if (i == (n - 1)) {
                if(list>=1){
                    page++;
                }

            }

        }
        System.out.println(page);

    }
}

//*********************************************
//FreePascal 2.0.4
var a,b,u:longint;
begin readln(a,b);
for u:=1 to b do inc(a);
writeln(a);
end.

//*********************************************
//Visual C# 2010
using System;
public class Sum
{
    private static void Main()
    {
        string[] tokens = Console.ReadLine().Split(' ');
        Console.WriteLine(int.Parse(tokens[0]) + int.Parse(tokens[1]));
    }
}

//*********************************************
//Java 1.7
import java.util.Scanner;
public class test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(sc.nextInt() + sc.nextInt());
    }
}

import java.util.*;

public class Test_1874 {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner s = new Scanner(System.in);
        int n, k, m;

        n = s.nextInt();
        k = s.nextInt();

        long[] a = new long[k];
        for (int i = 0; i < k; i++) {
            a[i] = s.nextInt();
        }
        for (int i = 1; i < k; i++) {
            if (a[i] < a[i - 1]) {
                m = (int) a[i];
                a[i] = a[i - 1];
                a[i - 1] = m;
            }
        }
        m = (int) (n - (n - a[0]) - (n - a[1]));
        if (m <= 0) {
            System.out.println("0");
        } else {
            System.out.println(m);
        }
    }
}

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

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /**
     * call this method to initialize reader for InputStream
     */
    static void init(InputStream input) {
        reader = new BufferedReader(new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    /**
     * get next word
     */
    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}

public class _1106 {

    public static void main(String args[]) throws IOException {
        int a;
        Reader.init(System.in);

        int n = Reader.nextInt();
        int graph[][] = new int[n][n];
        ArrayList<ArrayList<Integer>> st = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> grp1 = new ArrayList<Integer>();
        ArrayList<Integer> grp2 = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> ar = new ArrayList<Integer>();
            do {
                a = Reader.nextInt();
                if (a != 0) {
                    graph[i][a - 1] = 1;
                    ar.add(a - 1);
                }

            }
            while (a != 0);
            st.add(ar);
        }


        if (n != 0) {
            grp1.add(0);
            for (int i = 1; i < n; i++) {
                if (graph[0][i] != 1) {
                    grp1.add(i);
                } else {
                    grp2.add(i);
                }
            }

            for (int i = 1; i < grp1.size(); i++) {
                int x = grp1.get(i);

                if (!st.get(x).isEmpty()) {
                    boolean frFlag = false;
                    Iterator it = st.get(x).iterator();
                    while (it.hasNext()) {
                        if (grp2.contains((Integer) it.next())) {
                            frFlag = true;
                            continue;
                        }
                    }

                    if (!frFlag) {
                        Integer rm = st.get(x).get(0);
                        //grp1.r
                        grp1.remove(rm);
                        grp2.add(rm);
                    }
                }

            }

            System.out.println(grp1.size());
            Iterator it1 = grp1.iterator();
            while (it1.hasNext()) {
                System.out.print(((Integer) it1.next() + 1) + " ");
            }
        } else {
            System.out.println(0);
        }

    }
}

Edited by author 05.06.2014 17:45

Edited by author 05.06.2014 18:23

Edited by author 05.06.2014 18:41

Edited by author 05.06.2014 18:53

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Scanner;

public class Test {
    public static void main(String[] args) throws IOException {
        new Test().solve();
    }

    private static Scanner s = new Scanner(System.in);
    static int n = 0;

    void solve() throws IOException {

        String input = null;
        String[] strArray = new String[30];

        while (true) {
            input = getString();

            if (input.equals("#")) {
                break;
            } else {
                saveItToArray(strArray, input);
            }
        }

        checkOutIdentical(strArray);

        System.out.println(n - 1);
    }

    private static String getString() throws IOException {

        String input;

        input = s.nextLine();
        return (input);
    }

    void saveItToArray(String[] strArray, String input) {
        boolean isDash = false;
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '-') {
                strArray[n++] = input.substring(0, i);
                strArray[n++] = input.substring(i + 1, input.length());

                isDash = true;
                break;
            } else {
                isDash = false;
            }
        }

        if (!isDash) {
            strArray[n++] = input;
        }

    }

    void checkOutIdentical(String[] strArray) {
        int count = 0;
        count = n;
        for (int i = 1; i < count; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (!strArray[i].equals(" ") && !strArray[j].equals(" ")
                        && strArray[i].equals(strArray[j])) {
                    strArray[i] = " ";
                    n--;
                }
            }
        }
    }

}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_READ 250000
#define MASIVE(a, b) (b *) malloc(sizeof(b *)*(a))
#define STRING(a) MASIVE((a), char);

#define R_CONCAT(T,S,A) strcat(A, T); \
                        strcat(A, " "); \
                        strcat(A, S); \

int * Z_simple(char * str, int len) {
  int * z = MASIVE(len, int);

  for (int i = 1;  i < len; i++) {
    int * val = z + i;
    *val = 0;
    for (int j = 0; i + j < len; j++) {
      if (str[i + j] != str[j]) {
        break;
      }
      (*val)++;
    }
  }
  return z;
}

int * Z(char * str, int len) {
  int * z = MASIVE(len, int);
  int l = 0, r = 0;

  for (int k = 1; k < len; k++) {
    if (k > r) {
      l = k;
      int pos = 0;

      while (k + pos < len && str[pos] == str[k + pos]) {
        pos++;
      }

      if (pos == 0) {
        r = l;
        z[k] = 0;
      } else {
        r = k + pos - 1;
        z[k] = pos;
      }

    } else {
      int m = k - l;
      int b = z[l] - m;
      if (z[m] < b) {
        z[k] = z[m];
      } else {

        int pos1 = b;
        int pos2 = k + b;
        int pos = 0;

        while(pos2 + pos < len && str[pos1 + pos] == str[pos2+pos]) {
          pos ++;
        }

        if (pos != 0) {
          l = k;
          r = pos2 + pos - 1;
          z[k] = b + pos;
        } else {
          z[k] = b;
        }

      }
    }

  }

  return z;
}



int main() {

    int n;
    int result = -1;
    scanf("%d", &n);

    char * T = STRING(n);
    char * S = STRING(n);

    scanf("%s%s", T, S);

    int len_N = 2*n + 1;

    char * N = STRING(len_N);

    R_CONCAT(T,S,N);

    int * z = Z(N, len_N);
    z = z + (n + 1);

    for (int i = 0; i < n; i++) {
        if (z[i] == n - i) {
            int k = z[i];
            int b = 0;
            for (int j = 0; j < i; j++) {
                if (T[k + j] != S[j]) {
                     b = 1;
                     break;
                }
            }
            if (b == 0)
                result = i;
            break;
        }
    }

    printf("%d", result);
}

Edited by author 04.06.2014 19:39

Main idea:

Number tree levels from bottom to top like: 0th, 1st, 2nd ...

We can traverse the whole tree, but it would take at most 2^31 vertexes to visit. I call [traversing the whole tree]: going from bottom left vertex to bottom right vertex of the tree. So we can observe that we can skip traversing some part of the tree. Since traversing tree A of level AL is the same as traversing two smaller trees with levels (AL-1) + 2*(cost to go from bottom to top (highest) vertex of tree A). Example:

  +-----+4+----+
  +            +
++2++        ++6++
+   +        +   +
1   3        5   7

To traverse tree A (from 1 to 7) with level 2 is the same as traversing tree B (from 1 - 3) with level 1 twice and adding costs: from 3 to 4, from 4 to 5.

Let's call m[level of tree] = min cost to traverse tree with such level from bottom left to bottom right of tree. Then we could find out what is traversal cost for each tree with arbitrary level like:

 for 1..MAX_LEVEL_OF_TREE:
    m[i] = 2 * m[i - 1] + 2 * (i - 1);

We traverse tree from left to right. We shall call destination vertex d, current vertex c and level of tree where we can find c: cl. Initially c is vertex we start from.
We know that if we are standing at c, vertex number that is one level above c is: upRight = c + 2^cl. So if  d >= upRight we have to go to upRight vertex, because here: [c ; upRight-1] is no destination vertex.

Similarly we know that if we are standing at c, vertex number that is at 0th level to the right of c is: downRight = c + 1. We should go to downRight  if: d < upRight.

So finally:

cost(v) - cost by going directly from bottom vertex to v. Example: cost(8) = 2, cost(16) = 3.

We go up right if d >= upRight :
[whole cost] = [whole cost] + m[cl - 1] + cost(c) + cost(upRight)
c = c + 2^cl

We go down right if if d < upRight:
[whole cost] = [whole cost] + cost(c)
c = c + 1

Complexity similar to log(n)^2

procedure do;
var     n:int64;
begin
        if eof then exit;
        read(n);
        do;
        writeln(sqrt(n):0:4);
end;

begin
        do;
end.


I think this problem is quite easy.
Please tell me why it gives wrong answer, thank you!

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

namespace _1869_2
{
    class Program
    {
        static void Main(string[] args)
        {
            Random random = new Random();
            int rand;
            int i, j, k, max;



            int N = int.Parse(Console.ReadLine());
            int[,] A = new int[100, 100];

            for (i = 0; i <N; ++i)
                for (j = 0; j <N; ++j)
                {
                    if (i == j)
                        A[i, j] = 0;
                    else
                    {
                        rand = random.Next(0, 1000);
                        A[i, j] = rand;
                    }
                }
            for (i = 0; i < N; i++)
                for (j = 0; j < N; j++)
                {
                    if (A[i,j] == 0)
                        continue;

                    // Vladi -> Moscow
                    if (i < j && j - i > 1)
                    {
                        for (k = i; k < j; k++)
                        {
                            A[k,k + 1] += A[i,j];
                        }
                    }
                    // Moscow -> Vladi
                    else if (i > j && i - j > 1)
                    {
                        for (k = i; k > j; k--)
                        {
                            A[k,k - 1] += A[i,j];
                        }
                    }
                };

            // get maximum for each pair of stations
            max = 0;
            for (i = 0; i < N - 1; i++)
            {
                if (Math.Max(A[i,i + 1], A[i + 1,i]) > max)
                {
                    max = Math.Max(A[i, i + 1], A[i + 1, i]);
                }
            }
            if (max % 36 == 0)
            {
                max /= 36;
                Console.WriteLine(max);
            }
            else
            {
                max /= 36;
                max = max + 1;
                Console.WriteLine(max);
            }

            //Console.ReadKey();

        }
    }
}

double res = (bpi*bvi)/(bti*R);
cout << "n = ";
if(res < 1)
    printf("%.0f", res);
else
    printf("%.6f", res);

When res (n) < 1 u should cout 0 else u should cout number with an error.
Good Luck!

Greedy can pass this problem quickly.

if you deal with n>5 and n<=5 cases separately. The former does not require any factorial calculation

That's magical and I don't think there's any undefined behaviors etc. in my code..
Those who are puzzled in ridiculous WA may try to change the compiler.

crc16 hash table is not working on test 7.

someone solved using hash tables?

Very good task.Thanks!!!

10 0
1

2 1
0

30 95
0

3 4
36

3 6
100

10 30
1657615050256

15 30
5988336077235600

20 100
475696100826892995150152084506564

50 300
3660144008320861404705392514284143308670326732628084621145897204106027006076468826991924409

тем, у кого не получилось, советую поменять операции writeln и readln на write и read. Тоже не понимал, почему не получается, испробовал кучу входных данных - все было правильно. но программа давала WA в первом же тесте. Однако, как только сделал так, как указал выше, все сразу получилось.

Edited by author 01.06.2014 20:08

Edited by author 01.06.2014 20:08

Can anyone please tell me what is test case #5....My code is giving the correct ans for all the tests in the forum..