Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
3 / 3 / 1
Регистрация: 11.11.2009
Сообщений: 132
1

Вывести единственное число: минимальную возможную стоимость маршрута черепашки

29.04.2014, 22:44. Показов 2292. Ответов 12
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте!
Прошу помощи, т.к. не могу адекватно реализовать программу. Задача из серии олимпиадных, с сайта еолимп.

Постановка задачи:
Входные данные


В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 1000 - размеры таблицы. Далее идёт N строк, каждая из которых содержит M чисел, разделённых пробелами - описание таблицы с указанием для каждой клетки содержания кислоты на ней (в миллилитрах).

Выходные данные


Программа должна вывести единственное число: минимальную возможную стоимость маршрута черепашки.

Пример входных данных:
3 4
5 9 4 3
3 1 6 9
8 6 8 12
На выход получаем 35.

Всё реализовано, считает правильно, но не укладываюсь в память.
Скорее всего проблема хранения очень большого массива.

Вот код:
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace cherepaha
{
    class Program
    {
        static void Main()
        {
            string s = Console.ReadLine();
            string[] s2 = s.Split(new Char[] { ' ' });
            int[,] a = new int[Int32.Parse(s2[0]), Int32.Parse(s2[1])];
 
            for (int i = 0; i < a.GetLength(0); i++)
            {
 
                s = Console.ReadLine();
                s2 = s.Split(new Char[] { ' ' });
                for (int j = 0; j < a.GetLength(1); j++)
                    a[i, j] = Int32.Parse(s2[j]);
 
            }
            return 0;
            int min;
            for (int i = 0; i < a.GetLength(0); i++)
                for (int j = 0; j < a.GetLength(1); j++)
                {
                    if (i == 0 && j == 0)
                        min = 0;
                    else
                    {
                        if (i == 0 && j != 0)
                            min = a[i, j - 1];
                        else
                        {
                            if (i != 0 && j == 0)
                                min = a[i - 1, j];
                            else
                                min = Math.Min(a[i - 1, j], a[i, j - 1]);
                        }
                    }
 
                    a[i, j] += min;
 
                }
            Console.WriteLine(a[a.GetLength(0) - 1, a.GetLength(1) - 1]);
 
 
          
        }
    }
}
Заранее спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
29.04.2014, 22:44
Ответы с готовыми решениями:

Написать программу, которая подсчитает минимальную возможную стоимость оставленных предметов
Впервые в жизни Петя летит на международную олимпиаду по программированию. Петя так волновался, что...

Найти минимальную и максимальную возможную суммарную стоимость всех заготовок в ящике
в ящике лежат заготовки 4 видов.вес заготовки каждого вида составляет 4,8,2,5кг.стоимость заготовки...

Вывести единственное целое число
В первый день спортсмен пробежал x километров, а затем он каждый день увеличивал пробег на 70% от...

Вывести единственное число - суммц заданных чисел a+b
Привет Всем! Я не программист и знаю паскаль только на нижнем уровне самые простые задачи. Вот,...

12
Master of Orion
Эксперт .NET
6100 / 4956 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
29.04.2014, 22:55 2
NARTZISS, используйте тип byte или short, если возможно. в 4-16 раз сократит объем памяти.
0
2152 / 1289 / 516
Регистрация: 04.03.2014
Сообщений: 4,092
29.04.2014, 23:28 3
Цитата Сообщение от Psilon Посмотреть сообщение
используйте тип byte или short,
да я всегда для этого сайта минимизировал свой код используя минимально возможные типы по памяти (в циклах в том числе)

