Как окружить единицы их порядковыми номерами в матрице?

#cpp #массивы #алгоритм #матрицы #олимпиада

  Дан двухмерный массив целых чисел. Массив заполнен нулями и единицами.
  "Окружить" каждую единицу, заменив только 0 на порядковый номер
  единицы в массиве, считая от левого верхнего угла и далее по строкам.
  
  Пример входного потока:5 5
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 0 0
     
  
  Пример выходного потока: 
1 1 2 0 0
1 1 2 0 0
3 3 4 5 5
0 0 5 1 5
0 0 5 5 5     


Привожу свою версию, но я явно что-то делаю не так, например, если единица стоит
в конце строки, неверно считает. Или, если массив состоит из одной-двух строк или столбцов.
Выводит порядковый номер даже когда единиц поблизости нет. Очень прошу помощи!

#include 
#include 
using namespace std;
int main()
{
  int x,y,q=0;
  cin >> x >> y;
  int a[x][y];
  for (int i=0;i> a[i][j];
    }
  }
  for (int i=0;i3) lim1=3; else lim1=x;
        if (y>3) lim2=3; else lim2=y;
        for (int m=0;m

Ответы
Ответ 1

Как-то так, если я правильно понял условие.

#include 
#include 
using namespace std;
int main() {
    int x, y, q = 0;
    cin >> x >> y;
    vector> m(x, vector(y, 0));
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            cin >> m[i][j];
        }
    }
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            if (m[i][j] == 1) {
                q++;
                // обход подматрицы 3x3, центр которой 1
                for (int a = i - 1; a <= i + 1; a++) {
                    for (int b = j - 1; b <= j + 1; b++) {
                        // проверка границ и что элемент можно изменить
                        if (a >= 0 && a < x && b >= 0 && b < y && m[a][b] == 0) {
                            m[a][b] = q;
                        }
                    }
                }
            }
        }
    }

    for (auto& v : m) {
        for (auto& i : v) {
            cout << i << ' ';
        }
        cout << '\n';
    }
}


Ответ 2

#include 


