Jako fan najbardziej udanego zespołu piłkarskiego ^BE , pod koniec sezonu często zastanawiam się, czy moja ulubiona drużyna ma jeszcze teoretyczną szansę na zostanie mistrzem. Twoim zadaniem w tym wyzwaniu jest udzielenie mi odpowiedzi na to pytanie.

Wejście

Otrzymasz trzy dane wejściowe: bieżącą tabelę, listę pozostałych meczów oraz aktualną pozycję drużyny, którą jesteśmy zainteresowani.

Wejście 1: aktualna tabela , sekwencja numerów były i numer -ty są punkty zdobyte przez zespół i tak daleko. Na przykład dane wejściowe [93, 86, 78, 76, 75]kodują następującą tabelę (ważna jest tylko ostatnia kolumna):

Wejście 2 : Pozostałe mecze , sekwencja krotek, w której każda krotka ( i , j ) oznacza pozostały mecz między drużyną i i j . W powyższym przykładzie drugie wejście [(1,2), (4,3), (2,3), (3,2), (1,2)]oznaczałoby, że pozostałe dopasowania to:

Chelsea vs Tottenham, Liverpool vs Man. City, Tottenham vs Man. City, Man. City vs Tottenham, Chelsea vs Tottenham

Wejście 3: aktualna pozycja . Zespołu jesteśmy zainteresowani Na przykład wejście2 na powyższym przykładzie oznaczałoby, że chcielibyśmy wiedzieć, czy Tottenham wciąż może zostać mistrzem.

Wynik

Dla każdego pozostałego dopasowania formularza ( i , j ) istnieją trzy możliwe wyniki:

• Drużyna i wygrywa: Drużyna i otrzymuje 3 punkty , drużyna j dostaje 0 punktów
• Drużyna j wygrywa: Drużyna i otrzymuje 0 punktów , drużyna j otrzymuje 3 punkty
• Draw: Zespół I i J zarówno dostać 1 punkt

Musisz podać prawdziwą wartość, jeśli jest jakiś wynik dla wszystkich pozostałych gier, tak że na końcu żadna inna drużyna nie ma więcej punktów niż drużyna określona w 3. danych wejściowych. W przeciwnym razie wypisz wartość fałszowania.

Przykład : Rozważ przykładowe dane wejściowe z powyższej sekcji:

Wejście 1 = [93, 86, 78, 76, 75], Wejście 2 = [(1,2), (4,3), (2,3), (3,2), (1,2)], Wejście 3 =2

Jeśli drużyna 2wygra wszystkie pozostałe mecze (tj. (1,2), (2,3), (3,2), (1,2)), Otrzyma 4 * 3 = 12 dodatkowych punktów; żadna z pozostałych drużyn nie otrzymuje żadnych punktów za te mecze. Powiedzmy, że drugi pozostały mecz (tj. (4,3)) To remis. Wtedy końcowe wyniki byłyby następujące:

 Team 1: 93, Team 2: 86 + 12 = 98, Team 3: 78 + 1 = 79, Team 4: 76 + 1 = 77, Team 5: 75

Oznacza to, że znaleźliśmy już pewne wyniki dla pozostałych meczów, dzięki czemu żadna inna drużyna nie ma więcej punktów niż drużyna 2 , więc wyniki dla tego wkładu muszą być zgodne z prawdą.

Detale

• Możesz założyć, że pierwszym wejściem jest sekwencja uporządkowana, tj. Dla i < j , i -ty wpis jest równy lub większy niż j- ty wpis. Pierwsze dane wejściowe mogą być traktowane jako lista, ciąg znaków lub tym podobne.
• Drugie wejście możesz wziąć jako ciąg, listę krotek lub tym podobne. Alternatywnie, możesz potraktować to jako tablicę dwuwymiarową, agdzie a[i][j]jest liczba wpisów formularza (i,j)na liście pozostałych dopasowań. Na przykład a[1][2] = 2, a[2][3] = 1, a[3][2] = 1, a[4][3] = 1 odpowiada [(1,2), (4,3), (2,3), (3,2), (1,2)].
• W przypadku drugiego i trzeciego wejścia można założyć indeksowanie 0 zamiast indeksowania 1.
• Możesz wziąć trzy dane wejściowe w dowolnej kolejności.

