Tävlingsprogrammering/Uppgifter/Siffersumman

Se problemet

För att få 4 av 5 poäng på denna krävdes bara att man gör precis vad som står i uppgiften: Man ökar succesivt talet med 1, räknar varje gång ut siffersumman, och avbryter när man kommer till ett tal som ger samma siffersumma som det ursprungliga talet.

Enda möjliga svårigheten är alltså att beräkna siffersumman för ett givet tal. Detta kan göras på flera olika sätt (t.ex. med strängfunktioner eller mod-operatorn) och eftersom effektiviteten här inte spelar någon roll väljer man lämpligtvis ett sätt som är så enkelt som möjligt att skriva i det programmeringsspråket man skriver i.

Lösningsförslag i Python 2, som ger 4p:

import sys
def siffersumma(n): 
   return sum( [ int(x) for x in str(n) ] )    #Översätt talet till sträng och sedan varje tecken tillbaka till tal

N=int(sys.stdin.readline())
m=N+1
while siffersumma(N) != siffersumma(m): 
   m+=1
print m

Att få den sista poängen är betydligt svårare. Med så stora tal tar det alldeles för lång tid att stega sig fram tal för tal. Istället får man hitta en lösning som bygger på ett mer matematiskt resonemang:

• För enkelhets skull låter vi en inledande 0:a ingå i talet.
• Svaret är alltid ett tal där någon av siffrorna (eventuellt den inledande nollan) har ökat med 1 och alla siffrorna till vänster om den är oförändrade. Bevis: Antag att det finns en lösning där en siffra har ökats med Q>1 (och alla siffror till vänster om den är oförändrade) och att summan av siffrorna till höger om denna siffra från början var S. Då vet vi att den summan kan vara S och att den även kan vara S-Q, och därmed måste den även kunna ligga däremellan, t.ex. S-1. Alltså finns det en lösning där siffran har ökats med 1 istället, och denna lösning är ju naturligtvis ett lägre tal än den antagna lösningen.
• För att lösningen ska bli ett så lågt tal som möjligt ska den siffran som ökats med 1 vara så långt till höger som möjligt i talet.
• När väl den siffran hittats, kan siffrorna till höger sättas "glupskt" så att de minst signifikanta siffrorna (längst till höger) är så stora som möjligt (gärna 9:or), men naturligtvis uppfyllande att summan ska vara S-1.

Följaktligen löser vi problemet i två steg: Först kollar vi för varje siffra, med början från höger, om den kan ökas med 1 (kravet är att siffran inte är 9 och att siffersumman till höger (S) inte är 0 eftersom den ska minskas med 1). Därefter "fyller vi upp" siffrorna till höger enligt ovan.

Exempel: N=97=097

• Vi börjar från höger
• 7:an kan inte ökas eftersom summan till höger är 0.
• 9:an kan inte ökas eftersom den redan är 9.
• 0:an kan ökas till 1 eftersom summan till höger är 16.
• Den nya summan till höger ska då vara 15 och vi börjar nu från höger och sätter siffrorna så stora som möjligt, först en 9:a och sedan en 6:a.
• Svar: 169

Lösningsförslag i C:

#include <stdio.h>
#include <string.h>
int MIN(int p, int q) {return p<q?p:q;}

int main() {
  int N[100],i,k,m,p,S;
  char inp[101];	
  scanf("%s", inp);
  m=0;
  for(i=strlen(inp)-1;i>=0;i--) N[m++]=inp[i]-'0';
  N[m++]=0;   //Lägg till en inledande nolla

  //Hitta den siffran som ska ökas.
  S=0;  //Siffersumman till höger
  for(k=0;k<m;k++) {  
    if(N[k]<9 && S>0) break;   //Då har vi hittat rätt siffra
    S+=N[k];
  }

  // Öka siffran och minska den återstående siffersumman
  N[k]+=1; 
  S--;

  //Fyll upp glupskt till den återstående siffersumman.
  for(p=0;p<k;p++) {
    N[p]=MIN(S,9);
    S-=N[p];
  }

  //Skriv ut lösningen
  for(p=m-1;p>=0;p--) if(p<m-1 || N[p]>0) printf("%d",N[p]);   //Undvik att skriva ut inledande nolla
  printf("\n");
  return 0;
}