Решение задачек (Всероссийской олимпиаде школьников по информатике)

@Andryuxa · 16.12.2012, 21:10. **Показов** 9748. **Ответов** 23

Студворк — интернет-сервис помощи студентам

Здравствуйте!!
Возможно кто нибудь из вас участвовал в муниципальном этапе Всероссийской олимпиаде школьников по информатике и решил все задачи.
Ну я не такой прошаренный поэтому решил только первые 2. Я бы хотел узнать решения остальных двух задач. Если кому то стало интересно я могу скинуть ему сами задачи

@Afflicted · 16.12.2012, 21:12

У нас тут не битва экстрасенсов. Где задачи?

@sovaz1997 · 16.12.2012, 21:12

Тебе на редкость повезло. Я участвовал. Решил только первую задачу.
P.S. Кстати, какой у тебя округ???
P.P.S. Ну, выкладывай задачки и наработки

@Issues · 16.12.2012, 22:48

Andryuxa, кидай.

@sovaz1997 · 16.12.2012, 22:49

Кидай

@Andryuxa · 17.12.2012, 15:05 **[ТС]**

Сообщение от Afflicted

У нас тут не битва экстрасенсов. Где задачи?

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

Добавлено через 56 секунд

Сообщение от sovaz1997

Тебе на редкость повезло. Я участвовал. Решил только первую задачу.
P.S. Кстати, какой у тебя округ???
P.P.S. Ну, выкладывай задачки и наработки

Я по Московской области могу скинуть решение второй задачи (оно большое и слишком банальное меян тут засмеют наверно)

Добавлено через 9 минут
В задачах много воды буду писать самое основное

Задача 1 (решено но скиньте свое решение если хотите)

Требуется написать программу которая по заданному году определяет какая была в этом году олимпиада (зимняя или летняя или и та и другая или вообще не было олимпиад).
Даны условия: промежуток времени от 1800 до 2012 включительно. В нашей эре Летние Игры первый раз прошли в 1896 году раз в 4 года (до этого игр не было) потом с 1924 года начались зимние игры причем они проходили в один и тот же год что и летние (так же раз в 4 года). Но в 1992 оба вида игр проводились вместе последний раз. И так в 1994 году только зимние, а в 1996 только летние и так раз в 4 года. Ткакже известно что в 1916, 1940, 1944 годах игр не было. Еще известно что в 1906 проводились внеочередные Игры.
Пример входных выходных данных
1896 summer
1803 nothing
1994 winter
1924 winter summer

Добавлено через 3 минуты
Задача 2 (решено)

Дано натуральное число N
Требуется написать программу, которая находит такое минимальное число M, произведение цифр которого равно N.
1<=N<=2*10^6
M>=10
Пример входных выходных данных

20 45
1 11
13 No solution

Добавлено через 7 минут
Задача 3 (самое интересное началось)

Есть два кубика. На каждом кубике на каждой грани написана цифра. Требуется написать программу которая выводит такое максимальное число К, что все числа от 1 до К включительно можно выложить из этих двух кубиков.
На вход дается цифры с граней кубико записаные через пробел. Причем если перевернуть 6 то можно получить 9 ( ну то есть если на кубике есть 6 то из нее можно получить и 9). На выход только одно число К. Если невозможно получить даже еденицу то вывести 0
Пример

0 1 2 3 4 5
0 6 7 8 9 2 /////// 10 ( // - это ограничение между входными и выходными)

Добавлено через 6 минут
Задача 4 (самый экшн как по мне)

Дана доска размера N на M. На доске есть плохие клетки, обычные клетки, и стоят два короля. По правилам игры короли по очереди ходят (так же как в шахматах на любые 8 соседних клеток, но не на соседние с другим королем), нельзя наступать на плохие клетки. Цель игры за минимальное количество ходов короли далжны поменяться позициями. За 1 ход считается именно ход одного короля. Первым ходит белый король.
На входа дается
Числа N M - размер доски
Далее в N строках по M символов дается доска, где символ * - плохая клетка, символ _ - обычная клетка, W -начальное положение белого короля, B - черного.
Программа должна найти минимальное количество ходов или вывести фразу Impossible если невозможно решить.

Пример

4 3
*_*
W_B
___
*_* ////////// 8

Плохой пример

2 3

W__
__B ////// Impossible

go · 17.12.2012, 23:11

Сообщение от Andryuxa

Пример
0 1 2 3 4 5
0 6 7 8 9 2 /////// 10 ( // - это ограничение между входными и выходными)

Не понятно почему 10? Тут 5 + 6 = 11 и т.д.

@soon · 17.12.2012, 23:15

go,

Сообщение от Andryuxa

можно выложить из этих двух кубиков.