Podaj dokładny format wejściowy wybrany w odpowiedzi.

_{Węzeł boczny : problem leżący u podstaw tego wyzwania okazał się być NP-zupełny w „ Eliminacja piłki nożnej jest trudna do podjęcia na podstawie reguły 3-punktowej ”. Co ciekawe, jeśli za zwycięstwo zostaną przyznane tylko dwa punkty, problem staje się rozwiązywalny w czasie wielomianowym.}

Przypadki testowe

Wszystkie przypadki testowe są w formacie Input1, Input2, Input3.

Prawda:

• [93, 86, 78, 76, 75], [(1,2), (4,3), (2,3), (3,2), (1,2)],2
• [50], [],1
• [10, 10, 10], [],3
• [15, 10, 8], [(2,3), (1,3), (1,3), (3,1), (2,1)],2

Falsy:

• [10, 9, 8], [],2
• [10, 9, 9], [(2,3), (3,2)],1
• [21, 12, 11], [(2,1), (1,2), (2,3), (1,3), (1,3), (3,1), (3,1)],2

Zwycięzca

To jest golf golfowy , więc wygrywa najkrótsza poprawna odpowiedź (w bajtach). Zwycięzca zostanie wybrany tydzień po opublikowaniu pierwszej poprawnej odpowiedzi.

Haskell (Lambdabot) , 84 bajtów

Dzięki @bartavelle za uratowanie mi bajtu.

Bez Lambdabot dodaj 20 bajtów import Control.Lensplus znak nowej linii.

Funkcja przyjmuje argumenty w tej samej kolejności, jak opisano w OP, indeksowane 0. Drugim argumentem (lista pozostałych pojedynków) jest płaska lista indeksów (np. [1,2,4,1]Odpowiada [(Team 1 vs Team 2), (Team 4 vs Team 1)]).

Zasady są nieco niejasne, czy jest to dozwolone. Jeśli nie jest to dozwolone, funkcja może przyjmować dane wejściowe w formacie podanym w przykładach - listę krotek. W takim przypadku dodaj 2 bajty do wyniku tego rozwiązania ze względu na zastąpienie a:b:rgo (a,b):r.

(!)=(+~).element
(t?(a:b:r))s=any(t?r)[a!3$s,b!3$s,b!1$a!1$s]
(t?_)s=s!!t==maximum s

Wyjaśnienie:

Pierwszy wiersz definiuje funkcję infix !trzech zmiennych typu (!) :: Int -> Int -> [Int] -> [Int], która zwiększa wartość przy danym indeksie na liście. Ponieważ często kod jest łatwiejszy do zrozumienia niż słowa (a ponieważ składnia Haskella może być dziwna), oto tłumaczenie Pythona:

def add(index, amount, items):
    items[index] += amount
    return items

Drugi wiersz definiuje kolejną funkcję infix ?, również trzech zmiennych (wejście wyzwalające). Przepiszę to bardziej czytelnie tutaj:

(t ? a:b:r) s = any (t ? r) [a ! 3 $ s, b ! 3 $ s, (b ! 1 $ a) ! 1 $ s]
(t ? _) s = (s !! t) == maximum s

Jest to rekurencyjna implementacja wyczerpującego wyszukiwania. Powtarza się na liście pozostałych gier, rozgałęziając się na trzech możliwych wynikach, a następnie, gdy lista jest pusta, sprawdza, czy nasza drużyna ma maksymalną liczbę punktów. Ponownie w (nie-idiomatycznym) Pythonie jest to:

def can_still_win(standings, games_left, our_team):
    if games_left == []:
        return standings[our_team] == max(standings)
    team1, team2, other_games = games_left[0], games_left[1], games_left[2:]
    team1Wins, team2Wins, tie = standings.copy(), standings.copy(), standings.copy()
    team1Wins[team1] += 3
    team2Wins[team2] += 3
    tie[team1] += 1
    tie[team2] += 1
    return (can_still_win(team1Wins, other_games, our_team)
            or can_still_win(team2Wins, other_games, our_team)
            or can_still_win(tie, other_games, our_team))

Wypróbuj online!

^* Niestety, TiO nie obsługuje Obiektywu, więc ten link tak naprawdę się nie uruchomi.