int main()
{
    int x = 5;
    int y = 5;

    int matrix[x][y] = { {1, 0, 0, 0, 0},
                         {0, 0, 0, 0, 0},
                         {0, 0, 0, 0, 0},
                         {0, 0, 0, 1, 0},
                         {0, 0, 0, 0, 0} };

    for (int i = 0; i < x; ++i)
    {
        for (int j = 0; j < y; ++j)
        {
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }

    std::cout << std::endl;

    int count = 0;
    int points[8][2] = { {-1,  1},
                         { 0,  1},
                         { 1,  1},
                         { 1,  0},
                         { 1, -1},
                         { 0, -1},
                         {-1, -1},
                         {-1,  0}};

    for (int i = 0; i < x; ++i)
    {
        for (int j = 0; j < y; ++j)
        {
            if (matrix[i][j] == 1)
            {
                ++count;
                for (auto point : points)
                {
                    int xi = i + point[0];
                    int yj = j + point[1];

                    if (xi < 0 || xi >= x)
                    {
                        continue;
                    }

                    if (yj < 0 || yj >= y)
                    {
                        continue;
                    }

                    if (matrix[xi][yj] == 0)
                    {
                        matrix[xi][yj] = count;
                    }
                }
            }
        }
    }

    for (int i = 0; i < x; ++i)
    {
        for (int j = 0; j < y; ++j)
        {
            std::cout << matrix[i][j] << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

Есть ли смысл заниматься олимпиадным программированием? [закрыт]

#php #олимпиада

        
             
                
                    
                        
                            Закрыт. На этот вопрос невозможно дать объективный ответ.
Ответы на него в данный момент не принимаются.
                            
                        
                    
                
                                Закрыт 3 года назад.
            
                    
        
             
                
                        
                            
                        
                    
                        
                            Заблокировано. Этот вопрос и ответы на него заблокированы,
так как он не соответствует тематике сайта, но имеет историческое значение. Для него
недоступна публикация ответов и другие действия.
                            
                        
                    
                
                            
                    
Работаю веб-разработчиком (junior). Недавно проходил курс, где попалась олимпиадная
задача. Решить ее смог, но решение было далеко от идеала (сверил с решением автора).
Ну и задачи подобного формата мне даются сложно.

Поможет ли мне олимпиадное программирование в развитии программистких скиллов, если
выделю 6-7 часов в неделю?

Хипстерские советы типа "Лучше подключись к open source проекту на github" не актуальны. 

Какую литературу можете посоветовать?
    

Ответы

Ответ 1

Олимпиадное программирование даст вам хорошую эрудицию в алгоритмах и комбинаторике.
В целом весьма полезные знания и умения. Задачи, требующие таких знаний, в реальной
жизни бывают, но редко, зависит от наукоёмкости предметной области.

Сам по себе стиль в котором решаются олимпиадные задачи -- выполнить задачу хоть
как, но уложиться в заданное время -- в обычном программировании чаще всего неприемлем:
обычно тут нужно решить задачу с должным качеством, включая качество написанного кода,
за приемлемое время. Причём важен навык оценки времени на разработку и способность
уложиться в заявленное время. Понятность решения часто даже важнее производительности
-- потому что если кроме вас в этом никто не разберётся, то всё равно перепишут "как
проще".

Единственная ситуация в жизни, которая действительно похожа на олимпиадную -- это
когда кто-то (чаще всего вы сами) накосячили на проде, и нужно срочно найти решение
проблемы и пофиксить.

Успешным олимпиадникам на обычных проектах скучно -- мало мест где можно себя проявить,
зато море рутины.

Найти количество произведений пар чисел, которое кратно 10

#алгоритм #любой_язык #олимпиада

Добрый день, задача по олимпиадному программированию из егэ этого года. 

На вход подается целое положительное число N, не превышающее 10000, и последовательность
из N целых положительных чисел, не превышающих 1000. Программа должна выводить число
пар чисел, произведение чисел в которых кратно 10. При этом числа, произведение которых
мы проверяем на кратность, не обязаны стоять рядом: пара может составляться и из чисел,
взятых с разных концов последовательности. 
Пример входных данных: 

4
2 5 7 4 


Пример выходных данных: 

2 


Здесь подходят пары (2;5) и (5;4).

Решение перебором очевидно, но меня интересует решение эффективное по памяти и по
времени. Под эффективностью по времени и по памяти в егэ подразумевают следующее: 


  Программа считается эффективной по времени, если время работы программы пропорционально
количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно
увеличиваться не более чем в k раз.
  Программа считается эффективной по памяти, если размер памяти, использованной в
программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.


Очень интересно разобраться с этой задачей, буду благодарен за любую помощь. Язык
программирования не важен, я хочу понять сам алгоритм. 
    

Ответы

Ответ 1

Заводим массив a на 10 элементов - по остаткам от деления на 10.
Для каждого считанного числа x увеличиваем a[x%10].
Считаем сумму:


Умножаем a[0] на сумму всех остальных элементов
Умножаем a[5] на значения по чётным индексам кроме 0
т. к. произведение двух кратных 10 чисел тоже делится на 10, a[0] * (a[0]-1)



Бррр... А теперь упрощаем:


a0 - количество чисел, которые делятся на 10
b0 - количество чисел, которые не делятся на 10
a2 - количество чисел, которые делятся на 2, но не на 10
a5 - количество чисел, которые делятся на 5, но не на 10


Обращаю внимание, что в b0 входят a2 и a5.

Ответ: a0*(a0-1+b0) + a2*a5.

И ещё упрощаем: a0-1+b0 - это n-1.

PS: В соответствии с требованиями, надо не держать массив в памяти, а обрабатывать
по мере чтения.

Помогите пожалуйста разобраться с задачей на Python3

#python #python_3x #олимпиада

Система проверки сайта не принимает решение, пожалуйста подскажите где ошибка.  

Собственно задача:

1002.Телефонные номера


  Ограничение времени: 2.0 секунды
  Ограничение памяти: 64 МБ  


В современном мире вы встречаетесь с огромным количеством телефонных номеров,
которые со временем становятся всё длиннее и длиннее. И вам приходится
запоминать эти номера. Одним из простых способов запоминания является сопоставление
букв каждой цифре, как показано на следующем рисунке:  

1 ij    2 abc   3 def
4 gh    5 kl    6 mn
7 prs   8 tuv   9 wxy
        0 oqz


Таким образом, каждому слову или группе слов может быть сопоставлен уникальный номер,
так что можно запоминать слова вместо телефонных номеров. Очевидно, есть особый шарм
в том,
чтобы найти простую взаимосвязь между словом, используемым для запоминания телефонного
номера,
и владельцем этого номера. Так, телефонный номер 941837296 вашего друга, играющего
в шахматы,
может быть прочитан как WHITEPAWN (белая пешка), а номер 2855304 Вашего любимого учителя
может быть прочитан как BULLDOG (бульдог).  

Напишите программу, находящую самую короткую последовательность слов
(имеющую наименьшее количество слов), которая соответствует заданному номеру телефона и
заданному списку слов. Соответствие описано на рисунке выше.  

Исходные данные

Ввод состоит из набора тестов. Первая строка каждого теста содержит номер телефона,
к которому нужно подобрать мнемонику. Номер состоит не более чем из 100 цифр.
Вторая строка содержит общее количество слов в словаре (максимум 50 000).
Каждая из оставшихся строк содержит одно слово,
состоящее не более чем из 50 строчных латинских букв.
Общий размер ввода не превосходит 300 килобайт.
Последняя строка ввода содержит число −1.

Результат

Каждая строка вывода должна содержать кратчайшую последовательность слов, найденную
вашей программой. 
Слова должны быть разделены одиночными пробелами. Если для входных данных нет решения,
соответствующая 
строка вывода должна содержать текст No solution.. 
Если существует несколько решений, имеющих одинаковое количество слов, можете выбрать
любое из них.


Ввод и вывод данные авторами для примера:

7325189087
5
it
your
reality
real
our
4294967296
5
it
your
reality
real
our
-1
# Ожидаемый результат  
reality our
No solution.


Мои вводные для теста:

2272583262772
11
ba
ra
ku
k
ss
u
ma
da
m
a
ssa
-1


По логике ответ должен быть

ba ra ku da ma ssa


Но это решение почему-то в список возможных не попадает.
Причем если ma расположить после da то это решение находится.
Вот список решений из которых идет выбор оптимального:  

['ba', 'ra', 'ku', 'da', 'm', 'a', 'ss', 'a']
['a', 'a', 'ra', 'ku', 'da', 'm', 'a', 'ss', 'a']


И соответственно оптимальным код считает:  

ba ra ku da m a ss a


Ну и соответственно валидатор не принимает это решение.
Подскажите пожалуйста где косяк

Мое решение:

keyboard = {'1': 'ij', '2': 'abc', '3': 'def',
            '4': 'gh', '5': 'kl', '6': 'mn',
            '7': 'prs', '8': 'tuv', '9': 'wxy',
            '0': 'oqz'}

while True:
    phone_num = input()
    solutions = []
    if phone_num == '-1':
        break
    phone_len = len(phone_num)
    words = [input() for _ in range(int(input()))]
    collector = []
    for word in words:
        if len(word) > phone_len:
            continue

        solution = []
        for i in range(len(word)):
            if word[i] not in keyboard[phone_num[i]]:
                break

        else:
            solution.append(word)
            test_solution = []

            while test_solution != solution:
                test_solution = solution.copy()
                raw_solution = ''.join(solution)
                len_solution = len(raw_solution)
                new_words = [item for item in words if len(item) <= phone_len - len_solution]
                if new_words:
                    for item in new_words:
                        raw_solution = ''.join(solution)
                        len_solution = len(raw_solution)
                        test_string = raw_solution + item
                        len_test_string = len(test_string)
                        if len_test_string > phone_len:
                            continue
                        for s in range(len_solution, len_test_string):
                            if test_string[s] not in keyboard[phone_num[s]]:
                                break
                        else:
                            solution.append(item)

            solutions.append(solution)

    if solutions:
        solutions.sort(key=lambda g: len(g))
        print(*solutions[0])
    else:
        print('No solution.')

    

Ответы

Ответ 1

Общий принцип решения:

Пусть N – длина телефонного номера.

Словарь представим как список из M слов.

Все слова словаря можно сразу переписать как последовательности чисел номера.

Затем создаём квадратную матрицу размерности N+1 x N+1 (Я предполагаю, что индексы
везде начинаются с 0).

Каждая ячейка (i,j) = k  матрицы означает, что у нас есть слово под номером k из
словаря такое, что оно совпадает с частью i .. j-1 цифр телефона.

Заполним все её ячейки значением -1. Это будет обозначать, что у нас нет такого слова.

Затем в цикле по всем словам проверяем, к какой части телефонного номера они подходят
и заполняем матрицу.

Затем поиском в ширину находим путь в нашей матрице из 0 в N.

Если путь найден, слова из словаря под значениями ячеек пути будут решением задачи,
иначе "No solution."

Время заполнения матрицы O(NxM). Время поиска в ширину O(NxN). 

Не самый оптимальный способ: 

n = len(phone_num)
m = int(input())
words = [input() for _ in range(m)]

# Создаём матрицу (n+1) x (n+1)
a = [[-1] * (n+1) for i in range(n+1)]


wordNumbers = [convertToNumber(words[i]) for i in range(m)]

# Заполняем матрицу переходов
# перебираем слова и проверяем, что они совпадают с частью номера телефона
for i in range(n):
    for k in range(m):
        number = wordNumbers[k]
        number_length = len(number)

        if (phone_num[i:i+number_length] == number):
            a[i][i+number_length]=k


#Поиск в ширину

# Сюда будем записывать вершины пути 
# (вес, откуда пришли, куда идём)
# По вершине на каждую цифру номера
vertex = [(10000000,-1,-1)] * (n+1)

stack = []
stack.append(0)
vertex[0]=(0, 0, 0)

while(stack):
    top = stack.pop()
    ver = vertex[top]
    new_weight = ver[0] + 1
    for j in range(top+1, n+1):
        k = a[top][j]
        if k > -1:
            v = vertex[j]
            if v[0]>new_weight:
                if v[1] == -1:
                    stack.append(j)
                vertex[j] = (new_weight, top, k)


# Извлечение пути

rver = vertex[n]
if rver[1] == -1: #Мы не достигли конца
    print('No solution.')
else:
    way = []
    pos = n
    while pos != 0:
        v = vertex[pos]
        way.insert(0,words[v[2]])
        pos = v[1]
    print(' '.join(way))


Остальное вам, наверное, понятно.


Ответ 2

Еще одно решение. Проходит все тесты.

# Класс, описывающий структуру вершин графа
class Vertex(object):
    def __init__(self, value, predecessor):
        # Слово
        self.value = value
        # Список вершин-наследников = вершина предка + длина слова
        self.successor = predecessor + len(value)
        # Метка посещения вершины
        self.is_explored = False

    def __eq__(self, other):
        return self.successor == other.successor


# Функция перевода слова в его цифровое представление
def get_number(value):
    letters = {
        'i': '1', 'j': '1', 'a': '2', 'b': '2', 'c': '2', 'd': '3', 'e': '3', 'f':
'3', 'g': '4', 'h': '4', 'k': '5',
        'l': '5', 'm': '6', 'n': '6', 'p': '7', 'r': '7', 's': '7', 't': '8', 'u':
'8', 'v': '8', 'w': '9', 'x': '9',
        'y': '9', 'o': '0', 'q': '0', 'z': '0'
    }
    return ''.join([letters[ch] for ch in value])


# Возвращает список всех возможных вершин слова
def get_vertex(edge, path):
    start = 0
    while True:
        try:
            vertex = path.index(edge, start)
            yield (vertex)
            start = vertex + 1
        except ValueError:
            break


# Функция нахождения кратчайшего пути методом поиска в глубину (BFS)
def bfs_shortest_path(graph, start, goal):
    queue = [[vertex] for vertex in graph[start]]

    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node.is_explored:
            continue
        try:
            neighbours = graph[node.successor]
            for neighbour in neighbours:
                new_path = list(path)
                new_path.append(neighbour)
                queue.append(new_path)
                if neighbour.successor == goal:
                    return new_path
        except KeyError:
            pass

        node.is_explored = True

    return None


if __name__ == '__main__':
    while True:
        phone = input()
        if phone == '-1':
            break

        # Метка существования слова, с которого начинается номер
        is_start = False
        # Метка существования возможного результата
        is_result = False
        result = ''
        # Граф
        dictionary = {}

        for _ in range(int(input())):
            word = input()
            if is_result:
                continue
            number = get_number(word)
            if number == phone:
                is_result = True
                result = word
            else:
                for position in get_vertex(number, phone):
                    if position == 0:
                        is_start = True
                    vertex_word = Vertex(word, position)
                    try:
                        if any(map(lambda w: w == vertex_word, dictionary[position])):
                            continue
                        dictionary[position] += [vertex_word]
                    except KeyError:
                        dictionary[position] = [vertex_word]

        if is_result:
            print(result)
            continue
        if is_start:
            result = bfs_shortest_path(dictionary, 0, len(phone))
            if result:
                print(' '.join([word.value for word in result]))
                continue
            print('No solution.')
        else:
            print('No solution.')

Из цифр двух натуральных чисел создать наименьшее возможное число, сохраняя порядок следования цифр

#cpp #алгоритм #олимпиада

Требуется написать программу, которая из цифр двух натуральных чисел создает наименьшее
возможное число, сохраняя при этом порядок следования цифр в этих числах.

Входной поток содержит два натуральных числа, записанных в двух строках. Числа больше
нуля и меньше 10^255.
(например, 125 и 34)

В единственную строку выходного потока нужно вывести наименьшее возможное число,
удовлетворяющее условию задачи. (например, 12345)

#include 
#include 
using namespace std;
int main()
{
  string a, b;
  cin >> a >> b;
  int x=0,y=0;
  while ((x

Ответы
Ответ 1

Проще всего, мне кажется, написать такую рекурсивную функцию:

bool compare(string a, int ia, string b, int ib)
{
    if (ia == a.length()) return true;
    if (ib == b.length()) return false;
    if (a[ia] == b[ib]) return compare(a, ia+1, b, ib+1);
    return a[ia] > b[ib];
}


И использовать ее так:

int main()
{
    string a = "12";
    string b = "21";
    int ia = 0;
    int ib = 0;
    while (ia < a.length() || ib < b.length())
    {
        if (compare(a, ia, b, ib))
            cout << b[ib++];
        else
            cout << a[ia++];
    }
    return 0;
}


https://ideone.com/PPtYY0

Максимальная глубина рекурсии при этом может быть 255, думаю, памяти хватит на всё
(есть ограничения на память?).


Ответ 2

Давайте разбираться.

a = 12, b = 21 


должно получиться 1212 - a[0]b[0]b[1]a[1], а у Вас получается 1221 - a[0]a[1]b[0]b[1].

В чем тут дело? Дело в принятии решения, по какому числу двигаться, когда цифры одинаковые.
Значит, волевое решение переходить к следующей цифре первого числа - как у Вас в коде
- нас не устраивает.

Чтобы принять правильное решение, надо заглянуть за эти одинаковые цифры и двигаться
по тому числу, у которого за этой одинаковой цифрой следует цифра меньшая, чем у другого
числа.

Но это еще не все...

Продолжаем. Интересный момент здесь состоит в том, что таких одинаковых цифр в числах
может идти больше одного подряд. Таким образом, нам нужно "заглядывать" за такие цепочки
одинаковых цифр в обоих числах.

И наконец, последний нюанс. Число может заканчиваться этой цепочкой одинаковых цифр.
Если оба числа ими заканчиваются, то все одинаковые цифры просто окажутся в конце результата.
Если только одно число заканчивается такой цепочкой, то надо смотреть на цифру, идущую
после цепочки в другом числе. Если эта цифра меньше одинаковых цифр, то надо выводить
цифры этого числа и не продвигаться в другом. И наоборот. 

Вам осталось перевести этот рассказ в код.



P.S. Не понимаю, что Вас смущает в размере чисел. Входные "числа" - это строки включающие
в себя до 255 десятичных цифр.

Чем заменить перебор?

#python #олимпиада #задачи

Недавно ездил на олимпиаду, и там была задача:


  На вход поступает 3 положительных натуральных числа, l r a Нужно найти сколько
пар чисел от l до r (включительно) можно составить, но сумма этих 2 чисел должна быть
кратна числу а.
  
  Например: на вход идут 3 числа 1 5 2. На выход 4. Так как можно составить 4 пары
[1, 3](1+3=4. 4 делится на 2 без остатка)[1,5][2,4][3,5]. 


Если решать эту задачу перебором, то при больших числах программа превышает лимит
времени. Видел как кто-то решил данную задачу математически, но постеснялся узнать
подробности.
    

Ответы

Ответ 1

Находим остатки от деления

lm = l % a
rm = r % a


И частные, округленные вверх для нижней границы и вниз для верхней

lq = (l + a - 1) // a
rq = r // a


Если rq > lq, то промежуток a*lq..a*rq-1 содержит все возможные остатки 0..a-1 в
количестве rq-lq раз каждый, и ещё имеются остатки в диапазонах lm..a-1 и 0..rm

Зная количество разных остатков, можно найти количество их попарных сумм, дающих 0 
 или a 

Для приведённого примера остаток 0 встречается 2 раза, остаток 1 - 3 раза. Количество
пар для остатков q и a-q будет N(q)*N(a-q) или N(q)*(N(q)-1)/2 в случае q=a-q или q=0,
т.е. здесь 2*1/2 + 3*2/2 = 4

Для промежутка 2..11 и a=3  ответ будет 3*2/2+3*4=15, a для a=4 2*1/2+3*2/2+3*2=10


Ответ 2

Исходя из того, что в ответе в парах одно число всегда меньше другого могу предложить
такой вариант.


Перебираете в цикле все значения i от l до r-l.
На каждом шаге:

2.1. находите такое минимально j, что i

Как развиваться в олимпиадном программировании? [закрыт]

#cpp #алгоритм #олимпиада

        
             
                
                    
                        
                            Closed. This question is opinion-based. It is not currently
accepting answers.
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            Want to improve this question? Update the question so
it can be answered with facts and citations by editing this post.
                        
                        Closed 1 месяц назад.
                                                                                
           
                
        
С недавнего времени меня очень зайтересовало олимпиадное программирование.  

Я учусь на первом курсе.
Основы языка и несложные алгоритмы я уже выучил.
Но вот как мне дальше развиваться не знаю.  

Что учить?
 Где учить?
Где можно поучаствовать?
 Какие-нибудь курсы?
 Какие-нибудь форумы? 



Буду очень признателен если кто-то поможет.
    

Ответы

Ответ 1

Выскажу своё мнение, так как много лет занимался олимпиадами и был участником чемпионата
мира по программированию (19-е место). Сейчас я программист-математик в довольно узкой
области, но владею этой областью как профессионала международного уровня. Не смог бы
стать таким профессионалом если бы вовремя не соскочил с иглы олимпиад.

Первое, что вы обязаны понимать: олимпиады - это игра. Она полезная, развивает некоторые
полезные навыки программирования и немаловажную способность к оптимизации. Когда я
закончил играть в эту игру лет 13 назад, я был удивлён тому, насколько лучше любых
других программистов я умею писать быстрый и эффективный код, который они даже представить
себе не могли (когда речь идёт о сложных задачах). Но главное в этой игре - ВОВРЕМЯ
УЙТИ. В один прекрасный момент вы должны понять, что наступила точка насыщения, после
которой вместо развития начинается деградация. Вы начинаете работать уже не на развития
своих навыков, а на оттачивание до совершенства именно соревновательных навыков, которые
на реальной работе не нужны и даже вредны.

Второе: олимпиадники не способны решать задачи, на которые нужно потратить больше
5 часов времени. Сколько я не преподавал, ни разу не попался человек, успешный в олимпиадах,
но при этом способный решать сложные научные задачи. Они привыкли, что можно написать
некий просто хороший код, эффективнее которого не смогут написать почти 100% обычных
программистов, и этого достаточно. Но нет, в научных расчётах попадаются такие задачи,
которые нужно пробивать месяцами упорного труда типа "написал - стёр - написал заново",
этот цикл может длиться десятки итераций и приходится применять те приёмы, которые
НЕ нужны в олимпиадах. Они этого не умеют. И, что ужасно, не могут себя заставить переучиться
с игры на кропотливый труд.

Третье: олимпиадники не способны писать грамотный промышленный код. Их можно этому
научить, но не всегда получается. Да, их код очень хорош в плане эффективности, они
чувствуют код как свою часть тела и знают как он будет работать. Многие из них даже
не делают ошибок в коде - он сразу запускается и работает правильно (так было у меня
лет 13 назад, код на домашних тренировках я писал в "блокноте" (без плюсов) и он сразу
компилировался и работал без ошибок, можно даже не проверять, но этот навык не нужен
и быстро теряется). Но одна беда: этот код не понятен другим людям, он не структурирован
так, чтобы в нём легко можно было разобраться, чтобы заменить одну часть кода другой,
его ВООБЩЕ невозможно поддерживать, можно только удалить и написать заново.

Четвёртое: из второго и третьего пунктов следует важная деталь - параллельно с олимпиадами
нужно работать над реальными задачами, имеющими практический смысл. Это могут быть
игры (обязательно по правилам разработки игр, а не самопал), могут быть научные расчёты
(обязательно по правилам той научной лаборатории, где работаете), могут быть промышленные
задачи (по ВСЕМ правилам промышленного кода и разработки программного обеспечения).
Только так вы не станете развитым лишь на один бок и не будете мучиться в своей профессиональной
карьере.

Пятое. Не впадайте в демонизм и не пытайтесь унижать своих собратьев, не прошедших
олимпиадную школу. Они никогда не напишут какой-нибудь алгоритм Форда-Фалкерсона так,
чтобы он работал быстро и правильно, у них в голове нет 70-100 алгоритмов, которые
вы можете быстро напечатать за несколько минут, они даже не слышали, что такое максимальный
поток, а вы знаете 15 алгоритмов его поиска наизусть. Это приводит к ощущению какой-то
возвышенности и важности. На самом деле вы должны понимать главное: в реальной жизни
вы - бесполезный мусор, если не умеете решать реальные задачи. Держите этот момент
в голове, если захотите кого-то унизить, кто не знает что такое динамическое программирование,
например.

Шестое. Развитие вас как олимпиадника должно быть постоянным, нельзя останавливаться.
Обязательно посещайте сборы программистов-олимпиадников, таких сейчас много, и когда
нет сборов, каждый день решайте задачи с разных серверов. В наше время были популярными
acm.timus.ru и acm.sgu.ru, сейчас я даже не знают, работают ли они, но сейчас полно
других вариантов: topcoder, codeforces (загуглите). Без сборов ваше обучения будет
очень слабым. Без каждодневных тренировок на серверах (пусть хоть полчасика в день) - тоже.

Седьмое. Как только поймёте, что дошли до точки насыщения и дальнейший рост в олимпиадах
приводит только к развитию навыков скорости и соревнования, а классические основы всех
алгоритмов вам уже известны, валите оттуда как можно скорее. Потому что с этого момента
начинается ваша деградация как человека практического. Сразу переключайтесь на реальную
работу, изучайте стандарты программирования, которые не смогли изучить в бытность олимпиадником
и беритесь за реальные задачи. Если вы проигнорировали совет делать это параллельно,
то придётся несколько лет переучиваться.

Восьмое. Игры затягивают в себя своим соревновательным духом, олимпиады насыщают
гордыню и подсаживают на чувстве значимости и особенности. Помните, что это иллюзия,
увод в сторону. Это хорошая школа для того чтобы научиться чувствовать код и компьютер,
изучить алгоритмы, но всё остальное (призы, места, победы и поражения, взгляды юных
девушек) - это туфта. Не ведитесь на неё, потом будет обидно.

Всё, желаю удачи, и да прибудет с вами здравый смысл :)


Ответ 2

Спортивная олимпиада поможет стать спортсменом. Математическая олимпиада поможет
стать математиком. Олимпиадное программирование - не поможет стать программистом. Хобби
- да. Как заменитель книг/игр - да. Как зарядка для ума - да. Как обучение программированию
- нет. Слишком разные подходы к коду. Слишком разные цели у олимпиады и production. 

Поэтому, если хотите развиваться, советую участвовать в открытых проектах на github,
gitlab, bitbucket, sourceforge и так далее. Таким образом вы и сообществу поможете,
и получите опыт работы в команде, и получите опыт участия в реальных проектах. Да к
тому же будет что показать работодателю если попросят примеры кода.


Ответ 3

Имхо

Если Вы пишиете, и хотите продолжать писать на плюсах, то лучшее, что я могу Вам
посоветовать,
и что максимально поспособствует Вашему развитию (сугубо мое мнение), это написание игр.

Начиная с легких консольных игр в которых будет присутствовать какая-то игровая логика,
 и двигаясь в сторону того, чтобы начинать изучать графические библиотеки, которые
смогут помочь
 Вам постепенно лучше понять, как можно работать не только с консольными приложениями 
под винду, линукс и пр., а и приложения, на которые лично Вам станет приятнее смотреть.

Как вариант, начните со змейки, крестиков ноликов, тенис и т.д. 

Лично я начинал с SFML, но вариантов также достаточно много, гугл поможет выбрать Ваш.

В процессе, вероятнее всего, станет интереснее как написать более правильно, то что
Вы делаете

и тогда можно будет копнуть глубже в паттерны. Книг много и каждому больше подходит
свое. 

Вместе с этим можно поднатаскать и навыки алгоритмов, но не стоит пытаться выучить
каждый,
 т.к. профита от этого мало и большая часть либо выучится на практике, пока Вы будете
искать хорошее решение своей проблемы, либо же вовсе Вам не понадобится, в силу того,
что использовать приходится в большинстве случаев именно готовые решения.


Главное - не стоит сильно закапываться в эти темы без практики, т.к. сырая теория
в программировании дает невероятно маленький выхлоп, при этом без практики забывается
все это очень быстро.


Курсы

Выбор на рынке крайне большой, но в целом, можете посмотреть бесплатные лекции на
той же Курсере курс от Яндекса, есть чему научится.

Полезным и интересным мне показался курс про многопоточность/сокеты на Степике, опять
таки бесплатный и с достаточном хорошим уровнем задач где-то после 20-30% курса.

Полезно

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

Элементарно можете начать с помощи одногруппникам с его лабой, которая почему-то
не работает. Пытаясь понять его код (если он не будет у всех копипастой) Вы будете
понемногу, но учится работать с чужим кодом. Т.к. в этой професии работать с чужим
кодом зачастую приходится ооочень часто, то такой навык будет очень сильно упрощать
Вашу первую и последущие.

А еще, никогда не ленитесь дебажить, если что-то не работает, и сразу непонятно,
что именно сломалось, в первую очередь попытайтесь изучить (если еще не изучили), а
после применить свои скиллы дебагинга и найти корень зла в Вашей программе.


П.С.

Слегка сумбурно, скорее всего еще подкорректирую и дополню, но в целом, желаю успеха
в Ваших начинаниях.


Ответ 4

Вопрос был задан про развитие в олимпиадном программировании, а ответы про то, насколько
это бесполезно и т.д... Отвечу по теме. Во-первых надо смотреть по уровню. Лично я
с командой в начале тренировался на этом сайте: https://acmp.ru/. Там много простых
задач, и можно потихоньку увеличивать сложность. Некоторых задач можно найти разборы
на ютубе и в интернете. Так же изучайте алгоритмы! На том же сайте есть тренировки
алгоритмов, и хороший сайт с алгоритмами: http://e-maxx.ru/algo/. Там есть и графы,
и со строками, и на комбинаторику, и всё, что душа пожелает. А участвовать можно на
соревнованиях тут: https://codeforces.com/problemset . Тут самые похожие задачи с теми,
что на олимпиаде. По началу можете в архивах находить те, что с самой простой сложностью.
Когда повысите уровень, можете пробывать участвовать в соревнованиях. И вообще, олимпиадное
программирование мало похоже на профессиональное, но оно даст вам хорошую базу, и знание
алгоритмов. И когда мы ездим на олимпиады, всегда есть возможность завести новые знакомства,
и куча it компаний предлагают работу у себя. Так что это точно опыт, который не помешает.
Так что не слушай некого, и занимайся тем, что нравится))


Ответ 5

Мой любимий сайт с задачами по программированию, очень хорошо можно прокачать свой
уровень и главное увидеть прогресс. 

Решая регулярно эти задачи можно подготовится к олимпиаде и не только, очень многое
вам пригодится в учебе и в будущей работе.

https://www.codewars.com/  

Еще классний момент, сайт исходя из вашей инфы найдет других пользователей, которые
учаться с вами в одном универе. Можно найти новых друзей.

Удачи!

Как отсортировать целые числа от 1 до n так, чтобы каждое число, начиная со второго, делило сумму чисел, стоящих левее него, нацело

Массив всегда начинается с 1 и заканчивается каким-нибудь n и числа идут по порядку

Наример, есть массив [1,2,3,4,5]
на выходе должно получится [3,1,4,2,5]

P.S. Имеется ограничение по времени - 1 секунда, а максимальная длина массива может быть до 10000 чисел (все числа идут по порядку и не повторяются)

Вот что пока выходит:

def check(a): #проверка подходит массив под условие или нет
    E = a[0]
    out = False
    for i in a[1:]:
        if(E%i==0):
            out = True
        if(E%i!=0):
            return False
        E=E+i
    return out


def sort(arr): #сортировка, тут у нас простой перебор комбинаций 
    n = len(arr) 
    for a in range(n):
        for b in range(n):
            if(b==a): continue 
            E = arr[b] #сумма чисел стоящих левее
            for c in range(n):
                if(c==b): continue
                if(E%arr[c]!=0): #если сумма чисел стоящих левее делится на текущее нацело то меняем текущее и предыдущее числа местами
                    temp = arr[c-1]
                    arr[c-1] = arr[c]
                    arr[c] = temp
                if(check(arr)): return arr #если массив проходим проверку возвращаем его

                E=E+arr[c]

    

Ответы

Ответ 1

Окончательный ответ. На С++, правда :)

#include 
#include 

using namespace std;


int main()
{
    int N;
    cin >> N;
    int m = N/2;
    for(int i = 1; i <= m; ++i)
        cout << (m+i) << " " << i << " ";

    if (N % 2) cout << (2*m+1);

    cout << endl;
}


Итак, если это N = 2m, то мы пишем числа 

m+1, 1, m+2, 2, ..., 2m, m


Если N = 2m+1, то 

m+1, 1, m+2, 2, ..., 2m, m, 2m+1


Всё.

Промежуточный ответ не вытираю, все ж таки пример перебора с возвратом - иногда годится. Да и о том, как прочищает мозги информация о том, что решение существует - тоже :)

Прошу обратить внимание - сами видите, что условие "до 10000, 1 секунда" автомато
наводит на совсем другие рассуждения :) Никогда не ленитесь выкладывать полное условие!


Ответ 2

Реализация алгоритма @Harry на Python:

def div_sort(array):
    m = N // 2
    result = []
    for i in range(0, m):
        result.append(array[m+i])
        result.append(array[i])
    if N % 2:
        result.append(array[N-1])
    return result


N = int(input('N = '))
print(div_sort(range(1, N+1)))


Если вместо перестановок элементов исходного массива генерировать результирующи
"на лету", то можно несколько упростить код:

def div_sort(N):
    m = N // 2
    result = []
    for i in range(1, m+1):
        result.append(m+i)
        result.append(i)
    if N % 2:
        result.append(N)
    return result


N = int(input('N = '))
print(div_sort(N))


Ответ 3

Как промежуточный ответ - явно есть какой-то точный алгоритм, который мне пока н
известен - есть метод перебора с возвратом. Полный перебор заткнется уже на втором десятке окончательно...

Мы просто перебираем варианты - подставляя поочередно первое число, в качестве второг
- только те, которые удовлетворяют условию, потом третьи для этих двух - так мы отсечем львиную долю негодных комбинаций... но все равно это будет слишком долго.

На python'е не умею, вот этот перебор с возвратом на C++:

#include 
#include 
#include 
#include 
#include 

using namespace std;

vector v;

bool test(vector&b, int n, vector&r)
{
    if (n == b.size())
    {
        for(auto i: r) cout << setw(3) << i; cout << endl;
        return true;
    }
    int sum = accumulate(r.begin(),r.end(),0);
    for(int j =0; j < b.size(); ++j)
    {
        if (b[j] == false)
        {
            if (sum % (j+1) != 0) continue;
            b[j] = true;
            r.push_back(j+1);
            bool res = test(b,n+1,r);
            r.pop_back();
            b[j] = false;
            if (res) return true;
        }
    }
    return false;
}


int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    for(int i = 0; i < N; ++i) v.push_back(false);

    vector r;
    test(v,0,r);

}


