Ищем правду, решаем судоку и генерируем числа: подборка задач для программистов

Question 1

Оригинал задачи на английском языке

Answer

There are hundred statements.

1st one asserts : at least one is wrong.
2nd one asserts : at least two are wrong.
3rd one asserts : at least three are wrong.
4th one asserts : at least four are wrong.
…
100th one asserts : at least 100 are wrong.

How many statements are actually wrong and how many actually right ?

Question 2

Решение задачи на русском языке

Answer

100-е утверждение определенно ложно, поскольку опровергает само себя, следовательно:

100-е ложно и
1-е утверждение истинно.

99-е утверждение не может быть верным, поскольку тогда должно было бы быть 2 верных утверждения (1-е, и 99-е), хотя 99-е утверждение заявляет, что по меньшей мере 99 утверждений — ложны.

99-е ложно и
2 корректно

Рассуждая таким образом, можно посчитать, что 50 утверждений истинны (первые 50 утверждений) и 50 утверждений — ложны.

Question 3

Решение задачи на английском языке

Answer

100th statement is definitely wrong because it disproves own claim. But if that is correct, then 100 statement itself cannot be right.

100th statement is wrong and
1st statement is correct.

99th statement cannot be correct because if it were correct, then two statements would become correct (1st and 99th itself.) But 99th statement says that at least 99 are wrong.

99th is wrong and
2nd is correct.

calculating so on…

50 statements are right (the first 50 ones) remaining 50 statements are wrong.

Question 4

Оригинал задачи на английском языке

Answer

Given a Sudoku Board configuration, write a program to check whether it is valid or not.

Examples:

Input:

			[5 3 - - 7 - - - -]
[6 - - 1 9 5 - - -]
[- 9 8 - - - - 6 -]
[8 - - - 6 - - - 3]
[4 - - 8 - 3 - - 1]
[7 - - - 2 - - - 6]
[- 6 - - - - 2 8 -]
[- - - 4 1 9 - - 5]
[- - - - 8 - - 7 9]

Output: True

Question 5

Решение задачи на русском языке

Answer

Основная идея состоит в том, чтобы проверить каждую строку, столбец и квадрат 3х3 на корректность, согласно следующим соображениям:

Доска судоку может быть заполнена частично, пустые клетки заполняются символом «.».
Пустая доска — корректна.
Корректная доска судоку (частично заполненная) —не обязательно решаема. Нужно проверять только заполненные поля.

Question 6

Решение задачи на английском языке

Answer

The basic idea is to check whether each row, column, and the 3×3 box is valid or not on the basis of following points:

The Sudoku board could be partially filled, where empty cells are filled with the character «.».
An empty Sudoku board is also valid.
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Question 7

Код

Answer

			#include <bits/stdc++.h>
using namespace std;
 
// Checks whether there is any duplicate
// in current row or not
bool notInRow(char arr[][9], int row)
{
    // Set to store characters seen so far.
    set st;
 
    for (int i = 0; i < 9; i++) {
 
        // If already encountered before, return false
        if (st.find(arr[row][i]) != st.end())
            return false;
 
        // If it is not an empty cell, insert value
        // at the current cell in the set
        if (arr[row][i] != '.')
            st.insert(arr[row][i]);
    }
    return true;
}
 
// Checks whether there is any duplicate
// in current column or not.
bool notInCol(char arr[][9], int col)
{
    set st;
 
    for (int i = 0; i < 9; i++) {
 
        // If already encountered before, return false
        if (st.find(arr[i][col]) != st.end())
            return false;
 
        // If it is not an empty cell,
        // insert value at the current cell in the set
        if (arr[i][col] != '.')
            st.insert(arr[i][col]);
    }
    return true;
}
 
// Checks whether there is any duplicate
// in current 3x3 box or not.
bool notInBox(char arr[][9], int startRow, int startCol)
{
    set st;
 
    for (int row = 0; row < 3; row++) {
        for (int col = 0; col < 3; col++) {
            char curr = arr[row + startRow][col + startCol];
 
            // If already encountered before, return false
            if (st.find(curr) != st.end())
                return false;
 
            // If it is not an empty cell,
            // insert value at current cell in set
            if (curr != '.')
                st.insert(curr);
        }
    }
    return true;
}
 
