Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

AVAILABLE LESSONS:

Lesson 1

Iterations

Lesson 2

Arrays

Lesson 3

Time Complexity

Lesson 4

Counting Elements

Lesson 5

Prefix Sums

Lesson 6

Sorting

Lesson 7

Stacks and Queues

Lesson 8

Leader

Lesson 9

Maximum slice problem

Lesson 10

Prime and composite numbers

Lesson 11

Sieve of Eratosthenes

Lesson 12

Euclidean algorithm

Lesson 13

Fibonacci numbers

Lesson 14

Binary search algorithm

Lesson 15

Caterpillar method

Lesson 16

Greedy algorithms

Lesson 17

Dynamic programming

Lesson 90

Tasks from Indeed Prime 2015 challenge

Lesson 91

Tasks from Indeed Prime 2016 challenge

Lesson 92

Tasks from Indeed Prime 2016 College Coders challenge

Lesson 99

Future training

Find out how many dwarfs can fit on a raft such that it's balanced when crossing a river.

Spoken language:

A company of dwarfs is travelling across the New Zealand. On reaching the Clutha River the dwarfs need to get across, but recent storms have washed away the bridge. Luckily, a small ferry, in the form of a square raft, is operating.

The raft is square and has N rows of seats, numbered from 1 to N. Each row contains N seats, labeled with consecutive letters (`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

The raft has already been loaded with barrels in some seat positions, and other seats are already occupied by dwarfs. Our company of dwarfs may only take the remaining unoccupied seats. The ferryman wants to accommodate as many dwarfs as possible, but the raft needs to be stable when making the crossing. That is, the following conditions must be satisfied:

- the front and back halves of the raft (in terms of the rows of seats) must each contain the same number of dwarfs;
- similarly, the left and right sides of the raft (in terms of the columns of seats) must each contain the same number of dwarfs.

You do not have to worry about balancing the barrels; you can assume that their weights are negligible.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

The positions of the barrels are given in string S. The occupied seat numbers are given in string T. The contents of the strings are separated by single spaces and may appear in any order. For example, in the diagram above, S = "`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

In this example, the ferryman can accommodate at most six more dwarfs, as indicated by the green squares in the following diagram:

The raft is then balanced: both left and right halves have the same number of dwarfs (four), and both front and back halves have the same number of dwarfs (also four).

Write a function:

int solution(int N, char *S, char *T);

that, given the size of the raft N and two strings S, T that describes the positions of barrels and occupied seats, respectively, returns the maximum number of dwarfs that can fit on the raft. If it is not possible to balance the raft with dwarfs, your function should return `-1`.

For instance, given N = 4, S = "`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

In your solution, focus on ** correctness**. The performance of your solution will not be the focus of the assessment.

Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A company of dwarfs is travelling across the New Zealand. On reaching the Clutha River the dwarfs need to get across, but recent storms have washed away the bridge. Luckily, a small ferry, in the form of a square raft, is operating.

The raft is square and has N rows of seats, numbered from 1 to N. Each row contains N seats, labeled with consecutive letters (`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

The raft has already been loaded with barrels in some seat positions, and other seats are already occupied by dwarfs. Our company of dwarfs may only take the remaining unoccupied seats. The ferryman wants to accommodate as many dwarfs as possible, but the raft needs to be stable when making the crossing. That is, the following conditions must be satisfied:

- the front and back halves of the raft (in terms of the rows of seats) must each contain the same number of dwarfs;
- similarly, the left and right sides of the raft (in terms of the columns of seats) must each contain the same number of dwarfs.

You do not have to worry about balancing the barrels; you can assume that their weights are negligible.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

The positions of the barrels are given in string S. The occupied seat numbers are given in string T. The contents of the strings are separated by single spaces and may appear in any order. For example, in the diagram above, S = "`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

In this example, the ferryman can accommodate at most six more dwarfs, as indicated by the green squares in the following diagram:

The raft is then balanced: both left and right halves have the same number of dwarfs (four), and both front and back halves have the same number of dwarfs (also four).

Write a function:

int solution(int N, string &S, string &T);

that, given the size of the raft N and two strings S, T that describes the positions of barrels and occupied seats, respectively, returns the maximum number of dwarfs that can fit on the raft. If it is not possible to balance the raft with dwarfs, your function should return `-1`.

For instance, given N = 4, S = "`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

In your solution, focus on ** correctness**. The performance of your solution will not be the focus of the assessment.

Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A company of dwarfs is travelling across the New Zealand. On reaching the Clutha River the dwarfs need to get across, but recent storms have washed away the bridge. Luckily, a small ferry, in the form of a square raft, is operating.

The raft is square and has N rows of seats, numbered from 1 to N. Each row contains N seats, labeled with consecutive letters (`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

The raft has already been loaded with barrels in some seat positions, and other seats are already occupied by dwarfs. Our company of dwarfs may only take the remaining unoccupied seats. The ferryman wants to accommodate as many dwarfs as possible, but the raft needs to be stable when making the crossing. That is, the following conditions must be satisfied:

- the front and back halves of the raft (in terms of the rows of seats) must each contain the same number of dwarfs;
- similarly, the left and right sides of the raft (in terms of the columns of seats) must each contain the same number of dwarfs.

You do not have to worry about balancing the barrels; you can assume that their weights are negligible.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

The positions of the barrels are given in string S. The occupied seat numbers are given in string T. The contents of the strings are separated by single spaces and may appear in any order. For example, in the diagram above, S = "`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

In this example, the ferryman can accommodate at most six more dwarfs, as indicated by the green squares in the following diagram:

The raft is then balanced: both left and right halves have the same number of dwarfs (four), and both front and back halves have the same number of dwarfs (also four).

Write a function:

class Solution { public int solution(int N, string S, string T); }

that, given the size of the raft N and two strings S, T that describes the positions of barrels and occupied seats, respectively, returns the maximum number of dwarfs that can fit on the raft. If it is not possible to balance the raft with dwarfs, your function should return `-1`.

For instance, given N = 4, S = "`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

In your solution, focus on ** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

func Solution(N int, S string, T string) int

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

class Solution { public int solution(int N, String S, String T); }

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

class Solution { public int solution(int N, String S, String T); }

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

function solution(N, S, T);

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

fun solution(N: Int, S: String, T: String): Int

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

function solution(N, S, T)

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

int solution(int N, NSString *S, NSString *T);

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

function solution(N: longint; S: PChar; T: PChar): longint;

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

function solution($N, $S, $T);

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

sub solution { my ($N, $S, $T)=@_; ... }

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

def solution(N, S, T)

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

def solution(n, s, t)

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

object Solution { def solution(n: Int, s: String, t: String): Int }

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

public func solution(_ N : Int, _ S : inout String, _ T : inout String) -> Int

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.

`A`, `B`, `C`, etc.). Each seat is identified by a string composed of its row number followed by its column number; for example, "`9C`" denotes the third seat in the 9th row.

For example, a raft of size N = 4 is shown in the following illustration:

Barrels are marked as brown squares, and seats that are already occupied by dwarfs are labeled `d`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`".

Write a function:

Private Function solution(N As Integer, S As String, T As String) As Integer

`-1`.

`1B 1C 4B 1D 2A`" and T = "`3B 2D`", your function should return 6, as explained above.

Assume that:

- N is an even integer within the range [2..26];
- strings S, T consist of valid seat numbers, separated with spaces;
- each seat number can appear no more than once in the strings;
- no seat number can appear in both S and T simultaneously.

** correctness**. The performance of your solution will not be the focus of the assessment.