Тут действующий пример для 35. Как видите, для 10000 не вариант...

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

https://ideone.com/1c9Z5T


Ответ 4

Саааамый простой вариант — написать функцию, которая проверяет, является ли масси
отсортированным «как надо», и подать ей на вход все возможные перестановки этого массива (а их можно получить с помощью библиотечных функций, кстати). Это будет т.н. «переборный алгоритм».

Между прочим, не исключено, что подходящих перестановок и не будет, т.е. данный конкретный массив отсортировать «как надо» невозможно. (В обычной сортировке такого не бывает =)

Когда у вас в руках будет «какой-нибудь» корректный (проверьте это) алгоритм решени
задачи, имеет смысл подумать, а нужно ли его оптимизировать по числу операций. Может быть и нет ;)

Найти количество произведений пар чисел, которое кратно 10

Добрый день, задача по олимпиадному программированию из егэ этого года.
На вход подается целое положительное число N, не превышающее 10000, и последовательность из N целых положительных чисел, не превышающих 1000. Программа должна выводить число пар чисел, произведение чисел в которых кратно 10. При этом числа, произведение которых мы проверяем на кратность, не обязаны стоять рядом: пара может составляться и из чисел, взятых с разных концов последовательности. Пример входных данных:
4 2 5 7 4
Пример выходных данных:
2
Здесь подходят пары (2;5) и (5;4).
Решение перебором очевидно, но меня интересует решение эффективное по памяти и по времени. Под эффективностью по времени и по памяти в егэ подразумевают следующее:
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Очень интересно разобраться с этой задачей, буду благодарен за любую помощь. Язык программирования не важен, я хочу понять сам алгоритм.