Microsoft SQL Server, 792 bajtów

CREATE FUNCTION my.f(@s XML,@m XML,@ INT)RETURNS TABLE RETURN
WITH s AS(SELECT s.value('@p','INT')p FROM @s.nodes('S')s(s)),
m AS(SELECT m.value('@i','INT')i,m.value('@j','INT')j FROM @m.nodes('M')m(m)),
a AS(SELECT ROW_NUMBER()OVER(ORDER BY-p)t,p FROM s),
b AS(SELECT p+3*(SELECT COUNT(*)FROM m WHERE t IN(i,j))o FROM a WHERE t=@),
c AS(SELECT i,j,ROW_NUMBER()OVER(ORDER BY 1/0)k FROM m WHERE @ NOT IN(i,j)),
d AS(SELECT COUNT(*)u,POWER(3,COUNT(*))-1 v FROM c UNION ALL SELECT u,v-1 FROM d WHERE v>0),
e AS(SELECT v,u,v/3 q,v%3 r FROM d UNION ALL SELECT v,u-1,q/3,q%3 FROM e WHERE u>1),
f AS(SELECT v,p+SUM(IIF(t=i,r,(2-r))%3*3/2)s FROM a,c,e WHERE t IN(i,j)AND k=u GROUP BY v,t,p),
g AS(SELECT MAX(s)x FROM f GROUP BY v)SELECT SUM(IIF(o<ISNULL(x,p),0,1))f FROM a,(b OUTER APPLY g)WHERE t=1;

Funkcja zwraca 0 dla wyniku fałszywego i więcej niż 0 dla wyniku zgodnego z prawdą.

Cały fragment:

SET NOCOUNT ON;
--USE tempdb;
USE rextester;
GO
IF SCHEMA_ID('my') IS NULL EXEC('CREATE SCHEMA my');
ELSE BEGIN
  IF OBJECT_ID('my.f', 'IF') IS NOT NULL DROP FUNCTION my.f;
  IF OBJECT_ID('my.s', 'U') IS NOT NULL DROP TABLE my.s;
  IF OBJECT_ID('my.m', 'U') IS NOT NULL DROP TABLE my.m;
  IF OBJECT_ID('my.c', 'U') IS NOT NULL DROP TABLE my.c;
END;
GO
CREATE TABLE my.c( -- Test cases
  c INT PRIMARY KEY CLUSTERED CHECK(c > 0), -- Test Case Id
  n INT CHECK(n > 0), -- Current position of the team of interest
);
CREATE TABLE my.s( -- Standings
  a INT FOREIGN KEY REFERENCES my.c(c) CHECK(a > 0), -- Test cAse Id
  p INT CHECK(p > 0) -- Team pts
);
CREATE TABLE my.m( -- Matches
  s INT FOREIGN KEY REFERENCES my.c(c) CHECK(s > 0), -- Test caSe Id
  i INT CHECK(i > 0), -- Team i
  j INT CHECK(j > 0), -- Team j
  CHECK(i != j)
);
GO
INSERT my.c(c, n) VALUES (1, 2), (2, 1), (3, 3), (4, 2), (5, 2), (6, 1), (7, 2);
INSERT my.s(a, p) VALUES (1, 93), (1, 86), (1, 78), (1, 76), (1, 75),
(2, 50), (3, 10), (3, 10), (3, 10), (4, 15), (4, 10), (4, 8),
(5, 10), (5, 9), (5, 8), (6, 10), (6, 9), (6, 9), (7, 21), (7, 12), (7, 11);
INSERT my.m(s, i, j) VALUES (1, 1, 2), (1, 4, 3), (1, 2, 3), (1, 3, 2), (1, 1, 2),
(4, 2, 3), (4, 1, 3), (4, 1, 3),(4, 3, 1), (4, 2, 1), (6, 2, 3), (6, 3, 2),
(7, 2, 1), (7, 1, 2), (7, 2, 3), (7, 1, 3), (7, 1, 3), (7, 3, 1), (7, 3, 1);
GO
CREATE FUNCTION my.f(@s XML,@m XML,@ INT)RETURNS TABLE RETURN
WITH s AS(SELECT s.value('@p','INT')p FROM @s.nodes('S')s(s)),
m AS(SELECT m.value('@i','INT')i,m.value('@j','INT')j FROM @m.nodes('M')m(m)),
a AS(SELECT ROW_NUMBER()OVER(ORDER BY-p)t,p FROM s),
b AS(SELECT p+3*(SELECT COUNT(*)FROM m WHERE t IN(i,j))o FROM a WHERE t=@),
c AS(SELECT i,j,ROW_NUMBER()OVER(ORDER BY 1/0)k FROM m WHERE @ NOT IN(i,j)),
d AS(SELECT COUNT(*)u,POWER(3,COUNT(*))-1 v FROM c UNION ALL SELECT u,v-1 FROM d WHERE v>0),
e AS(SELECT v,u,v/3 q,v%3 r FROM d UNION ALL SELECT v,u-1,q/3,q%3 FROM e WHERE u>1),
f AS(SELECT v,p+SUM(IIF(t=i,r,(2-r))%3*3/2)s FROM a,c,e WHERE t IN(i,j)AND k=u GROUP BY v,t,p),
g AS(SELECT MAX(s)x FROM f GROUP BY v)SELECT SUM(IIF(o<ISNULL(x,p),0,1))f FROM a,(b OUTER APPLY g)WHERE t=1;
GO
SELECT c, f
FROM my.c
OUTER APPLY(SELECT p FROM my.s S WHERE a = c FOR XML AUTO)S(s)
OUTER APPLY(SELECT i, j FROM my.m M WHERE s = c FOR XML AUTO)M(m)
OUTER APPLY my.f(s, m, n)
ORDER BY c
OPTION(MAXRECURSION 0);

Sprawdź to online!

Python 2, 242 221 bajtów

from itertools import*
def u(S,M,t,O):
 for m,o in zip(M,O):
  if t in m:S[t]+=3
  else:S[m[0]]+=(1,3,0)[o];S[m[1]]+=(1,0,3)[o]
 return S[t]>=max(S)
f=lambda s,m,t:any(u(s[:],m,t,O)for O in product([0,1,2],repeat=len(m)))

Wypróbuj online!

Po pierwszym przejściu z podstawowym golfowym myśleniem. Pobiera dane wejściowe z indeksowaniem opartym na 0 ; przypadki testowe w TIO dostosowują się do tego za pomocą funkcji F.

product([0,1,2],repeat=len(m))Iteracja ocenia możliwe wyniki na tie / WIN / strata za każdym meczu, chyba że zespół-of-interest (TOI) jest częścią meczu (w którym, TOI jest zawsze zakłada się wygrać).

JavaScript (ES6), 145 bajtów

(s,d,t,o=[],g=(c=s,i=0)=>d[i]?[3,,0,3,1,1].map((a,j)=>(j%=2,r=j?r:[...c],r[d[i][j]]+=a,g(r,i+1))):o.push(c))=>o.some(r=>r[t]==Math.max(...r),g())

Pobiera dane wejściowe jako tablicę ( [93,86,78,76,75]), nadchodzące gry jako tablicę tablic 2-wartościowych ( [[0,1],[3,2],[1,2],[2,1],[0,1]]), a indeks zespołu jako liczbę całkowitą ( 1). Wszystko jest indeksowane na 0.

Test Snippet

let f=
(s,d,t,o=[],g=(c=s,i=0)=>d[i]?[3,,0,3,1,1].map((a,j)=>(j%=2,r=j?r:[...c],r[d[i][j]]+=a,g(r,i+1))):o.push(c))=>o.some(r=>r[t]==Math.max(...r),g())

console.log("---Truthy---")
console.log(f([93, 86, 78, 76, 75], [[0,1], [3,2], [1,2], [2,1], [0,1]], 1))
console.log(f([50], [], 0))
console.log(f([10, 10, 10], [], 2))
console.log(f([15, 10, 8], [[1,2], [0,2], [0,2], [2,0], [1,0]], 1))
console.log("---Falsy---")
console.log(f([10, 9, 8], [], 1))
console.log(f([10, 9, 9], [[1,2],[2,1]], 0))
console.log(f([21, 12, 11], [[1,0], [0,1], [1,2], [0,2], [0,2], [2,0], [2,0]], 1))

.as-console-wrapper{max-height:100%!important}