// Checks whether current row and current column and
// current 3x3 box is valid or not
bool isValid(char arr[][9], int row, int col)
{
    return notInRow(arr, row) && notInCol(arr, col) &&
           notInBox(arr, row - row % 3, col - col % 3);
}
 
bool isValidConfig(char arr[][9], int n)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
 
            // If current row or current column or
            // current 3x3 box is not valid, return false
            if (!isValid(arr, i, j))
                return false;
        }
    }
    return true;
}
 
// Drivers code
int main()
{
    char board[9][9] = { { '5', '3', '.', '.', '7', '.', '.', '.', '.' },
                         { '6', '.', '.', '1', '9', '5', '.', '.', '.' },
                         { '.', '9', '8', '.', '.', '.', '.', '6', '.' },
                         { '8', '.', '.', '.', '6', '.', '.', '.', '3' },
                         { '4', '.', '.', '8', '.', '3', '.', '.', '1' },
                         { '7', '.', '.', '.', '2', '.', '.', '.', '6' },
                         { '.', '6', '.', '.', '.', '.', '2', '8', '.' },
                         { '.', '.', '.', '4', '1', '9', '.', '.', '5' },
                         { '.', '.', '.', '.', '8', '.', '.', '7', '9' } };
 
    cout << (isValidConfig(board, 9) ? "YES\n" : "NO\n");
    return 0;
}

Question 8

Оригинал задачи на английском языке

Answer

Write a method to generate a random number between 1 and 8, given a method that generates a random number between 1 and 3. The distribution between each of the numbers must be uniform.

Question 9

Решение задачи на русском языке

Answer

Попробуем представить задачу в виде дерева решений. Каждое rand3() является решением.

Если мы сможем как-либо сгенерировать числа, кратные 8 (8, 16, 24, …) с равной вероятностью, то можно будет использовать остаток от деления на 8 с добавлением 1 чтобы получить числа от 1 до 8 с равновероятным распределением.

Попробуем получить числа диапазона 1-8. Если будем получать числа выходящие из диапазона — повторим попытку. Поскольку вероятность получения каждого из 8 значений одинакова, повторные попытки не повлияют на их распределение.

Получить числа от 1 до 8 с равновероятным распределением можно используя следующее выражение:

3*rand3() + rand3() – 3

Как это можно использовать?

Всего возможны 3 комбинации значений как первого, так и второго rand3(). Следовательно всего возможны 9 комбинаций.
Диапазон возвращаемых значений будет от 1 до 9, с вхождением каждого числа ровно 1 раз.
Если полученное значение меньше 9 — возвращаем остаток от деления на 8 с добавлением 1. Иначе — рекурсивно повторяем генерацию числа. Распределение получаемых чисел будет ⅛.

Question 10

Решение задачи на английском языке

Answer

Let’s think of this like a decision tree. Each rand3() will be a decision.

If we somehow generate integers from 1 to a-multiple-of-8 (like 8, 16, 24, …) with equal probability, we can use modulo division by 8 followed by adding 1 to get the numbers from 1 to 8 with equal probability.

We try to get maximum bunches of 8 as we can (1-8, 1 set of 8). If we get any of the other values, we just try again. Since the probability of getting each of 8 values are the same every time, trying again won’t affect their probabilities.

We can generate from 1 to 9 with equal probability using the following expression.

3*rand3() + rand3() – 3

See, how this can be used?

For each value of first rand3(), there can be 3 possible combinations for values of second rand3(). So, there are total 9 combinations possible.
The range of values returned by the above equation is 1 to 9, each integer occurring exactly once.
If the value of the equation comes out to be less than 9, return modulo division by 8 followed by adding 1. Else, again call the method recursively. The probability of returning each integer thus becomes ⅛.

Question 11

Код

Answer

			// returns 1 to 8 with equal probability
int my_rand()
{
    int i;
	while(1)
	{
	    i = 3*rand3() + rand3() - 3;
	    if (i < 9)
	        return i%8 + 1;
	}
}

Ищем правду, решаем судоку и генерируем числа: подборка задач для программистов

Правильные и неправильные предложения

Проверка поля Судоку

Генератор равной вероятности