Programozó versenyek

DEIK Regionális Programozó Csapatverseny, egyetemi/főiskolai kategória, 2016. december 4.

2016. december 4. 10:10 – 2016. december 4. 15:10

Vizsgák újraelosztása

Linda épp vizsgáztat. Amikor a vizsgának vége van, Linda szétosztja a dolgozatokat a hallgatók között, hogy értékeljék egymás válaszait, és adjanak rájuk egy előzetes pontszámot.

A hallgatók több különböző méretű terembe vannak elosztva. Linda az alábbi séma szerint osztja szét a dolgozatokat:

  1. Bemegy az első terembe, összeszedi az összes ott írt dolgozatot, és elhelyezi őket egy kupacba.
  2. Minden további teremben Linda levesz a kupac tetejéről annyi dolgozatot, ahányan a teremben vannak, és véletlenszerűen szétosztja őket a hallgatók között. Ezután összeszedi az abban a teremben írt dolgozatokat, és a kupac aljára rakja őket.
  3. Miután minden termet végigjárt pontosan egyszer, visszatér az első terembe, ahol szétosztja a kupacban maradt dolgozatokat.

Természetesen lényeges, hogy egyetlen hallgató se kapja meg a saját dolgozatát értékelésre, valamint hogy Linda a szétosztás közben ne fogyjon ki a dolgozatokból (azaz amikor bemegy egy terembe az első után, a kupacában legalább annyi dolgozat legyen, ahányan az adott teremben vannak). Hogy teljesülnek-e ezek a feltételek, az attól függ, hogy milyen sorrendben járja végig a termeket. Azt mondjuk, hogy a termek egy sorrendje biztonságos, ha Linda nem fogy ki a dolgozatokból, ha az adott sorrendben járja végig a termeket, és nem fordulhat elő az, hogy egy hallgató a saját dolgozatát kapja értékelésre.

A feladatod, hogy meghatározd a termek bejárásának egy biztonságos sorrendjét, vagy hogy megállapítsd, hogy nem létezik biztonságos sorrend.

A bemenet specifikációja

A bemenet a következő adatokat tartalmazza:

  • egy sort, amelyben egy n egész szám, a termek száma szerepel (2 ≤ n ≤ 30);
  • egy sort, amelyben n egész szám szerepel (s1, …, sn), ahol si az i-edik teremben lévő hallgatók számát adja meg (1 ≤ si ≤ 100 minden i-re).

A kimenet specifikációja

Ha a dolgozatokat nem lehet biztonságosan szétosztani, akkor az „impossible” szót, különben a termek bejárásának egy biztonságos sorrendjét kell a kimenetre írni a termek sorszámainak megadásával. Ha több biztonságos sorrend is létezik, akkor közülük bármelyik megadható.

1. példa bemenet

  1. 4
  2. 2 3 3 1
letöltés szöveges állományként

Az 1. példa bemenethez tartozó kimenet

  1. 2 3 4 1
letöltés szöveges állományként

2. példa bemenet

  1. 2
  2. 10 20
letöltés szöveges állományként

A 2. példa bemenethez tartozó kimenet

  1. impossible
letöltés szöveges állományként
Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.