На втором кубике нет единицы.

go · 17.12.2012, 23:32

soon, а т.е. не сумировать надо. Теперь понял задание.

Добавлено через 15 минут
3) Как-то так

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
   std::vector<short> cube1 = { 0, 1, 2, 3, 4, 5 };
   std::vector<short> cube2 = { 0, 6, 7, 8, 9, 2 };
   
   short answer = 1;
   bool  changes;
   
   do
   {
      changes = false;
      for (auto &i : cube1)
      {
         for (auto &j : cube2)
         {
            short ii = i == 9 ? 6 : i == 6 ? 9 : i;
            short jj = j == 9 ? 6 : j == 6 ? 9 : j;
            if ((i * 10 + j) == answer || (j * 10 + i) == answer || (ii * 10 + j) == answer || (j * 10 + ii) == answer
               || (i * 10 + jj) == answer || (jj * 10 + i) == answer)
            {
               ++answer; 
               changes = true;
               break;
            }
         }
         if (changes)
            break;
      }
   }
   while (changes);
   
   std::cout << --answer << std::endl;
   
   return 0;
}

http://liveworkspace.org/code/4uxJeE

@Andryuxa · 18.12.2012, 15:39 **[ТС]**

Часть решения от go мне не понятна, но все равно спасибо! Буду разбирать

@MrGrig · 18.12.2012, 17:22

Сообщение от Andryuxa

Дана доска размера N на M. На доске есть плохие клетки, обычные клетки, и стоят два короля. По правилам игры короли по очереди ходят (так же как в шахматах на любые 8 соседних клеток, но не на соседние с другим королем), нельзя наступать на плохие клетки. Цель игры за минимальное количество ходов короли далжны поменяться позициями. За 1 ход считается именно ход одного короля. Первым ходит белый король.
На входа дается
Числа N M - размер доски
Далее в N строках по M символов дается доска, где символ * - плохая клетка, символ _ - обычная клетка, W -начальное положение белого короля, B - черного.
Программа должна найти минимальное количество ходов или вывести фразу Impossible если невозможно решить.

пока могу сказать только алгоритм ибо из за сессии пока некогда писать =с

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

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

что касается пробы т.е. проверяем наступаем ли мы на плохую клетку или нет если нет двигать короля.
что касается шага. двигая короля мы запоминаем пространство вокруг будущей клетки на предмет плохой обычной
покрываем это пространство плохими клетками видимыми толко для короля противника шагаем в эту клетку на предыдущую територию откатываем територию которая была запомнена на предыдущем ходе
PROFIT!!!!!!!!!
Но это действительно жесть, её отлаживать заколебаешься =)

valeriikozlov · 18.12.2012, 19:56

Сообщение от Andryuxa

Задача 4 (самый экшн как по мне)
Дана доска размера N на M.

максимальные значения N и M есть?

@Afflicted · 18.12.2012, 19:57

1 <= N , M <= 8

@Andryuxa · 18.12.2012, 20:10 **[ТС]**

Сообщение от MrGrig

Но это действительно жесть, её отлаживать заколебаешься =)

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

valeriikozlov · 18.12.2012, 20:35

Сообщение от Afflicted

1 <= N , M <= 8

Если такие ограничения, то решение не сложное. Даже при самом плохом раскладе: N=8, M=8, плохих клеток нет совсем получается вариантов расположения королей A и B (даже если им можно стоять рядом) всего: 64*63 (а с учетом того что для каждого варианта расположения королей может ходить или белый или черный король, то вариантов 64*63*2).
Для начала решения нужно в вектор занести значения возможных положений королей (с учетом плохих клеток и условием того что "очень близко" короли стоять не могут), в каждом из которых описываются: координаты белого короля, координаты черного короля, кто ходит, количество ходов до этого положения. Изначально количество ходов всем вариантам поставить 1000000000.
Варианту с начальным расположением двух королей и когда ходит белый король ставим значение 0.
Заносим этот вариант в очередь. Теперь алгоритм:
- берем очередной элемент из очереди смотрим куда может пойти из этого положения король (какой именно король ходит это видно из значения очередного элемента). Если есть вариант куда может пойти король не нарушая правил и для этого варианта "время" (количество ходов уменьшится, учитывая время очередного рассматриваемого элемента), то для этого нового варианта уменьшаем время и ищем его в очереди, если его нет в очереди то заносим.
Когда очередь кончится, то смотрим значение "времени" у варианта когда короли поменялись местами. Если время равно 1000000000, то выводим Impossible , иначе выводим "время" этого варианта.

@Andryuxa · 18.12.2012, 21:54 **[ТС]**

Сообщение от valeriikozlov

