Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Aleksey19718
3 / 3 / 1
Регистрация: 20.12.2015
Сообщений: 47
#1

Олимпиадная задача. Алгоритм - C++

24.03.2017, 23:30. Просмотров 237. Ответов 7
Метки нет (Все метки)

Всем привет. Помогите понять алгоритм решения задачи.
Олимпиадная задача. Алгоритм

1. Как найти перекресток, с которого начинается движение робота (и принципиально ли это вообще)
2. Если нашел начало пути, по какому алгоритму идти дальше? Стоя на перекрестке, смотреть, с какой стороны наибольшее кол-во монет? или как?

Код не прошу, подскажите с алгоритмом (на словах). Пожалуйста))
http://www.cyberforum.ru/cpp-beginners/thread716035.html
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.03.2017, 23:30
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Олимпиадная задача. Алгоритм (C++):

C++. Олимпиадная задача
Здравствуйте! Код не проходит какой-то тест, может алгоритм не правильный. И...

Олимпиадная задача
Алфавит мурмарианской системы счисления включает три цифры - 1, 2 и 3. Одна...

Олимпиадная задача
Вот наткнулся сегодня на такую задачу: Всем известно, что в позапрошлом веке...

Олимпиадная задача
Был в прошлом году на олимпиаде по программированию и там была такая задача:...

Олимпиадная задача
#include <cstdio> #include <cstdlib> #include <iostream> using namespace...

7
Hekk
0 / 0 / 4
Регистрация: 19.09.2016
Сообщений: 32
25.03.2017, 00:20 #2
1. нет
2. Думаю полчучится через это: нахождение расстояния от источника до всех вершин - метод Форда-Беллмана (гугл в помощь). Для неориентированного взвешенного графа. Но точного ответа алгоритм не даст, надо будет слегка модифицировать для этой задач.
0
DUMP
73 / 47 / 26
Регистрация: 22.02.2015
Сообщений: 306
25.03.2017, 00:28 #3
Hekk, здесь не нужно искать минимальное расстояние до вершины. Нам нужно пройтись по графу, собрав как можно больше монет. Входные данные очень малы, можно рекурсивно выполнять задание из каждой вершины.
0
MrGluck
Модератор
Эксперт CЭксперт С++
8020 / 4863 / 1424
Регистрация: 29.11.2010
Сообщений: 13,239
25.03.2017, 00:48 #4
Цитата Сообщение от Aleksey19718 Посмотреть сообщение
Код не прошу, подскажите с алгоритмом (на словах). Пожалуйста))
Рекурсивно перебрать все варианты. При проходе помечать переход как "пройденный".
0
DUMP
73 / 47 / 26
Регистрация: 22.02.2015
Сообщений: 306
25.03.2017, 01:19 #5
Цитата Сообщение от MrGluck Посмотреть сообщение
При проходе помечать переход как "пройденный".
Не все так просто, при переходе мы отнимаем половину монет и можем вернуться назад, если монеты ещё есть.
0
Aleksey19718
3 / 3 / 1
Регистрация: 20.12.2015
Сообщений: 47
25.03.2017, 01:24  [ТС] #6
Так что можете посоветовать?
0
MrGluck
Модератор
Эксперт CЭксперт С++
8020 / 4863 / 1424
Регистрация: 29.11.2010
Сообщений: 13,239
25.03.2017, 10:47 #7
Цитата Сообщение от DUMP Посмотреть сообщение
Не все так просто, при переходе мы отнимаем половину монет и можем вернуться назад, если монеты ещё есть.
Ну сделать состояние не bool, а int. Разница не велика.
0
elch10
40 / 21 / 4
Регистрация: 27.04.2015
Сообщений: 174
Завершенные тесты: 2
27.03.2017, 19:58 #8
Лучший ответ Сообщение было отмечено Aleksey19718 как решение

Решение

Aleksey19718, Вот здесь решение https://neerc.ifmo.ru/school/archive...4-analysis.pdf
А тут есть даже решения жюри и участников(пролистай до материалы олимпиады):https://neerc.ifmo.ru/school/archive/2014-2015.html#team-rus
1
27.03.2017, 19:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.03.2017, 19:58
Привет! Вот еще темы с решениями:

Олимпиадная задача
Дошел до этой олимпиадной задачи и впал в ступор. Нагуглил, что можно решить с...

Олимпиадная задача
Есть такая задачка: В ряд выписаны числа, состоящие только из цифр 1, 3, 7: 1,...

Олимпиадная задача. Деревни
Всем привет.. задача такая: Деревни В тридесятом государстве есть N...

Олимпиадная задача на перевертыши
Жетоны По случаю организации сотого чемпионата по спортивной рыбалке,...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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