Tävlingsprogrammering/Uppgifter/Talfamiljer

Talfamiljer

Följande uppgift är en generalisering av ett problem från det senaste kvalet till skolor- nas matematiktävling. Vi säger att varje positivt heltal N har en familj som består av N samt alla positiva heltal man kan få genom att ordna om N:s siffror, utom dem som vid omordningen får en nolla som första siffra. (T.ex. har talet 101 familjen 101, 110.) Vi säger också att N:s familj gillar det positiva heltalet p om N eller något annat tal i familjen är delbart med p. (Alla tal som familjen ovan gillar är 1,2,5,10,11,22,55,101,110.)

Skriv ett program som, givet ett antal (högst 10) positiva heltal, bestämmer det minsta positiva heltalet vars familj gillar samtliga av de givna talen. I givna testfall kommer det alltid att finnas ett sådant tal med högst sex siffror.

Körningsexempel 1 (detta var uppgiften i mattetävlingen)

Antal tal? 5 
Tal 1 ? 3 
Tal 2 ? 5 
Tal 3 ? 7 
Tal 4 ? 9 
Tal 5 ? 11
Svar: 459

Körningsexempel 2

Antal tal? 3
Tal 1 ? 79
Tal 2 ? 97
Tal 3 ? 113
Svar: 1469

Körningsexempel 3

Antal tal? 7
Tal 1 ? 164
Tal 2 ? 278
Tal 3 ? 293
Tal 4 ? 382
Tal 5 ? 483
Tal 6 ? 598
Tal 7 ? 23
Svar: 102246

Lösning

Ganska få löste denna trots att den låg som nummer tre, en ledtråd om att den inte var så svår. En miljon tal hinner man loopa igenom och kolla delbarheten med de 10 givna "småtalen". Det enda problemet är att vi inte letar efter ett enstaka tal som är delbart med alla småtalen utan en familj som tillsammans är det. Den enklaste lösningen på detta problem är att när man kollar om ett tal i är delbart med varje småtal så registrerar man resultaten inte på i själv utan på en representant för i:s familj. Då är det enda viktiga att alla i familjen hänvisar till samma representant. Eftersom man sedan ska skriva ut det minsta talet är det ett naturligt val att låta alla hänvisa till det minsta talet i familjen.

För att hitta den minsta representanten i familjen till ett givet tal kan man t.ex. sortera siffrorna i storleksordning eller räkna hur många siffror det finns av varje sort och sedan plocka ihop dem i storleksordning. Det enda man måste vara försiktig med är att man inte sätter en nolla först, för det var ju inte tillåtet enligt uppgiften. För att spara vilka av småtalen som redan är avklarade för en given familj kan man använda en vanlig 1000000 x 10 matris, men eftersom det bara är högst 10 småtal och vi bara vill spara true/false för varje, kan det vara smidigt att spara som en array med binära tal (bitmaskar) istället. Då kan vi efteråt loopa igenom arrayen i stigande ordning tills vi hittar ett tal som har "fullt hus": 111111...

#include <stdio.h>
#define MAX 1000000

int main() {
  int N,i,j,k,p[10],n[100];
  int mask[MAX];
  scanf("%d", &N);
  for(i=0;i<N;i++) scanf("%d", &n[i]);
  for(i=1;i<MAX;i++) mask[i]=0;   //Nollställ de binära talen: inga delbarheter registrerade
  for(i=1;i<MAX;i++) {   //Loopa över alla tal i
    
    //Räkna antal förekomster av varje siffra i talet i
    k=i;
    for(j=0;j<10;j++) p[j]=0;
    while (k>0) {p[k%10]++; k/=10; }

    //Bygg nu upp talet k med siffrorna i storleksordning men första siffran får inte vara 0
    for(j=1;j<10;j++) if(p[j]>0) {k=j; p[j]--; break; }
    for(j=0;j<10;j++) while (p[j]>0) {k=10*k+j; p[j]--; }
    
    for(j=0;j<N;j++) if(i%n[j]==0) mask[k]|=(1<<j);   //Loopa över småtalen och registrera eventuella delbarheter på talet k
  }
  for(i=1;i<MAX;i++) if(mask[i]==(1<<N)-1) break;    //Hitta första talet som har fått registrerat delbarhet med samtliga småtal (d.v.s. mask=2^N-1)
  printf("%d\n", i); 
  return 0;
}

I stort sett samma idé som lösningen ovan. Dock beskriver vi en familj genom att spara antalet av varje siffra i talet, vilket gör att vi måste använda en HashMap istället för en matris alternativt en array med en bitmask.

import java.util.*;

public class Talfamiljer
{
	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		System.out.print("Antal tal? ");
		final int N = scan.nextInt();

		//Läser in talen.
		int [] v = new int [N];
		for(int i = 0; i<N; i++)
		{
			System.out.printf("Tal %d ? ", i+1);
			v[i] = scan.nextInt();
		}

		//id[i] = unikt id för familjen talet i tillhör.
		//id:t för ett tal beräknas på följande sätt, där antal syftar på siffror i talet.
		// [antal nollor]*8^0 + [antal ettor]*8^1 + ... + [antal nior]*8^9
		//Maxvärdet för ett ID är 8^10 - 1 = 2^30 - 1 vilket ryms i en int.
		//Eftersom det max kan förekomma 6 antal av varje siffra kan vi använda 7 som bas,
		// men med bas 8 kan vi använda oss av bitshiftningar istället för multiplikationer = snabbare.
		int [] id = new int [1000000];

		//För varje familj sparar vi en array som markerar vilka av talen,
		// som delar något tal i familjen.
		HashMap <Integer,boolean[]> map = new HashMap <Integer,boolean[]> ();

		//Svaret har högst 6 siffror => bara tal <1000000 är intressanta.
		for(int i = 1; i<1000000; i++)
		{
			//Ex: id[13773] = id[1377] + 8^3
			id[i] = id[i/10] + (1<<3*(i%10)); //1<<3*i == 8^i

			//Om denna familj inte redan finns, så "skapar" vi den.
			if(!map.containsKey(id[i])) map.put(id[i],new boolean [N]);
		}

		//Markerar vilka familjer varje tal delar.
		for(int i = 0; i<N; i++)
		for(int j = v[i]; j<1000000; j+=v[i])
		map.get(id[j])[i] = true;

		//Går igenom alla familjer.
		loop:for(int i = 1; i<1000000; i++)
		{
			boolean [] u = map.get(id[i]); //Hämtar familjen.
			if(u==null) continue; //Vi har redan kollat denna familj.

			for(int j = 0; j<N; j++) //Kollar om den gillas av alla talen.
			if(!u[j]) //Ajdå det fanns ett tal som inte gillade familjen.
			{
				map.remove(id[i]); //Tar bort familjen.
				continue loop;
			}

			//Vi klarade oss igenom ovanstående loop.
			//Alltså gillas i's familj av alla tal.
			System.out.println("\nSvar: " + i);
			break;
		}
	}
}