Ответ

Заводим массив a на 10 элементов - по остаткам от деления на 10. Для каждого считанного числа x увеличиваем a[x%10] Считаем сумму:
Умножаем a[0] на сумму всех остальных элементов Умножаем a[5] на значения по чётным индексам кроме 0 т. к. произведение двух кратных 10 чисел тоже делится на 10, a[0] * (a[0]-1)
Бррр... А теперь упрощаем:
a0 - количество чисел, которые делятся на 10 b0 - количество чисел, которые не делятся на 10 a2 - количество чисел, которые делятся на 2, но не на 10 a5 - количество чисел, которые делятся на 5, но не на 10
Обращаю внимание, что в b0 входят a2 и a5
Ответ: a0*(a0-1+b0) + a2*a5
И ещё упрощаем: a0-1+b0 - это n-1
PS: В соответствии с требованиями, надо не держать массив в памяти, а обрабатывать по мере чтения.

Есть ли смысл заниматься олимпиадным программированием? [закрыт]

Работаю веб-разработчиком (junior). Недавно проходил курс, где попалась олимпиадная задача. Решить ее смог, но решение было далеко от идеала (сверил с решением автора). Ну и задачи подобного формата мне даются сложно.
Поможет ли мне олимпиадное программирование в развитии программистких скиллов, если выделю 6-7 часов в неделю?
Хипстерские советы типа "Лучше подключись к open source проекту на github" не актуальны.
Какую литературу можете посоветовать?

Ответ

Олимпиадное программирование даст вам хорошую эрудицию в алгоритмах и комбинаторике. В целом весьма полезные знания и умения. Задачи, требующие таких знаний, в реальной жизни бывают, но редко, зависит от наукоёмкости предметной области.
Сам по себе стиль в котором решаются олимпиадные задачи -- выполнить задачу хоть как, но уложиться в заданное время -- в обычном программировании чаще всего неприемлем: обычно тут нужно решить задачу с должным качеством, включая качество написанного кода, за приемлемое время. Причём важен навык оценки времени на разработку и способность уложиться в заявленное время. Понятность решения часто даже важнее производительности -- потому что если кроме вас в этом никто не разберётся, то всё равно перепишут "как проще".
Единственная ситуация в жизни, которая действительно похожа на олимпиадную -- это когда кто-то (чаще всего вы сами) накосячили на проде, и нужно срочно найти решение проблемы и пофиксить.
Успешным олимпиадникам на обычных проектах скучно -- мало мест где можно себя проявить, зато море рутины.