Tävlingsprogrammering/Uppgifter/Hopplek

Hopplek

När kängurumammans barn blivit äldre och står på egna ben, leker de en hopplek (för vad leker kängurur annars?). De har ritat upp N rutor (högst 100) i en rad på marken, numrerade från 1 till N. Eftersom barnen (högst 10 stycken) är olika stora hoppar de olika långt: det första (minsta) barnet hoppar alltid en ruta i taget, det andra barnet alltid två rutor i taget, det tredje barnet alltid tre rutor i taget o.s.v.

Givet i vilken ruta varje kängurubarn står från början (alla olika), skriv ett program som räknar ut det maximala antalet barn som kan hamna i samma ruta. De kan göra hur många hopp de vill och de kan även stå stilla, men de får inte hoppa utanför rutorna.

Körningsexempel 1

Antal barn ? 6 
Antal rutor ? 9 
Position för barn 1 ? 1 
Position för barn 2 ? 7 
Position för barn 3 ? 9 
Position för barn 4 ? 6 
Position för barn 5 ? 8 
Position för barn 6 ? 3 
Maximal samling: 5

Körningsexempel 2

Antal barn ? 4 
Antal rutor ? 5 
Position för barn 1 ? 4 
Position för barn 2 ? 2 
Position för barn 3 ? 3 
Position för barn 4 ? 5 
Maximal samling: 2

Lösning

Istället för att börja låta kängurubarnen hoppa omkring planlöst bör man fråga sig: Kan känguru j komma till ruta k ? För detta finns ett enkelt villkor, nämligen att k-p[j] är jämnt delbart med j, där p[j] är startpositionen för känguru j. Om vi nu för en given ruta loopar över alla kängururna får vi enkelt veta hur många kängurur som kan nå denna ruta. Dessutom behövs en loop över rutorna för att räkna ut maxvärdet.

Lösning i C:

#include <stdio.h>

int main() {
  int N,nk,p[11],i,j,k,max,cnt;
  scanf("%d %d", &nk,&N);
  for(i=1;i<=nk;i++) scanf("%d", &p[i]);
  max=0;
  for(k=1;k<=N;k++) {  //Loopa över målrutor
    cnt=0;
    for(j=1;j<=nk;j++)    // Loopa över kängurur
      if( (p[j] - k) % j == 0) cnt++;    //Öka räknaren om känguru j kan nå ruta k
    if(cnt>max) max=cnt;   //Spara det maximala värdet
  }
  printf("Maximal samling: %d\n", max);
  return 0;
}