Добавлено через 4 минуты
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
40
41
42
43
44
45
46
47
string s = Console.ReadLine();
            string[] s2 = s.Split(new Char[] { ' ' });
            short [,] a = new int[Int16.Parse(s2[0]), Int16.Parse(s2[1])];
 
            short i;
            short l=a.GetLength(0)
            for (i= 0; i < l); i++)
            {
 
                s = Console.ReadLine();
                s2 = s.Split(new Char[] { ' ' });
                for (int j = 0; j < a.GetLength(1); j++)
                    a[i, j] = Int16.Parse(s2[j]);
 
            }
            return 0;
            short min;
            short j;
            short l2=a.GetLength(1);
            for ( i = 0; i < l; i++)
                for (j = 0; j < l2; j++)
                {
                    if (i == 0 && j == 0)
                        min = 0;
                    else
                    {
                        if (i == 0 && j != 0)
                            min = a[i, j - 1];
                        else
                        {
                            if (i != 0 && j == 0)
                                min = a[i - 1, j];
                            else
                                min = Math.Min(a[i - 1, j], a[i, j - 1]);
                        }
                    }
 
                    a[i, j] += min;
 
                }
            Console.WriteLine(a[a.GetLength(0) - 1, a.GetLength(1) - 1]);
 
 
          
        }
    }
}
Добавлено через 26 секунд
писал без редактора проверь
0
3 / 3 / 1
Регистрация: 11.11.2009
Сообщений: 132
29.04.2014, 23:55  [ТС] 4
все поправил, только вот ругается, не могу исправить.
C#
1
short [,] a = new int[Int16.Parse(s2[0]), Int16.Parse(s2[1])];
0
2152 / 1289 / 516
Регистрация: 04.03.2014
Сообщений: 4,092
30.04.2014, 00:00 5
C#
1
short [,] a = new short[Int16.Parse(s2[0]), Int16.Parse(s2[1])];
1
3 / 3 / 1
Регистрация: 11.11.2009
Сообщений: 132
30.04.2014, 00:06  [ТС] 6
Спасибо, но не засчитано(
тот же лимит памяти.
Может быть не стоит хранить весь массив?
0
2152 / 1289 / 516
Регистрация: 04.03.2014
Сообщений: 4,092
30.04.2014, 00:19 7
точно лимит памяти ? не времени?
NARTZISS, попробуй поиграться с принудительной очисткой мусора
0
3 / 3 / 1
Регистрация: 11.11.2009
Сообщений: 132
30.04.2014, 00:26  [ТС] 8
Максимальное время выполнения: 0.015 секунды из 0.5 секунды, 3%
Лимит памяти: 8636 KB из 8192 KB, 105.4%

Что за принудительная очистка мусора?
0
2152 / 1289 / 516
Регистрация: 04.03.2014
Сообщений: 4,092
30.04.2014, 00:37 9
C#
1
2
GC.Collect(0, GCCollectionMode.Forced);
            GC.WaitForPendingFinalizers();
Добавлено через 46 секунд
возможно поочищает неиспользуемый строки
после этих операций
C#
1
2
s = Console.ReadLine();
                s2 = s.Split(new Char[] { ' ' });
0
3 / 3 / 1
Регистрация: 11.11.2009
Сообщений: 132
30.04.2014, 00:45  [ТС] 10
Максимальное время выполнения: 0.031 секунды из 0.5 секунды, 6.2%
Лимит памяти: 10472 KB из 8192 KB, 127.8%

После применения сборщика(
0
Master of Orion
Эксперт .NET
6100 / 4956 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
30.04.2014, 09:38 11
Не трогайте сборщика, он и так делает что может

Скорее всего, не нужно делать массив, либо делать его меньше. Куда черепашка добраться-то должна?..

Добавлено через 3 минуты
NARTZISS, кстати ограничение бредовое, особенно для шарпа. Считайте сами, размерность массива максимально 1000х1000. Если это массив short'ов, то это 2*1000*1000 ~ 2MB < 8MB. Так что вы где-то еще память теряете. Например, если вы делаете File.ReadAllLines, то тут все понятно
0
3 / 3 / 1
Регистрация: 11.11.2009
Сообщений: 132
13.05.2014, 00:37  [ТС] 12
а как считывать не все строки?
0
Master of Orion
Эксперт .NET
6100 / 4956 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
13.05.2014, 10:00 13
NARTZISS, ну либо вручную через StreamReader, либо читать все подряд и выкидывать ненужное.
0
13.05.2014, 10:00
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
13.05.2014, 10:00
Помогаю со студенческими работами здесь

Вывести единственное число — номер Пети в шеренге учеников
Петя впервые пришел на урок физкультуры в новой школе. Перед началом урока ученики выстраиваются по...

Вывести в выходной файл единственное целое число, которое было загадано
Задача С. Фокус Имя входного файла: Имя выходного гjгайла: Ограничение по времени: Ограничение но...

Вывести единственное целое число - количество гостей-счастливчиков, которым достался торт
&quot;Как на наши именины испекли мы каравай...&quot; прямоугольной формы со сторонам A и B. Именинник,...

В выходной поток вывести единственное вещественное число с точностью три знака после запятой
S=ln\frac{\sqrt{ax}}{1-{x}^{2}} Подскажите что исправить Вычислить значение выражения var a, x,...

В выходной поток вывести единственное вещественное число с точностью три знака после запятой
Входные данные: Во входном потоке задано три вещественных числа a (a &gt; 0), b (b &lt; 0), x (-1 &lt; x &lt;...

В выходной поток вывести единственное вещественное число с точностью три знака после запятой
Входные данные: Во входном потоке дано единственное вещественное число x (|x| &lt;= 1000, x != 4). ...


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Как подключить JavaScript файл в другом JavaScript файле
InfoMaster 20.01.2025
В современной веб-разработке организация кодовой базы играет ключевую роль в создании масштабируемых и поддерживаемых приложений. Модульность и правильное структурирование кода стали неотъемлемыми. . .
Как откатить изменения в исходниках, не внесенные в Git
InfoMaster 20.01.2025
При работе с системой контроля версий Git разработчики часто сталкиваются с необходимостью отменить внесенные изменения в исходном коде. Особенно актуальной становится ситуация, когда изменения еще. . .
В чем разница между px, in, mm, pt, dip, dp, sp
InfoMaster 20.01.2025
В мире цифрового дизайна и разработки интерфейсов правильный выбор единиц измерения играет ключевую роль в создании качественного пользовательского опыта. История развития систем измерений для. . .
Как изменить адрес удалённого репозитория (origin) в Git
InfoMaster 20.01.2025
В терминологии Git термин origin является стандартным именем для основного удаленного репозитория, с которым взаимодействует локальная копия проекта. Когда разработчик клонирует репозиторий с. . .
Как переместить последние коммиты в новую ветку (branch) в Git
InfoMaster 20.01.2025
При работе над проектом часто возникают ситуации, когда необходимо изолировать определенные изменения от основной линии разработки. Это может быть связано с экспериментальными функциями, исправлением. . .
Как вернуть результат из асинхронной функции в JavaScript
InfoMaster 20.01.2025
Асинхронное программирование представляет собой фундаментальную концепцию в JavaScript, которая позволяет выполнять длительные операции без блокировки основного потока выполнения программы. В. . .
Какой локальный веб-сервер выбрать
InfoMaster 19.01.2025
В современной веб-разработке локальные веб-серверы играют ключевую роль, предоставляя разработчикам надежную среду для создания, тестирования и отладки веб-приложений без необходимости использования. . .
Почему планшеты и iPad уже не так популярны, как раньше
InfoMaster 19.01.2025
Эра революционных инноваций История планшетов началась задолго до того, как эти устройства стали привычными спутниками нашей повседневной жизни. В начале 1990-х годов появились первые прототипы,. . .
Как самому прошить BIOS ноутбука
InfoMaster 19.01.2025
BIOS (Basic Input/ Output System) представляет собой важнейший компонент любого компьютера или ноутбука, который обеспечивает базовое взаимодействие между аппаратным и программным обеспечением. . .
Какой Linux выбрать для домашнего компьютера
InfoMaster 19.01.2025
Современные реалии выбора операционной системы В современном мире выбор операционной системы для домашнего компьютера становится все более важным решением, которое может существенно повлиять на. . .
Как объединить два словаря одним выражением в Python
InfoMaster 19.01.2025
В мире программирования на Python работа со словарями является неотъемлемой частью разработки. Словари представляют собой мощный инструмент для хранения и обработки данных в формате "ключ-значение". . . .
Как без исключения проверить существование файла в Python
InfoMaster 19.01.2025
При разработке программного обеспечения на Python часто возникает необходимость проверить существование файла перед выполнением операций с ним. Это критически важная задача, которая помогает избежать. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru