2 / 2 / 1
Регистрация: 05.08.2017
Сообщений: 61
1

Сколько различных прямоугольников может на листочке нарисовать Вася, если рисовать он умеет только по линиям?

09.10.2017, 13:11. Показов 5270. Ответов 16
Метки нет (Все метки)

У Васи есть листочек в клеточку, состоящий из N клеток по горизонтали и M клеток по вертикали, причем линии клеток листочка на краю также видны. Сколько различных прямоугольников может на этом листочке нарисовать Вася, если рисовать он умеет только по линиям?

Нашел решение, но не могу понять суть формулы.

Может кто поможет подробно расписать, откуда получилась такая формула (сам процес получение формулы).
Спасибо

Pascal
1
2
3
4
5
6
7
var  m, n, k: integer;
begin
  readLn(n,m);
  k:=(n*(n+1) div 2)*(m*(m+1) div 2);
  writeLn(k);
  readLn;
end.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.10.2017, 13:11
Ответы с готовыми решениями:

Сколько может быть дано различных сигналов, если каждый светофор имеет три состояния
На железнодорожной станции имеется m светофоров. Сколько может быть дано различных сигналов, если...

Сколько человек может говорить только по-французски и сколько может говорить на английском и французском языках?
В группе из 100 человек 72 человека могут говорить по-английски, а 43 могут говорить по-французски....

Найти интеграл методом прямоугольников по средним линиям
Уместен ли такой вариант записи формулы: I=h\sum_{k=0}^{n-1}f\left(a+h\left(k+1 \right) \right)...

Сколько бутылок воды выпьет Вася с друзьями, если бутылка воды стоит 20 коп
Мальчику в день рождения родители подарили 1 рубль, чтобы он с друзьями мог сходить в кафе. Сколько...

16
Модератор
9467 / 4793 / 3208
Регистрация: 17.08.2012
Сообщений: 15,027
11.10.2017, 14:57 2
Элементарно, Ватсон.

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

Прямоугольников шириной 1 и высотой m будет 1n штук.
Прямоугольников шириной 1 и высотой m-1 будет 2n штук.
Прямоугольников шириной 1 и высотой m-2 будет 3n штук.
...
Прямоугольников шириной 1 и высотой 1 будет mn штук.

Всего шириной 1 будет 1n+2n+3n+...+mn=(1+2+3+...+m)n

Прямоугольников шириной 2 и высотой m будет 1(n-1) штук.
Прямоугольников шириной 2 и высотой m-1 будет 2(n-1) штук.
Прямоугольников шириной 2 и высотой m-2 будет 3(n-1) штук.
...
Прямоугольников шириной 2 и высотой 1 будет m(n-1) штук.

Всего шириной 2 будет 1(n-1)+2(n-1)+3(n-1)+...+m(n-1)=(1+2+3+...+m)(n-1)

...
...
...

Прямоугольников шириной n и высотой m будет 1∙1 штук.
Прямоугольников шириной n и высотой m-1 будет 2∙1 штук.
Прямоугольников шириной n и высотой m-2 будет 3∙1 штук.
...
Прямоугольников шириной n и высотой 1 будет m∙1 штук.

Всего шириной n будет 1∙1+2∙1+3∙1+...+m∙1=(1+2+3+...+m)∙1

Суммируем все получившиеся количества:

(1+2+3+...+m)n+(1+2+3+...+m)(n-1)+...+(1+2+3+...+m)∙1=(1+2+3+...+m)(1+2+3+...+n)

суммы в скобках есть ни что иное, как суммы арифметических прогрессий с первым членом, равным 1, и разностью прогрессии, также равной 1. Записываем то, что в скобках, как формулы для суммы соответствующей прогрессии:

(m(m+1)/2)(n(n+1)/2)

используются целые числа, одно из двух подряд идущих целых чисел обязательно чётное, вместо оператора деления на 2 можно применить операцию деления на 2 нацело:

(n(n+1) div 2)(m(m+1) div 2)

