Çubuqlar#1405

Çubuqlar (Həll təhlili)

Tutaq ki, $S$ verilmiş çubuqlar çoxluğudur. Lazımdır ki, $S$ çoxluğunun içərisindən iki kəsişməyən altçoxluq $A$ və $B$ tapaq ki, onların hər biri uzunluqları bərabər olan iki altçoxluğa bölünsün.

Hər altçoxluq üçün $ma s k \subseteq S$ mask \subseteq S onun çubuqlarının uzunluqlarının cəmini hesablayıb $s u m [ma s k]$ sum[mask]-də qeyd edək.

Bütün altçoxluqları $I \subset S$ I \subset S olaraq seçək. Hər bir altçoxluq $I$ üçün onun bütün altçoxluqlarını $J \subset I$ J \subset I olaraq seçək. Əgər elə bir $J$ varsa ki, $2 \cdot s u m [J] = s u m [I]$ 2 \cdot sum[J] = sum[I] (yəni $J$ -dəki çubuqların ümumi uzunluğu $I$ -dəki bütün çubuqların uzunluqlarının cəminin yarısına bərabərdirsə), onda altçoxluq $I$ bir düzbucaqlının qarşı-qarşıya duran tərəfləri kimi istifadə edilə bilər. Bu halda $c an [I] = t r u e$ can[I] = true təyin edək.

Təsvir olunan prosedur $O (3^{n})$ O(3^n) zamanda yerinə yetirilir.

Bütün çubuqlar çoxluqlarının altçoxluqlarını seçək. Əgər bir çoxluq $I$ üçün bir altçoxluq $J \subset I$ J \subset I varsa ki, $c an [J] = t r u e$ can[J] = true və $c an [I x or J] = t r u e$ can[I~xor~J] = true (yəni $J$ və $I x or J$ I~xor~J çoxluqları kəsişmir), onda bir düzbucaqlının üfüqi və şaquli tərəfləri arasında çubuqların bir mümkün düzülüşünü tapmış oluruq.

Belə bir düzbucaqlının tərəflərinin uzunluqları $s u m [J] /2$ sum[J] / 2 və $s u m [I x or J] /2$ sum[I~xor~J] / 2 olur. Göstərilən dəyərlər arasında ən böyük sahəsi olan düzbucaqlını seçirik.

Alqoritmin icrası

Çubuqların uzunluqları $a$ massivində saxlanılır. Hər bir $ma s k$ çubuqlar altçoxluğu üçün onların ümumi uzunluğunu $s u m [ma s k]$ sum[mask] massivində saxlayırıq. Əgər $ma s k$ çoxluğu bərabər uzunluqlar cəmi olan iki altçoxluğa bölünə bilirsə - bu, düzbucaqlının qarşı-qarşıya duran tərəflərinə uyğun gələcək - $c an [ma s k]$ can[mask] qiymətini $t r u e$ olaraq təyin edirik.

#define MAX 16
int a[MAX];
int sum[1 << MAX];
bool can[1 << MAX];

Proqramın əsas hissəsi. Daxil olan məlumatları oxuyuruq.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);

Bütün çubuq altçoxluqlarını seçək və onların ümumi uzunluğunu hesablayın.

for (i = 0; i < 1 << n; i++)
  for (j = 0; j < n; j++)
    if (i & (1 << j)) sum[i] += a[j];

Sonra bütün mümkün çubuq altçoxluqlarını seçək. Əgər bir çoxluq $I$ üçün bir altçoxluq $J \subset I$ J \subset I varsa ki, $J$ -dəki çubuqların ümumi uzunluğu $I$ -dəki çubuqların ümumi uzunluğunun yarısına bərabərdirsə, onda $c an [I] = t r u e$ can[I] = true təyin edərək bu çubuqları düzbucaqlının qarşı-qarşıya duran tərəfləri kimi istifadə edə bilərik.

for (i = 1; i < 1 << n; i++) 
{
  int s = sum[i];
  for (j = i; j > 0; j = (j - 1) & i)
    if (sum[j] * 2 == s) 
    {
      can[i] = true;
      break;
    }
}

C++

Bütün çubuqların altçoxluqlarını seçirik. Əgər bir çoxluq $I$ üçün bir altçoxluq $J \subset I$ J \subset I varsa ki, $c an [J] = t r u e$ can[J] = true və $c an [I x or J] = t r u e$ can[I~xor~J] = true, onda bu, çubuqların üfüqi və şaquli tərəflər arasında bir mümkün düzülüşüdür. Belə bir düzbucaqlının tərəflərinin uzunluqları $s u m [J] /2$ sum[J] / 2 və $s u m [I x or J] /2$ sum[I xor J] / 2 olur.

res = 0;
for (i = 1; i < 1 << n; i++)
  for (j = i; j > 0; j = (j - 1) & i)
    if (can[j] && can[i ^ j])
      res = max(res, sum[j] / 2 * 1LL * sum[i ^ j] / 2);

Ən böyük ölçüsü olan tapılmış düzbucaqlının sahəsini çıxarırıq.

printf("%lld\n", res);