Tävlingsprogrammering/Uppgifter/Will Rogers fenomen
Will Rogers fenomen
Will Rogers (1879-1935) var en amerikansk komiker känd för bland annat följande citat:
”When the Okies left Oklahoma and moved to California, they raised the average intelligence level in both states.”
Denna skenbara paradox, att flyttning av ett element från en mängd till en annan gör att medelvärdet ökar i båda mängderna, har därför fått namnet Will Rogers fenomen. Du ska skriva ett program som läser in två grupper A och B vardera bestående av minst två och högst tio positiva heltal och avgör huruvida det är möjligt att genom att flytta ett tal från den ena gruppen till den andra få medelvärdet att öka i båda grupperna och i så fall vilket tal som ska flyttas till vilken grupp. Om det finns flera möjligheter så räcker det att ange en av dem.
Körningsexempel:
Antal tal i grupp A? 3 Tal ? 3 Tal ? 1 Tal ? 2 Antal tal i grupp B ? 4 Tal ? 4 Tal ? 3 Tal ? 5 Tal ? 4 Flytta talet 3 till A.
Ett andra körningsexempel:
Antal tal i grupp A ? 2 Tal ? 7 Tal ? 5 Antal tal i grupp B ? 2 Tal ? 4 Tal ? 6 Omöjligt!
Kommentar: I det första exemplet är medelvärdena 2 respektive 4 innan flyttning. Efter att talet 3 flyttats över från B till A är medelvärdena 2.25 respektive 4.333... I det andra exemplet kan fenomenet inte uppkomma. Om man t.ex. flyttar talet 5 från A till B så ökar visserligen medelvärdet i grupp A men medelvärdet i grupp B förblir oförändrat.
Lösning
[redigera]Här lönar det sig att tänka lite innan man börjar skriva. Man behöver faktiskt aldrig räkna ut nya medelvärden och jämföra dem med de gamla (även om en sådan lösning också är helt acceptabel). Istället kan man helt enkelt utnyttja att när man lägger till ett tal till en grupp så ökar medelvärdet om talet är högre än det tidigare medelvärdet, medan det minskar om talet är lägre än det tidigare medelvärdet.
Så problemet kan formuleras om så här:
- Räkna ut medelvärdena för grupperna, mA och mB.
- Gå igenom alla talen i grupp A. Om något av dem är lägre än mA men högre än mB, flytta talet till B.
- Gå igenom alla talen i grupp B. Om något av dem är lägre än mB men högre än mA, flytta talet till A.
- Om inget tal har flyttats, skriv ut "Omöjligt!"
Det finns en sak att tillägga, som är nyttig att tänka på i alla tävlingssammanhang. Om man direkt följer ovanstående algoritm, så måste man utföra jämförelse med flyttal. Även om detta ofta fungerar så är det ändå en källa till oro. Divisionen kan ha givit upphov till medelvärden som 5.9999999, vilket felaktigt tolkas som mindre än 6. I det här fallet är lösningen enkel. Räkna aldrig ut medelvärdena explicit utan jämför summorna istället.
#include <stdio.h>
int main(){
int na,nb,sa,sb,a[10],b[10],i,ok;
printf("Antal tal i grupp A ? ");
scanf("%d",&na);
sa=0;
for(i=0;i<na;i++) {
printf("Tal ? ");
scanf("%d",&a[i]);
sa+=a[i];
}
printf("Antal tal i grupp B ? ");
scanf("%d",&nb);
sb=0;
for(i=0;i<nb;i++) {
printf("Tal ? ");
scanf("%d",&b[i]);
sb+=b[i];
}
for(i=0;i<na;i++) if(a[i]*na<sa && a[i]*nb>sb) { //Om a[i] < sa/na och a[i] > sb/nb
printf("Flytta %d till B.\n",a[i]);
return 0;
}
for(i=0;i<nb;i++) if(b[i]*nb<sb && b[i]*na>sa) { //Om b[i] < sb/nb och a[i] > sa/na
printf("Flytta %d till A.\n",b[i]);
return 0;
}
printf ("Omöjligt!\n");
return 0;
}
Nästan samma program, fast i ruby
#!/usr/bin/env ruby
puts "Antal tal i grupp A?"
@antal_i_a = gets.to_i
@a, @b, @bool = [], [], true
until @antal_i_a == 0
@a.push gets.to_i
@antal_i_a -= 1
end
@antal_i_b = gets.to_i
until @antal_i_b == 0
@b.push gets.to_i
@antal_i_b -= x1
end
@a_medel, @b_medel = 0, 0
@a.each { |e| @a_medel += e.to_i }
@b.each { |e| @b_medel += e.to_i }
@a_medel /= @a.length
@b_medel /= @b.length
@a.each { |e| if e < @a_medel && e > @b_medel
puts "Flytta #{e} till B."
@bool = false
end}
@b.each { |e| if e < @b_medel && e > @a_medel
puts "Flytta #{e} till B."
@bool = false
end}
puts 'Omöjligt' if @bool
Python
avg = [0, 0]
def ReadInput(nSize, nIndex):
x = [input("Tal ? ") for i in range(nSize)]
avg[nIndex] = sum(x) / nSize
return x
def CalcMove(x, avg1, avg2):
for i in x:
if i < avg1 and i > avg2:
return i
group = [input("Antal tal i grupp A ? ")]
a = ReadInput(group[0], 0)
group.append(input("Antal tal i grupp B ? "))
b = ReadInput(group[1], 1)
a = CalcMove(a, avg[0], avg[1])
b = CalcMove(b, avg[1], avg[0])
if a:
print "Flytta talet "+repr(a)+" till B."
elif b:
print "Flytta talet "+repr(b)+" till A."
else:
print "Impossible."
Lösningsexempel i Java.
import java.util.*;
public class WillRoger
{
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Antal tal i grupp A: ");
int nrA = scan.nextInt();
int [] talA = new int [nrA];
int summaA = 0;
for(int i = 0; i<nrA; i++)
{
System.out.print("Tal: ");
talA[i] = scan.nextInt();
summaA += talA[i];
}
System.out.print("Antal tal i grupp B: ");
int nrB = scan.nextInt();
int [] talB = new int [nrB];
int summaB = 0;
for(int i = 0; i<nrB; i++)
{
System.out.print("Tal: ");
talB[i] = scan.nextInt();
summaB += talB[i];
}
String svar = "Omöjligt";
//Medelvärde i A = summaA/nrA.
//Medelvärde i B = summaB/nrB.
//Jämförelsen talA[i]<summaA/nrA som bör undvikas p.g.a. avrundningsfel
// är ekvivalent med jämförelsen talA[i]*nrA<summaA som är att föredra.
for(int i = 0; i<nrA; i++)
{
if(talA[i]*nrA<summaA && talA[i]*nrB>summaB)
{
svar = "Flytta talet " + talA[i] + " till B.";
}
}
for(int i = 0; i<nrB; i++)
{
if(talB[i]*nrB<summaB && talB[i]*nrA>summaA)
{
svar = "Flytta talet " + talB[i] + " till A.";
}
}
System.out.println(svar);
}
}
Lösning i Haskell.
-- WillRoger
module Main where
import IO
import Data.Ratio
main = do {
putStr "Antal tal i grupp A ? ";
n1 <- getLine;
a <- readTal (read n1);
putStr "Antal tal i grupp B ? ";
n2 <- getLine;
b <- readTal (read n2);
putStrLn $ svar a b
}
readTal :: Int -> IO [Integer]
readTal 0 = return []
readTal to = do {
putStr ("Tal ? ");
tal <- getLine;
rest <- readTal (to-1);
return $ (read tal):rest
}
svar :: [Integer] -> [Integer] -> String
svar a b | okies /= [] = "Flytta talet " ++ (show $ head okies) ++ " till B."
| calis /= [] = "Flytta talet " ++ (show $ head calis) ++ " till A."
| otherwise = "Omojligt!"
where
mA = (%) (sum a) (fromIntegral $ length a)
mB = (%) (sum b) (fromIntegral $ length b)
okies = [x | x <- a, y <- [(%) x 1], y<mA, y>mB]
calis = [x | x <- b, y <- [(%) x 1], y>mA, y<mB]