1012 - aranjare - Revision history

Danciu: Pagină nouă: = Cerința = Dorel tocmai a învățat la școală despre permutări. El a reținut faptul că `n` persoane pot fi aranjate pe `n` locuri în `n!` moduri, unde . Pentru a vă pune pe voi la încercare Dorel mai alege un număr `p` și vă întreabă în câte moduri putem aranja `n` persoane numerotate de la `1` la `n` pe `n` locuri, numerotate şi ele de la `1` la n 2024-06-04T08:36:13Z Pagină nouă: = Cerința = Dorel tocmai a învățat la școală despre permutări. El a reținut faptul că <code>n</code> persoane pot fi aranjate pe <code>n</code> locuri în <code>n!</code> moduri, unde . Pentru a vă pune pe voi la încercare Dorel mai alege un număr <code>p</code> și vă întreabă în câte moduri putem aranja <code>n</code> persoane numerotate de la <code>1</code> la <code>n</code> pe <code>n</code> locuri, numerotate şi ele de la <code>1</code> la <code>n</cod... New page = Cerința = Dorel tocmai a învățat la școală despre permutări. El a reținut faptul că <code>n</code> persoane pot fi aranjate pe <code>n</code> locuri în <code>n!</code> moduri, unde . Pentru a vă pune pe voi la încercare Dorel mai alege un număr <code>p</code> și vă întreabă în câte moduri putem aranja <code>n</code> persoane numerotate de la <code>1</code> la <code>n</code> pe <code>n</code> locuri, numerotate şi ele de la <code>1</code> la <code>n</code>, astfel încât suma dintre numărul persoanei și numărul locului să fie divizibilă cu <code>p</code>? = Date de intrare = Programul citește de la tastatură numerele <code>n</code> și <code>p</code>, separate prin spații. = Date de ieșire = Programul va afișa pe ecran numărul <code>m</code>, reprezentând numărul de moduri cerut. Deoarece acest număr ar putea fi foarte mare, rezultatul se va afișa modulo <code>100019</code>. = Restricții și precizări = * <code>1 ≤ p ≤ n ≤ 100.000</code> * locurile și persoanele sunt numerotate de la <code>1</code> la <code>n</code> = Exemplu: = Intrare 8 4 Ieșire 16 = Explicație = Avem <code>8</code> persoane și <code>8</code> locuri. Persoanele <code>1</code> și <code>5</code> se pot așeza pe locurile <code>3</code> și <code>7</code> în <code>2!</code> moduri, persoanele <code>2</code> și <code>6</code> pe locurile <code>2</code> și <code>6</code> în <code>2!</code> moduri, persoanele <code>3</code> și <code>7</code> pe locurile <code>1</code> și <code>5</code> în <code>2!</code> moduri, iar persoanele <code>4</code> și <code>8</code> pe locurile <code>4</code> și <code>8</code> în <code>2!</code> moduri. În total vom avea <code>2</code> <code>4 =16</code> moduri de aranjare. == Rezolvare == <syntaxhighlight lang="python3"> MOD = 100019 def count_valid_arrangements(n, p): total_arrangements = 0 dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)] dp[1][1] = 1 for i in range(2, n + 1): for j in range(1, n + 1): current_arrangements = 0 if (i + j) % p == 0: current_arrangements += dp[i - 1][j] if i != j: current_arrangements += dp[i][j - 1] dp[i][j] = current_arrangements for j in range(1, n + 1): total_arrangements += dp[n][j] return total_arrangements % MOD def main(): n, p = map(int, input().split()) valid_arrangements = count_valid_arrangements(n, p) print(valid_arrangements) if name == "main": main() </syntaxhighlight>