Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.78
Andryuxa
Заблокирован
16.12.2012, 21:10     Решение задачек (Всероссийской олимпиаде школьников по информатике) #1
Здравствуйте!!
Возможно кто нибудь из вас участвовал в муниципальном этапе Всероссийской олимпиаде школьников по информатике и решил все задачи.
Ну я не такой прошаренный поэтому решил только первые 2. Я бы хотел узнать решения остальных двух задач. Если кому то стало интересно я могу скинуть ему сами задачи
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2012, 21:10     Решение задачек (Всероссийской олимпиаде школьников по информатике)
Посмотрите здесь:

C++ Пара задачек по С
Олимпиадное задание на школьной олимпиаде C++
Задача по Олимпиаде C++
Подготовка к олимпиаде :) C++
C++ Структура со сведениями об олимпиаде по легкой атлетике
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Afflicted
Обитатель форума
199 / 182 / 8
Регистрация: 28.10.2012
Сообщений: 538
16.12.2012, 21:12     Решение задачек (Всероссийской олимпиаде школьников по информатике) #2
У нас тут не битва экстрасенсов. Где задачи?
sovaz1997
CEO SOVAZ Corp.
 Аватар для sovaz1997
379 / 225 / 2
Регистрация: 17.12.2011
Сообщений: 816
Записей в блоге: 1
16.12.2012, 21:12     Решение задачек (Всероссийской олимпиаде школьников по информатике) #3
Тебе на редкость повезло. Я участвовал. Решил только первую задачу.
P.S. Кстати, какой у тебя округ???
P.P.S. Ну, выкладывай задачки и наработки
Issues
429 / 364 / 37
Регистрация: 06.08.2012
Сообщений: 961
16.12.2012, 22:48     Решение задачек (Всероссийской олимпиаде школьников по информатике) #4
Andryuxa, кидай.
sovaz1997
CEO SOVAZ Corp.
 Аватар для sovaz1997
379 / 225 / 2
Регистрация: 17.12.2011
Сообщений: 816
Записей в блоге: 1
16.12.2012, 22:49     Решение задачек (Всероссийской олимпиаде школьников по информатике) #5
Кидай
Andryuxa
Заблокирован
17.12.2012, 15:05  [ТС]     Решение задачек (Всероссийской олимпиаде школьников по информатике) #6
Цитата Сообщение от 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
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
17.12.2012, 23:11     Решение задачек (Всероссийской олимпиаде школьников по информатике) #7
Цитата Сообщение от Andryuxa Посмотреть сообщение
Пример
0 1 2 3 4 5
0 6 7 8 9 2 /////// 10 ( // - это ограничение между входными и выходными)
Не понятно почему 10? Тут 5 + 6 = 11 и т.д.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
17.12.2012, 23:15     Решение задачек (Всероссийской олимпиаде школьников по информатике) #8
go,
Цитата Сообщение от Andryuxa Посмотреть сообщение
можно выложить из этих двух кубиков.
На втором кубике нет единицы.
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
17.12.2012, 23:32     Решение задачек (Всероссийской олимпиаде школьников по информатике) #9
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  [ТС]     Решение задачек (Всероссийской олимпиаде школьников по информатике) #10
Часть решения от go мне не понятна, но все равно спасибо! Буду разбирать
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
18.12.2012, 17:22     Решение задачек (Всероссийской олимпиаде школьников по информатике) #11
Цитата Сообщение от Andryuxa Посмотреть сообщение
Дана доска размера N на M. На доске есть плохие клетки, обычные клетки, и стоят два короля. По правилам игры короли по очереди ходят (так же как в шахматах на любые 8 соседних клеток, но не на соседние с другим королем), нельзя наступать на плохие клетки. Цель игры за минимальное количество ходов короли далжны поменяться позициями. За 1 ход считается именно ход одного короля. Первым ходит белый король.
На входа дается
Числа N M - размер доски
Далее в N строках по M символов дается доска, где символ * - плохая клетка, символ _ - обычная клетка, W -начальное положение белого короля, B - черного.
Программа должна найти минимальное количество ходов или вывести фразу Impossible если невозможно решить.
пока могу сказать только алгоритм ибо из за сессии пока некогда писать =с

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

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

что касается пробы т.е. проверяем наступаем ли мы на плохую клетку или нет если нет двигать короля.
что касается шага. двигая короля мы запоминаем пространство вокруг будущей клетки на предмет плохой обычной
покрываем это пространство плохими клетками видимыми толко для короля противника шагаем в эту клетку на предыдущую територию откатываем територию которая была запомнена на предыдущем ходе
PROFIT!!!!!!!!!
Но это действительно жесть, её отлаживать заколебаешься =)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.12.2012, 19:56     Решение задачек (Всероссийской олимпиаде школьников по информатике) #12
Цитата Сообщение от Andryuxa Посмотреть сообщение
Задача 4 (самый экшн как по мне)
Дана доска размера N на M.
максимальные значения N и M есть?
Afflicted
Обитатель форума
199 / 182 / 8
Регистрация: 28.10.2012
Сообщений: 538
18.12.2012, 19:57     Решение задачек (Всероссийской олимпиаде школьников по информатике) #13
1 <= N , M <= 8
Andryuxa
Заблокирован
18.12.2012, 20:10  [ТС]     Решение задачек (Всероссийской олимпиаде школьников по информатике) #14
Цитата Сообщение от MrGrig Посмотреть сообщение
Но это действительно жесть, её отлаживать заколебаешься =)
Если честно я пока не особо про в программировании, и поэтому мне до сих пор не понятно как реализовать именно движение королей в нужном направлении. Тупо перебирать все возможные варианты?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.12.2012, 20:35     Решение задачек (Всероссийской олимпиаде школьников по информатике) #15
Цитата Сообщение от 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  [ТС]     Решение задачек (Всероссийской олимпиаде школьников по информатике) #16
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Если такие ограничения, то решение не сложное. Даже при самом плохом раскладе: N=8, M=8, плохих клеток нет совсем получается вариантов расположения королей A и B (даже если им можно стоять рядом) всего: 64*63 (а с учетом того что для каждого варианта расположения королей может ходить или белый или черный король, то вариантов 64*63*2).
Для начала решения нужно в вектор занести значения возможных положений королей (с учетом плохих клеток и условием того что "очень близко" короли стоять не могут), в каждом из которых описываются: координаты белого короля, координаты черного короля, кто ходит, количество ходов до этого положения. Изначально количество ходов всем вариантам поставить 1000000000.
Варианту с начальным расположением двух королей и когда ходит белый король ставим значение 0.
Заносим этот вариант в очередь. Теперь алгоритм:
- берем очередной элемент из очереди смотрим куда может пойти из этого положения король (какой именно король ходит это видно из значения очередного элемента). Если есть вариант куда может пойти король не нарушая правил и для этого варианта "время" (количество ходов уменьшится, учитывая время очередного рассматриваемого элемента), то для этого нового варианта уменьшаем время и ищем его в очереди, если его нет в очереди то заносим.
Когда очередь кончится, то смотрим значение "времени" у варианта когда короли поменялись местами. Если время равно 1000000000, то выводим Impossible , иначе выводим "время" этого варианта.
Опять этот непонятный вектор! В принципе я уже начал писать решение с тупым перебором вариантов, немного похожим на твой. Но все равно спасибо!
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
18.12.2012, 22:24     Решение задачек (Всероссийской олимпиаде школьников по информатике) #17
Цитата Сообщение от Andryuxa Посмотреть сообщение
Опять этот непонятный вектор! В принципе я уже начал писать решение с тупым перебором вариантов, немного похожим на твой. Но все равно спасибо!
Исходник выложи плиз как напишешь =) хотябы чтобы она работала, про её трудоемкость даже если буде х^3 пофигу =)
Andryuxa
Заблокирован
19.12.2012, 00:10  [ТС]     Решение задачек (Всероссийской олимпиаде школьников по информатике) #18
Цитата Сообщение от MrGrig Посмотреть сообщение
Исходник выложи плиз как напишешь =) хотябы чтобы она работала, про её трудоемкость даже если буде х^3 пофигу =)
Конечно
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
19.12.2012, 06:51     Решение задачек (Всероссийской олимпиаде школьников по информатике) #19
Цитата Сообщение от Andryuxa Посмотреть сообщение
Опять этот непонятный вектор!
Вектор, это например: контейнер vector из STL. Можно обойтись и просто массивом. Каждый элемент вектора (массива) это 6 чисел: первые два координаты - белого коня, третье и четвертое число - координаты черного коня, пятое число - кто ходит, шестое число - время (количество ходов) достижения этого варианта.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.12.2012, 22:30     Решение задачек (Всероссийской олимпиаде школьников по информатике)
Еще ссылки по теме:

Подготовка к олимпиаде C++
C++ Сколько школьников списывали на экзамене, и выведите порядковые номера списывавших школьников

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Andryuxa
Заблокирован
19.12.2012, 22:30  [ТС]     Решение задачек (Всероссийской олимпиаде школьников по информатике) #20
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Вектор, это например: контейнер vector из STL. Можно обойтись и просто массивом. Каждый элемент вектора (массива) это 6 чисел: первые два координаты - белого коня, третье и четвертое число - координаты черного коня, пятое число - кто ходит, шестое число - время (количество ходов) достижения этого варианта.
Воу!! Классная штука спасибо! Кстати короля, а не коня

Добавлено через 6 часов 43 минуты
Не, че то у меня не особо получается. Помогайте, не могу прописать движение королей вверх и по диагонали!
Yandex
Объявления
19.12.2012, 22:30     Решение задачек (Всероссийской олимпиаде школьников по информатике)
Ответ Создать тему
Опции темы

Текущее время: 07:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru