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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.78
Andryuxa
Заблокирован
#1

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

16.12.2012, 21:10. Просмотров 2366. Ответов 23
Метки нет (Все метки)

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

Сколько школьников списывали на экзамене, и выведите порядковые номера списывавших школьников - C++
Здравствуйте, помогите пожалуйста. Группа из N школьников сдавала ЕГЭ по информатике. Каждый школьник получил некоторый результат от 0 до...

Решение задачи по информатике - C++
Доброго времени суток! Суть задачи проста: дано кол-во спичек 1<=N<=100, них нужно составить минимальное и максимальное число. Спички...

Использование C# во всероссийской олимпиаде школьников по программированию - C#
Здравствуйте!.. Хотел бы обратиться к КиберФорумчанам, имеющим опыт участия во всероссийских олимпиадах по программированию.. Вопрос вот в...

На олимпиаде по информатике участвовало пятеро учеников - Prolog
Помогите пожалуйста решить... На олимпиаде по информатике участвовало пятеро учеников: Вася (В), Гриша (Г), Иван (И), Саша (С) и...

Ищу 11 класс для участие в командной уральской олимпиаде для школьников - Pascal ABC
Нужен 1 человек в команду. пишите

На олимпиаде по информатике участвовали пятеро Андрей (А), Коля (К), Виктор (В), Егор (Е), Степан (С) - Prolog
Всем привет) На олимпиаде по информатике участвовали пятеро Андрей (А), Коля (К), Виктор (В), Егор (Е), Степан (С). Об итогах...

23
Afflicted
Обитатель форума
199 / 182 / 8
Регистрация: 28.10.2012
Сообщений: 543
16.12.2012, 21:12 #2
У нас тут не битва экстрасенсов. Где задачи?
0
sovaz1997
CEO SOVAZ Corp.
380 / 226 / 2
Регистрация: 17.12.2011
Сообщений: 819
Записей в блоге: 1
Завершенные тесты: 1
16.12.2012, 21:12 #3
Тебе на редкость повезло. Я участвовал. Решил только первую задачу.
P.S. Кстати, какой у тебя округ???
P.P.S. Ну, выкладывай задачки и наработки
0
Issues
430 / 365 / 37
Регистрация: 06.08.2012
Сообщений: 961
16.12.2012, 22:48 #4
Andryuxa, кидай.
0
sovaz1997
CEO SOVAZ Corp.
380 / 226 / 2
Регистрация: 17.12.2011
Сообщений: 819
Записей в блоге: 1
Завершенные тесты: 1
16.12.2012, 22:49 #5
Кидай
0
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
0
go
Эксперт С++
3586 / 1366 / 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 и т.д.
0
soon
2541 / 1306 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
17.12.2012, 23:15 #8
go,
Цитата Сообщение от Andryuxa Посмотреть сообщение
можно выложить из этих двух кубиков.
На втором кубике нет единицы.
0
go
Эксперт С++
3586 / 1366 / 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
1
Andryuxa
Заблокирован
18.12.2012, 15:39  [ТС] #10
Часть решения от go мне не понятна, но все равно спасибо! Буду разбирать
0
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!!!!!!!!!
Но это действительно жесть, её отлаживать заколебаешься =)
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.12.2012, 19:56 #12
Цитата Сообщение от Andryuxa Посмотреть сообщение
Задача 4 (самый экшн как по мне)
Дана доска размера N на M.
максимальные значения N и M есть?
0
Afflicted
Обитатель форума
199 / 182 / 8
Регистрация: 28.10.2012
Сообщений: 543
18.12.2012, 19:57 #13
1 <= N , M <= 8
0
Andryuxa
Заблокирован
18.12.2012, 20:10  [ТС] #14
Цитата Сообщение от MrGrig Посмотреть сообщение
Но это действительно жесть, её отлаживать заколебаешься =)
Если честно я пока не особо про в программировании, и поэтому мне до сих пор не понятно как реализовать именно движение королей в нужном направлении. Тупо перебирать все возможные варианты?
0
valeriikozlov
Эксперт С++
4670 / 2496 / 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 , иначе выводим "время" этого варианта.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.12.2012, 20:35
Привет! Вот еще темы с ответами:

Распечатать анкетные данные студентов, набравших в олимпиаде по информатике не менее 30 баллов - Pascal ABC
Записи, распечатать анкетные данные студентов, участвовавших в олимпиаде по информатике и заработавших не менее 30 баллов. определить, кто...

Распечатать анкетные данные учеников,участвовавших в олимпиаде по информатике и заработавших не менее 30баллов - C#
Распечатать анкетные данные учеников, участвовавших в олимпиаде по информатике и заработавших не менее 30 баллов.

Распечатать анкетные данные студентов, участвующих в олимпиаде по информатике и получивших не менее 30 баллов - Turbo Pascal
152. Распечатать анкетные данные студентов, участвующих в олимпиаде по информатике и получивших не менее 30 баллов.

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


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
18.12.2012, 20:35
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru