|
|
|
|
|
|
|
Вернуться
| 1 SKYDOS [Vladimir SU] [skydos.blogspot.com], 21 августа 2010 г. 18:23:02 | |
Привет Шуршилов Артём Александрович
Спасибоа за разборы!
Если тебя не затруднит - пиши разборы мне на мыло acskydos@gmail.com и я от твоего имени их буду публиковать, не забудь так же тект самой задачи скинуть.
Задачи разбираем - любые!
Поэтому разборы - это некая тренировка умения объяснять самое решение и алгоритм.
|
|
|
| 2 Шуршилов Артём Александрович, 21 августа 2010 г. 13:45:23 | |
|
Просто первая задачка которая попалась с сайта...или вам надо разбор задач по сложнее?
|
|
|
| 3 Шуршилов Артём Александрович, 21 августа 2010 г. 13:40:48 | |
Задачка на теорию графов,то что заданный нам граф неориентированный можно понять из условия(т.к. не сказанно о том,что по одной дороге можно проехать только в одну сторону),так же очевидно,что в каждом городе нужно заправляться.По данным нам входным данным составим матрицу смежности.
Для начала создадим двумерный массив A[101][101] и заполним его элементы каким-нибудь большим числом например 100000 (т.е. первоначально расстояние между городами большое число 100000-эквивалент бесконечности в нашем случае),а диагональным элементам A [i][i] присвоим значение 0(т.е. расстояние между одним и тем же городом равно 0)
Далее считаем цену на бензин в массив d,затем считывая по два числа (которые говорят о существовании пути между двумя городами) мы заполняем массив A[101][101] взяв соответственно цену на бензин из массива d:
I >> m;
for(i=0;i<m;i++){
I >> c >> k;
a[c-1][k-1]=d[c-1];//От города c-1 до k-1
a[k-1][c-1]=d[k-1];}//От k-1 до c-1
Далее С помощью алгоритма Флойда найдём минимальные цены за проезд между любыми 2 городами:
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++){
c=a[i][k]+a[k][j];
if(a[i][j]>c)
a[i][j]=c;}
Затем нам останется просто вывести минимальную цену от города 1 до n:
if(a[0][n-1]!=100000)
O<<a[0][n-1];
else O<<-1;
|
|
|
| 4 Шуршилов Артём Александрович, 21 августа 2010 г. 13:39:54 | |
Разбор задачи 133.(Первый раз пишу разбор,так что имейти ввиду)
В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее количество денег.
Входные данные
Во входном файле INPUT.TXT записано сначала число N (1<=N<=100), затем идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Далее идет число M - количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами - номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число - суммарную стоимость маршрута или -1, если добраться невозможно.
Пример:
INPUT.TXT OUTPUT.TXT
4 3
1 10 2 15
4
1 2
1 3
4 2
4 3
Задачка на теорию графов,то что заданный нам граф неориентированный можно понять из условия(т.к. не сказанно о том,что по одной дороге можно проехать только в одну сторону),так же очевидно,что в каждом городе нужно заправляться.По данным нам входным данным составим матрицу смежности.
Для начала создадим двумерный массив A[101][101] и заполним его элементы каким-нибудь большим числом например 100000 (т.е. первоначально расстояние между городами большое число 100000-эквивалент бесконечности в нашем случае),а диагональным элементам A [i][i] присвоим значение 0(т.е. расстояние между одним и тем же городом равно 0)
Далее считаем цену на бензин в массив d,затем считывая по два числа (которые говорят о существовании пути между двумя городами) мы заполняем массив A[101][101] взяв соответственно цену на бензин из массива d:
I >> m;
for(i=0;i<m;i++){
I >> c >> k;
a[c-1][k-1
|
|
|
| 5 Яхнев Иван Николаевич, 13 августа 2010 г. 17:40:00 | |
|
добавь разбор задач с регионального и заключительного этапа всероссийской олимпиады по информатике
|
|
|
| 6 Маскин М.В. [skydos.blogspot.com], 12 августа 2010 г. 12:31:13 | |
Ну лично я на плюсах вообще не пишу, да и вроде Андрей не очень то их использует)
Может ты напишешь какой разбор?=) Были бы благодарны
|
|
|
| 7 Шуршилов Артём Александрович, 12 августа 2010 г. 10:51:58 | |
|
Ну чё какие задачи разбирать будем на С++???=)))
|
|
|
| 8 SKYDOS [Vladimir SU] [skydos.blogspot.com], 02 августа 2010 г. 17:47:47 | |
Ниненко А. Е
ничего лучше блогспот не предоставляет.
|
|
|
| 9 Ниненко А. Е, 02 августа 2010 г. 16:15:10 | |
|
дизайн плохой, читать не очень удобно и к тому же ввергает в уныние
|
|
|
| 10 SKYDOS [Vladimir SU] [skydos.blogspot.com], 25 июля 2010 г. 15:29:44 | |
Бомж Вася
Понимаю, но блогспот не предоставляет более простые фоновые изображения, а свои загрузить не могу - нет такой опции.
|
|
|
| 11 Бомж Вася, 25 июля 2010 г. 15:25:26 | |
|
Да он просто и не отвлекающ, но кляксы коорые накладываеются на текст в некоторых местах не ок
|
|
|
| 12 SKYDOS [Vladimir SU] [skydos.blogspot.com], 25 июля 2010 г. 15:25:04 | |
Гостев Дмитрий Владиленович
Я буду только ЗА, если кто-то предоставит и решения на других языках - буду добавлять и их соответственно подписывая чьё это решение.
Я просто паскаль и ++ недолюбливаю, поэтому и юзаю шарп или яву.
|
|
|
| 13 Гостев Дмитрий Владиленович, 25 июля 2010 г. 13:55:58 | |
|
Блок конечно классный))) Но плохо что разборы на JAVA или С#,не все их знают, я думаю былобы не плохо что пользователю предлаглось выбор языка, например С++, Pascal, Java, C#, думаю и питончик можно)))
|
|
|
| 14 SKYDOS [Vladimir SU] [skydos.blogspot.com], 24 июля 2010 г. 18:03:41 | |
Бомж Вася
Убрал всё лишнее.
Фон другой не могу найти, это самый простой и неотвлекающий.
|
|
|
| 15 Бомж Вася, 24 июля 2010 г. 15:33:09 | |
|
Любой который не будет мишать читать будит лучше
|
|
|
| 16 SKYDOS [Vladimir SU] [skydos.blogspot.com], 23 июля 2010 г. 22:31:35 | |
Бомж Вася
Если есть более конструктивные идеи по дизайну - слушаю. Изменить не проблема, я не привязан к какому-то определенному.
|
|
|
| 17 Бомж Вася, 23 июля 2010 г. 22:26:11 | |
|
Он купльтурно намекнул что скин гавно :-)
|
|
|
| 18 SKYDOS [Vladimir SU] [skydos.blogspot.com], 22 июля 2010 г. 22:16:54 | |
Пересадин Илья
Что за грязь?) если если предложения по дизайну - делись)
мы открыты всему новому)
|
|
|
| 19 Пересадин Илья, 22 июля 2010 г. 21:35:32 | |
|
классный блог:) только не очень приятно, что "грязь" на мониторе, мешает ((
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
