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

Задача по плюсам - C++

Восстановить пароль Регистрация
 
ReckouNT
 Аватар для ReckouNT
0 / 0 / 0
Регистрация: 13.04.2011
Сообщений: 11
09.10.2011, 16:57     Задача по плюсам #1
Конечно понимаю что немного несправедливо с точки зрения рейтингов, но с задачкой провозился 2 часа, так и не разобрался... Возможно не стоило такую тяжелую брать
Еще можно упрекнуть, что не использовал функции, векора, и т.п. Это да, но я экономил на памяти и размере кода)
Ошибка не синтаксическая, но ответ программы не соответствует ответу на задачу.
Предположительно мог намудрить со знаками в циклах.
Спасибо заранее.

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
55
56
57
58
59
60
61
#include <fstream>
using namespace std;
 
int main()
{
/*
Задание # 337.
Условие: [url]http://********/index.asp?main=task&id_task=337[/url]
i - input
o - output
int n - количество лампочек
int k - количество инверсий
int pi[k-1] - массив из длин инверсий
int result - количество горящих лампочек
int lamps[n-1] - логический массив из лампочек (true - лампочка горит)
int u - количество произведенных инверсий в цикле
int w - для различных циклов
*/
//--------------------------------Input
ifstream i("INPUT.TXT", ios_base::in);
int n, k;
i >> n;
if (n < 1 || n > 1000000000)
 return 0;
i >> k;
if (k < 1 || k > 100)
 return 0;
i.seekg( 2 );
int pi[k-1];
for (int w = 0; w<k; w++)
{
 i >> pi[w];
 if ( pi[w] < 1 || pi[w] > 50 )
 return 0;
}
//-------------------------------/Input
int result = 0;
bool lamps[n-1];
for (int w = 0; w<k; w++)
{
 int u = 1;
 while (u*pi[w] < n)
 {
 //Если лампа текущей инверсии горит -> потушить ее, если не горит -> зажечь
 lamps[pi[w]*u]?lamps[pi[w]*u]=false:lamps[pi[w]*u]=true;
 ++u;
 }
}
 
//Считаем количество горящих лампочек:
for (int w = 0; w<n; w++)
{
 if (lamps[w] == true)
 ++result;
}
//--------------------------------Output
ofstream o("OUTPUT.TXT");
o << result;
//-------------------------------/Output
return 1;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.10.2011, 17:07     Задача по плюсам #2
А вы уверены, что потянете задачу с самым высоким процентом сложности на ********? >_>
Там в обсуждении задачи есть ссылка на решение.
Но лучше начните с чего-нибудь попроще...)
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.10.2011, 17:13     Задача по плюсам #3
Первое, что бросается в глаза:
2)
C++
1
int pi[k-1];
Массив так не объявляют.
ReckouNT
 Аватар для ReckouNT
0 / 0 / 0
Регистрация: 13.04.2011
Сообщений: 11
09.10.2011, 17:16  [ТС]     Задача по плюсам #4
Цитата Сообщение от diagon Посмотреть сообщение
А вы уверены, что потянете задачу с самым высоким процентом сложности на ********? >_>
Там в обсуждении задачи есть ссылка на решение.
Но лучше начните с чего-нибудь попроще...)
Да знаю я, но в этом тоже охота разобратся, не охота ни бросать свои баги, ни тупо копипастить код из обсуждений)

Добавлено через 2 минуты
Цитата Сообщение от soon Посмотреть сообщение
Первое, что бросается в глаза:
1) Переполнение int n.
2)
Массив так не объявляют.
1. В условии задачи посмотрите на множество в которое n входит.
2. Вроде бы массив с таким объявлением более менее работает
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.10.2011, 17:19     Задача по плюсам #5
Касательно int я уже поправился. А массив так _не_ объявляют, честное слово. Читайте про new или malloc в Си.
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.10.2011, 17:22     Задача по плюсам #6
Цитата Сообщение от ReckouNT Посмотреть сообщение
Да знаю я, но в этом тоже охота разобратся, не охота ни бросать свои баги, ни тупо копипастить код из обсуждений)
А вы уверены, что у вас есть достаточная теоретическая база, чтобы вообще понять решение?
Цитата Сообщение от ReckouNT Посмотреть сообщение
2. Вроде бы массив с таким объявлением более менее работает
Работает только в gcc либо С99. По стандарту с++ такие объявления недопустимы.
ReckouNT
 Аватар для ReckouNT
0 / 0 / 0
Регистрация: 13.04.2011
Сообщений: 11
09.10.2011, 17:28  [ТС]     Задача по плюсам #7
Цитата Сообщение от diagon Посмотреть сообщение
А вы уверены, что у вас есть достаточная теоретическая база, чтобы вообще понять решение?

Работает только в gcc либо С99. По стандарту с++ такие объявления недопустимы.
В теоретической базе уверен. Здесь сложности только с логикой.
У меня g++
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
09.10.2011, 17:32     Задача по плюсам #8
Компилятор на acmp может это просто не переварить. Читайте про new, либо делайте статический массив. Потом только будете с логикой разбираться.
aeshes
 Аватар для aeshes
437 / 200 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 17:39     Задача по плюсам #9
Вы пишите, что съэкономили на размере памяти и скорости... Но при максимальном N=1 млрд, вас не смущает массив из миллиарда ячеек? А время его обработки?
Эта задача должна использовать другие структуры данных, не массивы. Либо они должны быть по другому реализованы
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
09.10.2011, 17:50     Задача по плюсам #10
Цитата Сообщение от aeshes Посмотреть сообщение
Вы пишите, что съэкономили на размере памяти и скорости... Но при максимальном N=1 млрд, вас не смущает массив из миллиарда ячеек? А время его обработки?
Эта задача должна использовать другие структуры данных, не массивы. Либо они должны быть по другому реализованы
Угу, эта задача нерешаема перебором из-за ограничений.

Цитата Сообщение от soon Посмотреть сообщение
Компилятор на acmp может это просто не переварить.
Да, там древняя версия VC.
ReckouNT
 Аватар для ReckouNT
0 / 0 / 0
Регистрация: 13.04.2011
Сообщений: 11
09.10.2011, 17:52  [ТС]     Задача по плюсам #11
Цитата Сообщение от aeshes Посмотреть сообщение
Вы пишите, что съэкономили на размере памяти и скорости... Но при максимальном N=1 млрд, вас не смущает массив из миллиарда ячеек? А время его обработки?
Эта задача должна использовать другие структуры данных, не массивы. Либо они должны быть по другому реализованы
Смущает, очень даже...
Пока ничего лучше в голову не приходит)
aeshes
 Аватар для aeshes
437 / 200 / 13
Регистрация: 07.10.2011
Сообщений: 462
09.10.2011, 18:06     Задача по плюсам #12
Ну и еще, к слову, задачи на АСМР тренируют не навыки программирования на С++, а навыки алгоритмизации, построения оптимальных алгоритмов решения задач

так что ваша программа вполне возможно, написана верно с точки зрения синтаксиса С++, однако не будет принята сайтом из-за того, что не удовлетворяет ограничениям на память/скорость работы

Добавлено через 6 минут
Подумайте, нельзя ли как-то уменьшить размер рассматриваемого массива с 1 млрд элементов до более приемлемого числа
Yandex
Объявления
09.10.2011, 18:06     Задача по плюсам
Ответ Создать тему
Опции темы

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