Просуммировать количество точек в наборе домино, где количество точек на каждом конце может быть от 1 до n

@MayaNash · Регистрация: 24.08.2011

Студворк — интернет-сервис помощи студентам

Посмотрев на ряд костяшек, расположенный в лексикографическом порядке, видна формула этой суммы: 2*n*сумма(от 1 до n):

Code
1
2
1 1 1 2 2 2 3 3 3
1 2 3 1 2 3 1 2 3

Однако программа не проходит уже второй тест (тесты неизвестны):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
 
int sum(int n)
{
    return (n+1)*(n/2) + (n%2 == 1? (n+1)/2 : 0);
}
 
int main()
{
    int n;
    cin >> n;
    cout << 2*n*sum(n);
    return 0;
}

В чем дело?

@MayaNash · 13.11.2014, 10:12 **[ТС]**

Ilot, неправда, результат правильный, прошел все тесты

@SlavaSSU · 13.11.2014, 13:07

Ilot, 1) чем она малоэффективная? если есть решение быстрее, то кидайте. это решение я написал исходя из ограничений и оно прошло все тесты.

@mihey1993 · 13.11.2014, 13:51

Тут есть еще один вариант, не уверен правда что он лучше, но все же на первый взгляд работает.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
 
int Sum(int n){
    int sum = 0;
    if (n>2){
        sum = n*(3*n - 1) + Sum(n-1);
        return sum;
    }
    else {
        return 12;
    }
}
 
int main() {
    for (int i = 2;i<7;i++){
        cout << Sum(i) << endl;
    }
}

Дает ответы для n = 2 to 6 соответственно 12 36 80 150 252
Основано всё на статистическом наблюдении о том, что при переходе числа точек с n до n+1 сумма увеличивается на n(3n - 1). То есть при увеличении n с 2 до 3 сумма увеличивается на 3*(3*3-1) = 24 относительно суммы с n = 2, с 3 до 4 на 4*(3*4-1) = 44 относительно суммы с n = 3 и т.д.

@SlavaSSU · 13.11.2014, 14:00

mihey1993, правильный ответ при n == 3 -> 30. читайте мой коммент про правильность постановки выше, пример у ТС неправильно написан для n == 3.

Керра,
еще одно xD.

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
 
using namespace std;
 
int main(){
    long long n;
    cin >> n;
 
    cout << (n + 2) * (n * n + n) / 2;
 
    return 0;
}

@mihey1993 · 13.11.2014, 15:43

Прошу прощения, не заметил - тогда извратимся вот так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
 
int Sum(int n){
    int sum = 0;
    if (n>2){
        return n*(10 + 0.5*(10+n-4)*(n-3));
    }
    else {
        return 12;
    }
}
 
int main() {
    for (int i = 2;i<7;i++){
        cout << Sum(i) << endl;
    }
    return 0;
}

Ilot · 13.11.2014, 17:09

Сообщение от Керра

Ilot, неправда, результат правильный, прошел все тесты

Может быть потому, что вы немного не точно указали в сабже условие? Вариант без циклов:

C++
1
2
3
4
5
6
7
#include <iostream>
int main() {
    long long n;
    std::cin >> n;
    std::cout << ((n * (n + 1) * (n + 2)) >> 1);
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Программное добавление префикса в нумерацию документов Maks 27.10.2026 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .	После закрытия оутлука продолжает висеть процесс в диспетчере задач Maks 27.10.2026 С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .	Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный AmbA 26.10.2026 Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .	Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .

@MayaNash 1296 / 470 / 151 Регистрация: 24.08.2011 Сообщений: 2,249
	13.11.2014, 10:12 [ТС]
	Ilot, неправда, результат правильный, прошел все тесты 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	13.11.2014, 13:07
	Ilot, 1) чем она малоэффективная? если есть решение быстрее, то кидайте. это решение я написал исходя из ограничений и оно прошло все тесты. 0