Tävlingsprogrammering/Uppgifter/Pyramidbygge

Pyramidbygge (PO-kvalet 2008)

När man ska inleda ett större projekt, exempelvis bygga en pyramid, är det bäst att tänka efter en gång extra. Du ska skriva ett program som beräknar hur hög pyramid man kan bygga om man har tillgång till ett visst antal stenblock.

Vi antar att pyramiden är kompakt, d.v.s. det finns inga hålrum inuti. Vidare byggs den enligt principen i figuren ovan. Varje lager är alltså kvadratiskt med en sidlängd som är två block mindre än det underliggande lagrets. Det översta lagret består alltid av ett ensamt block.

Programmet ska fråga efter antalet tillgängliga block (högst hundra miljoner) och skriva ut höjden (i block räknat) för den största pyramid som kan byggas. Det gör ingenting om det blir block över, men det får inte saknas ett enda block.

Körningsexempel:

Antal block ? 83  
Höjd: 3 

Lösning

I motsats till verkliga pyramidbyggare kan vi börja från toppen. Vi lägger till ett lager i taget (med 1², 3², 5², ... block) och håller koll på det totala antalet använda block. När denna summa överstiger det tillgängliga antalet har vi byggt precis ett lager för högt.

Exempellösning i C:

#include <stdio.h>

int main() {
  int N, i, sum;
  printf("Antal block ? ");
  scanf("%d", &N);
  sum=0;
  for(i=1;1;i++) {
    sum+=(2*i-1)*(2*i-1);
    if(sum>N) break;
  }
  printf("Höjd: %d\n", i-1);
  return 0;
}

Exempellösning i Java:

import java.util.Scanner;
public class main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    System.out.print("Antal block: ");
    int antal = in.nextInt();
    int kloss = 1;
    int höjd = 0;
    int i = 3;
    while(antal >= kloss){
      antal -= kloss;
      kloss = i;
      kloss *= kloss;
      i += 2;
      höjd++;
    }
    System.out.print("Max höjd: " + höjd);
  }
}

Exempellösning i VB.net:

  Private Sub Berakna()
  Dim Block As Integer, Sum As Integer, n As Integer
  Block = InputBox("Antal block?")
  Do While 1 = 1
       n += 1
       Sum += (2 * n - 1) ^ 2
       If Sum > Block Then
          Exit Do
       End If
  Loop
  MsgBox("Höjd: " & n - 1)
  End Sub

Exempellösning i Haskell:

 solve x = length . takeWhile (<=x) . scanl1 (+) . map (^2) $ [1,3 ..]