Voila!
0
Почетный модератор
64270 / 47569 / 32739
Регистрация: 18.05.2008
Сообщений: 115,182
11.10.2017, 15:14 3
Самое интересное в его условии это прочитать m,n 2 числа размером, как в условии указано до 1010000
0
Модератор
9467 / 4793 / 3208
Регистрация: 17.08.2012
Сообщений: 15,027
11.10.2017, 15:32 4
Читал-читал... Как отреагирует, я всех его Васей в одну тему солью...
0
41 / 74 / 15
Регистрация: 04.10.2017
Сообщений: 283
13.10.2017, 17:33 5
Цитата Сообщение от Cyborg Drone Посмотреть сообщение
суммы в скобках есть ни что иное, как суммы арифметических прогрессий
Исправил. Может поэтому темы плодит.
1
Эксперт Pascal/Delphi
2383 / 1295 / 1491
Регистрация: 29.08.2014
Сообщений: 4,651
13.10.2017, 20:41 6
особо не проверял (арифметику отсюда сдул: http://e-maxx.ru/algo/big_integer):
Pascal
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
uses SysUtils,Math;
const base:longint=1000000000;
type LNum=array of longint;
     CArr=array of char;
var
  n,m,q,z:LNum;
  a,b:CArr;
  c:char;
  spc:boolean;
procedure LNumPrint(a:LNum);
var
  i:longint;
begin
   if length(a)=0 then write(0) else write(a[length(a)-1]);
   for i:=length(a)-2 downto 0 do
     write(Format('%.9d',[a[i]]));
end;
 
procedure CharArrtoLNum(s:array of char;var a:LNum);
var
  i,j:longint;
begin
  j:=0;
  setlength(a,0);
  i:=length(s);
  while i>0 do begin
    j:=j+1;
    setlength(a,j);
    if i>8 then a[j-1]:=StrToInt(copy(s,i-8,9))
           else a[j-1]:=StrToInt(copy(s,0,i));
    i:=i-9;
  end;
end;
 
procedure LNumAdd(var a:LNum;b:LNum);
var
  i,k,t:longint;
begin
  k:=0;
  for i:=0 to max(length(a),length(b))-1 do begin
    if i=length(a) then setlength(a,i+1);
    if i>=length(b) then t:=0 else t:=b[i];
     a[i]:=a[i]+k+t;
     if a[i]>base then begin k:=1;a[i]:=a[i]-base;end;
  end;
  if k=1 then begin setlength(a,i+1);a[i]:=1;end;
end;
 
Procedure LNumMult(a,b:LNum;var c:LNum);
var
  i,j,k,t:longint;
  z:uint64;
begin
  k:=0;
  setlength(c,length(a)+length(b));
  for i:=0 to length(c)-1 do c[i]:=0;
  for i:=0 to length(a)-1 do begin
    j:=0;
    while (j<length(b)) or (k<>0) do begin
      if j>=length(b) then t:=0 else t:=b[j];
      z:=uint64(c[i+j]+int64(a[i])*int64(t)+k);
      c[i+j]:=z mod base;
      k:=z div base;
      j:=j+1;
    end;
  end;
  while (length(c)>0) and (c[length(c)-1]=0) do setlength(c,length(c)-1);
end;
 
Procedure LNumDivNumber(var a:LNum;b:longint);
var
  i,j:integer;
  z:uint64;
begin
  if b>=base then exit;
  j:=0;
  for i:=length(a)-1 downto 0 do begin
    z:=uint64(int64(a[i])+uint64(int64(j)*int64(base)));
    a[i]:=z div b;
    j:=z mod b;
  end;
  while (length(a)>0) and (a[length(a)-1]=0) do setlength(a,length(a)-1);
end;
 
procedure addnum(var a:Carr;c:char);
var
  i:integer;
begin
  i:=length(a);
  setlength(a,i+1);
  a[i]:=c;
end;
 
begin
  spc:=false;
  while not eoln do begin
   read(c);
   if c=' ' then spc:=true;
   if spc then addnum(b,c) else addnum(a,c);
  end;
  CharArrToLNum(a,n);
  CharArrToLNum(b,m);
  setlength(q,1);
  q[0]:=1;
  LNumAdd(n,q);
  CharArrToLNum(a,z);
  LNumMult(z,n,n);
  LNumDivNumber(n,2);
  LNumAdd(m,q);
  CharArrToLNum(b,z);
  LNumMult(z,m,m);
  LNumDivNumber(m,2);
  LNumMult(n,m,q);
writeln('Result:');
  LNumPrint(q);
end.
0
Модератор
9467 / 4793 / 3208
Регистрация: 17.08.2012
Сообщений: 15,027
15.10.2017, 09:04 7
tmpValue, спасибо, исправил в посте #2 "геометрических" на "арифметических".
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32446 / 20941 / 8104
Регистрация: 22.10.2011
Сообщений: 36,207
Записей в блоге: 7
15.10.2017, 12:08 8
Цитата Сообщение от Joy Посмотреть сообщение
арифметику отсюда сдул
Зачем? Это ж FPC, тут свое есть:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
program project1;
 
{$mode objfpc}{$H+}
 
uses gmp;
 
var
  m, n, res : mpz_t;
 
begin
  mpz_init(m);
  mpz_init(n);
  if mp_scanf('%Zd %Zd', @m, @n) = 2 then
  begin
    mpz_init(res);
    res := (n * (n + 1) / 2);
    res := res * (m * (m + 1) / 2);
    mp_printf('%Zd'#10, @res);
  end;
end.
работает:
Миниатюры
Сколько различных прямоугольников может на листочке нарисовать Вася, если рисовать он умеет только по линиям?  
1
Почетный модератор
64270 / 47569 / 32739
Регистрация: 18.05.2008
Сообщений: 115,182
15.10.2017, 12:25 9
volvo, А почему у меня просит gmp.dll? Модуль gmp есть.
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32446 / 20941 / 8104
Регистрация: 22.10.2011
Сообщений: 36,207
Записей в блоге: 7
15.10.2017, 12:31 10
FPC Wiki говорит, что надо скачать по ссылке файл и переименовать его в gmp.dll
1
Почетный модератор
64270 / 47569 / 32739
Регистрация: 18.05.2008
Сообщений: 115,182
15.10.2017, 12:34 11
Спасибо, уже разобрался.

Добавлено через 55 секунд
Я скачал отсюда.
http://ru.dll-ocx.com/download/gmp.dll/24618.html
0
41 / 74 / 15
Регистрация: 04.10.2017
Сообщений: 283
15.10.2017, 13:45 12
Цитата Сообщение от volvo Посмотреть сообщение
Зачем? Это ж FPC, тут свое есть
Жую попкорн и думаю, а кто и как скоро вспомнит гну. Записки дебианщика =))
0
2 / 2 / 1
Регистрация: 05.08.2017
Сообщений: 61
16.10.2017, 18:37  [ТС] 13
Цитата Сообщение от Joy Посмотреть сообщение
особо не проверял (арифметику отсюда сдул: http://e-maxx.ru/algo/big_integer):
Скопировал и отправил решение на сайте e-olimp. Программа набрала 0%.

Добавлено через 1 минуту
Цитата Сообщение от volvo Посмотреть сообщение
Зачем? Это ж FPC, тут свое есть:
И этот вариант набрал 0%.
0
Эксперт Pascal/Delphi
2383 / 1295 / 1491
Регистрация: 29.08.2014
Сообщений: 4,651
16.10.2017, 18:40 14
а если убрать
Pascal
1
writeln('Result:');
?
0
2 / 2 / 1
Регистрация: 05.08.2017
Сообщений: 61
16.10.2017, 18:43  [ТС] 15
Цитата Сообщение от Joy Посмотреть сообщение
а если убрать
тогда проходит на 40%, что и было до длинной арифметики.
После теста №9 пишет "Неверный ответ"
0
tmpValue
16.10.2017, 21:19
  #16

Не по теме:

Капинус, так, чисто ради любопытства, олимпиадное программирование подразумевает наличие программиста? Ну то есть кто здает задание, тот его и пишет.

0
2 / 2 / 1
Регистрация: 05.08.2017
Сообщений: 61
17.10.2017, 08:44  [ТС] 17
Цитата Сообщение от tmpValue Посмотреть сообщение
Не по теме:
Капинус, так, чисто ради любопытства, олимпиадное программирование подразумевает наличие программиста? Ну то есть кто здает задание, тот его и пишет.
ага
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.10.2017, 08:44
Помогаю со студенческими работами здесь

Сколько различных протоколов может сформироваться?
Две команды играют в футбол. Игра идёт до 8 голов. После каждого гола в протокол сносится новый...

Сколько различных чисел может быть составлено?
Из девяти значащих цифр составляются трёхзначные числа. Сколько различных чисел может быть...

Сколько различных треугольников у него может получиться?
Имеется кусок проволоки длины 24. Петя Торт хочет согнуть её и получить треугольник с периметром 24...

Сколько различных последовательностей шаров может получиться?
Из мешка, содержащего m черных шаров и n белых, достают и выкладывают подряд шары. Сколько...

Сколько различных вариантов билетов может быть выписано?
На участке железной дороги 15 станций. Сколько различных вариантов билетов может быть выписано на...

Сколько различных кодовых слов может использовать Игорь
Помогите, пожалуйста, девушке, решить задачу по комбинаторике. Пересмотрела кучу решений подобных...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru