Sebagai penggemar tim sepak bola ^BE paling sukses , menjelang akhir musim saya sering bertanya-tanya apakah tim favorit saya masih memiliki peluang teoretis yang tersisa untuk menjadi juara. Tugas Anda dalam tantangan ini adalah menjawab pertanyaan itu untuk saya.

Memasukkan

Anda akan menerima tiga input: tabel saat ini, daftar pertandingan yang tersisa, dan posisi tim saat ini yang kami minati.

Input 1: The meja saat ini , urutan nomor adalah saya nomor -th adalah poin yang diperoleh oleh tim saya sejauh ini. Misalnya, input [93, 86, 78, 76, 75]menyandikan tabel berikut (hanya kolom terakhir yang penting):

Input 2 : Pertandingan yang tersisa , urutan tuple di mana masing-masing tuple ( i , j ) mewakili pertandingan yang tersisa antara tim i dan j . Dalam contoh di atas, input kedua [(1,2), (4,3), (2,3), (3,2), (1,2)]berarti bahwa kecocokan yang tersisa adalah:

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

Input 3: The posisi saat ini . Dari tim kami tertarik Misalnya, masukan dari 2untuk contoh di atas berarti bahwa kami ingin tahu apakah Tottenham masih bisa menjadi juara.

Keluaran

Untuk setiap pertandingan yang tersisa dari formulir ( i , j ), ada tiga hasil yang mungkin:

• Tim saya menang: Tim saya mendapat 3 poin , tim j mendapat 0 poin
• Tim j menang: Tim i mendapat 0 poin , tim j mendapat 3 poin
• Draw: Tim i dan j keduanya mendapatkan 1 poin

Anda harus menampilkan nilai kebenaran jika ada beberapa hasil untuk semua game yang tersisa sehingga pada akhirnya, tidak ada tim lain yang memiliki poin lebih banyak dari tim yang ditentukan dalam input ke-3. Jika tidak, hasilkan nilai palsu.

Contoh : Pertimbangkan input contoh dari bagian di atas:

Input 1 = [93, 86, 78, 76, 75], Input 2 = [(1,2), (4,3), (2,3), (3,2), (1,2)], Input 3 =2

Jika tim 2memenangkan semua pertandingan yang tersisa (yaitu (1,2), (2,3), (3,2), (1,2)), ia mendapat 4 * 3 = 12 poin tambahan; tidak ada tim lain yang mendapat poin dari pertandingan ini. Katakanlah sisa pertandingan lainnya (yaitu (4,3)) seri. Maka skor akhir adalah:

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

Ini berarti bahwa kami telah menemukan beberapa hasil untuk pertandingan yang tersisa sehingga tidak ada tim lain yang memiliki poin lebih dari tim 2, sehingga output untuk input ini harus benar.

Detail

• Anda dapat menganggap input pertama sebagai urutan yang diurutkan, yaitu untuk i < j , entri ke- i sama dengan atau lebih besar dari entri ke- j . Input pertama dapat diambil sebagai daftar, string atau sejenisnya.
• Anda dapat mengambil input kedua sebagai string, daftar tupel atau sejenisnya. Atau, Anda dapat menganggapnya sebagai array dua dimensi di amana a[i][j]jumlah entri formulir (i,j)dalam daftar kecocokan yang tersisa. Misalnya, a[1][2] = 2, a[2][3] = 1, a[3][2] = 1, a[4][3] = 1 berkorespondensi dengan [(1,2), (4,3), (2,3), (3,2), (1,2)].
• Untuk input kedua dan ketiga, Anda dapat mengasumsikan pengindeksan 0 bukannya pengindeksan 1.
• Anda dapat mengambil tiga input dalam urutan apa pun.

Silakan tentukan format input persis yang Anda pilih dalam jawaban Anda.

_{Node samping : Masalah yang mendasari tantangan ini terbukti NP-lengkap dalam " Eliminasi Sepakbola Sulit Diputuskan di Bawah Aturan 3-Poin ". Menariknya, jika hanya dua poin yang diberikan untuk menang, masalahnya menjadi terpecahkan dalam waktu polinomial.}

Uji Kasus

Semua kasus uji dalam format Input1, Input2, Input3.

Benar:

• [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

Pemenang

Ini adalah kode-golf , sehingga jawaban terpendek yang benar (dalam byte) menang. Pemenang akan dipilih satu minggu setelah jawaban pertama yang benar diposting.

Haskell (Lambdabot) , 84 byte

Terima kasih kepada @bartavelle karena telah menyelamatkan saya satu byte.

Tanpa Lambdabot, tambahkan 20 byte untuk import Control.Lensditambah baris baru.

Fungsi mengambil argumennya dalam urutan yang sama seperti yang dijelaskan dalam OP, 0-diindeks. Argumen keduanya (daftar pasangan yang tersisa) adalah daftar indeks yang datar (mis. [1,2,4,1]Sesuai dengan [(Team 1 vs Team 2), (Team 4 vs Team 1)]).

Aturannya agak kabur, apakah ini diizinkan atau tidak. Jika tidak diizinkan, fungsi dapat mengambil input dalam format yang disediakan oleh contoh - daftar tupel. Dalam hal ini, tambahkan 2 byte ke skor solusi ini, karena diganti a:b:rdengan (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

Penjelasan:

Baris pertama mendefinisikan fungsi infiks !dari tiga variabel, tipe (!) :: Int -> Int -> [Int] -> [Int], yang menambah nilai pada indeks yang diberikan dalam daftar. Karena, seringkali, kode lebih mudah dipahami daripada kata-kata (dan karena sintaksis Haskell bisa aneh), inilah terjemahan Python:

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

Baris kedua mendefinisikan fungsi infiks lain ?, juga dari tiga variabel (input tantangan). Saya akan menulis ulang lebih mudah di sini:

(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

Ini adalah implementasi rekursif pencarian lengkap. Itu berulang atas daftar permainan yang tersisa, bercabang pada tiga hasil yang mungkin, dan kemudian, setelah daftar kosong, memeriksa apakah tim kami memiliki jumlah poin maksimum atau tidak. Sekali lagi dalam Python (non-idiomatis), ini adalah:

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))

Cobalah online!

^* Sayangnya, TiO tidak mendukung Lens, jadi tautan ini tidak akan benar-benar berjalan.

Microsoft SQL Server, 792 byte

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;

Fungsi mengembalikan 0 untuk hasil yang salah dan lebih dari 0 untuk yang benar.

Seluruh cuplikan:

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);

Periksa secara Online!

Python 2, 242 221 byte

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)))

Cobalah online!

Setelah lulus pertama dengan pemikiran golf dasar. Mengambil input dengan pengindeksan berbasis 0 ; uji kasus di TIO menyesuaikan untuk ini melalui fungsi F.

The product([0,1,2],repeat=len(m))iterasi mengevaluasi hasil yang mungkin lebih dasi / menang / kerugian untuk setiap pertandingan kecuali tim-of-interest (TOI) adalah bagian dari pertandingan (di mana, TOI selalu diasumsikan untuk menang).

JavaScript (ES6), 145 byte

(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())

Mengambil input skor sebagai array ( [93,86,78,76,75]), game yang akan datang sebagai array dari array 2-nilai ( [[0,1],[3,2],[1,2],[2,1],[0,1]]), dan indeks tim sebagai integer ( 1). Semuanya terindeks 0.

Cuplikan Tes

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}