Если такие ограничения, то решение не сложное. Даже при самом плохом раскладе: N=8, M=8, плохих клеток нет совсем получается вариантов расположения королей A и B (даже если им можно стоять рядом) всего: 64*63 (а с учетом того что для каждого варианта расположения королей может ходить или белый или черный король, то вариантов 64*63*2).
Для начала решения нужно в вектор занести значения возможных положений королей (с учетом плохих клеток и условием того что "очень близко" короли стоять не могут), в каждом из которых описываются: координаты белого короля, координаты черного короля, кто ходит, количество ходов до этого положения. Изначально количество ходов всем вариантам поставить 1000000000.
Варианту с начальным расположением двух королей и когда ходит белый король ставим значение 0.
Заносим этот вариант в очередь. Теперь алгоритм:
- берем очередной элемент из очереди смотрим куда может пойти из этого положения король (какой именно король ходит это видно из значения очередного элемента). Если есть вариант куда может пойти король не нарушая правил и для этого варианта "время" (количество ходов уменьшится, учитывая время очередного рассматриваемого элемента), то для этого нового варианта уменьшаем время и ищем его в очереди, если его нет в очереди то заносим.
Когда очередь кончится, то смотрим значение "времени" у варианта когда короли поменялись местами. Если время равно 1000000000, то выводим Impossible , иначе выводим "время" этого варианта.

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

@MrGrig · 18.12.2012, 22:24

Сообщение от Andryuxa

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

Исходник выложи плиз как напишешь =) хотябы чтобы она работала, про её трудоемкость даже если буде х^3 пофигу =)

@Andryuxa · 19.12.2012, 00:10 **[ТС]**

Сообщение от MrGrig

Исходник выложи плиз как напишешь =) хотябы чтобы она работала, про её трудоемкость даже если буде х^3 пофигу =)

Конечно

valeriikozlov · 19.12.2012, 06:51

Сообщение от Andryuxa

Опять этот непонятный вектор!

Вектор, это например: контейнер vector из STL. Можно обойтись и просто массивом. Каждый элемент вектора (массива) это 6 чисел: первые два координаты - белого коня, третье и четвертое число - координаты черного коня, пятое число - кто ходит, шестое число - время (количество ходов) достижения этого варианта.

@Andryuxa · 19.12.2012, 22:30 **[ТС]**

Сообщение от valeriikozlov

Вектор, это например: контейнер vector из STL. Можно обойтись и просто массивом. Каждый элемент вектора (массива) это 6 чисел: первые два координаты - белого коня, третье и четвертое число - координаты черного коня, пятое число - кто ходит, шестое число - время (количество ходов) достижения этого варианта.

Воу!! Классная штука спасибо! Кстати короля, а не коня

Добавлено через 6 часов 43 минуты
Не, че то у меня не особо получается. Помогайте, не могу прописать движение королей вверх и по диагонали!

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

@Andryuxa Заблокирован

	Решение задачек (Всероссийской олимпиаде школьников по информатике) 16.12.2012, 21:10. Показов 9748. Ответов 23 Метки нет (Все метки) Здравствуйте!! Возможно кто нибудь из вас участвовал в муниципальном этапе Всероссийской олимпиаде школьников по информатике и решил все задачи. Ну я не такой прошаренный поэтому решил только первые 2. Я бы хотел узнать решения остальных двух задач. Если кому то стало интересно я могу скинуть ему сами задачи 0

@Afflicted Обитатель форума 201 / 184 / 54 Регистрация: 28.10.2012 Сообщений: 543
	16.12.2012, 21:12
	У нас тут не битва экстрасенсов. Где задачи? 0

@sovaz1997 CEO SOVAZ Corp. 386 / 232 / 51 Регистрация: 17.12.2011 Сообщений: 822 Записей в блоге: 1
	16.12.2012, 21:12
	Тебе на редкость повезло. Я участвовал. Решил только первую задачу. P.S. Кстати, какой у тебя округ??? P.P.S. Ну, выкладывай задачки и наработки 0

@Issues 433 / 368 / 149 Регистрация: 06.08.2012 Сообщений: 961
	16.12.2012, 22:48
	Andryuxa, кидай. 0

@sovaz1997 CEO SOVAZ Corp. 386 / 232 / 51 Регистрация: 17.12.2011 Сообщений: 822 Записей в блоге: 1
	16.12.2012, 22:49
	Кидай 0

@Andryuxa Заблокирован
	18.12.2012, 15:39 [ТС]
	Часть решения от go мне не понятна, но все равно спасибо! Буду разбирать 0

@Afflicted Обитатель форума 201 / 184 / 54 Регистрация: 28.10.2012 Сообщений: 543
	18.12.2012, 19:57
	1 <= N , M <= 8 0