Cristina94: Pagină nouă: ==Enunţ== Algorel tocmai a avut un interviu la AlgoTech. Fiind isteţ din fire, el a reuşit să rezolve toate problemele, mai puţin una de care nu reuşeşte nicicum să se prindă cum se face. Aflând că la Iaşi are loc Concursul Urmaşii lui Moisil, s-a gândit să propună această problemă şi să ofere 100 de puncte ca recompensă celor care o rezolvă corect. Fie un şir cu N cifre asupra căruia se poate efectua operaţia swap de maxim X ori. Prin swap se înţe...

2024-03-28T08:53:39Z

Pagină nouă: ==Enunţ== Algorel tocmai a avut un interviu la AlgoTech. Fiind isteţ din fire, el a reuşit să rezolve toate problemele, mai puţin una de care nu reuşeşte nicicum să se prindă cum se face. Aflând că la Iaşi are loc Concursul Urmaşii lui Moisil, s-a gândit să propună această problemă şi să ofere 100 de puncte ca recompensă celor care o rezolvă corect. Fie un şir cu N cifre asupra căruia se poate efectua operaţia swap de maxim X ori. Prin swap se înţe...

New page

==Enunţ==
Algorel tocmai a avut un interviu la AlgoTech. Fiind isteţ din fire, el a reuşit să rezolve toate problemele, mai puţin una de care nu reuşeşte nicicum să se prindă cum se face. Aflând că la Iaşi are loc Concursul Urmaşii lui Moisil, s-a gândit să propună această problemă şi să ofere 100 de puncte ca recompensă celor care o rezolvă corect.

Fie un şir cu N cifre asupra căruia se poate efectua operaţia swap de maxim X ori. Prin swap se înţelege interschimbarea a două elemente din şir aflate pe poziţii vecine.

==Cerința==
Să se determine numărul maxim care se poate obţine din şirul cu N cifre, după efectuarea a maxim X operaţii swap.

==Date de intrare==
Fișierul de intrare bignumber.in conține pe prima linie numerele naturale N şi X separate prin exact un spaţiu, iar pe următoarea linie se află N cifre fără spaţiu.

==Date de ieșire==
Fișierul de ieșire bignumber.out va conține pe prima linie numărul maxim care se poate obţine conform cerinţei din enunţ.

==Restricții și precizări==
*1 ≤ N ≤ 1.000.000
*0 ≤ X ≤ 1.000.000.000
*Pentru 30% din teste N ≤ 5.000
*Pentru alte 20% din teste X ≤ 25.000.000

==Exemplu1==
;bignumber.in
:5 3
:14325

;bignumber.out
:41532

==Exemplu2==
;bignumber.in
:1000001 3
:12345

;bignumber.out
:Date invalide.

==Rezolvare==
<syntaxhighlight lang="python" line>
#1161 BigNumber
def maximum_number(N, X, digits):
result = list(digits)

for i in range(N):
max_index = i
for j in range(i + 1, min(N, i + X + 1)):
if digits[j] > digits[max_index]:
max_index = j

for j in range(max_index, i, -1):
if X <= 0:
break
result[j], result[j - 1] = result[j - 1], result[j]
X -= 1

return ''.join(result)

def is_valid_input(N, X, digits):
if not (1 <= N <= 1000000):
return False
if not (0 <= X <= 1000000000):
return False
if len(digits) != N:
return False
for digit in digits:
if not ('0' <= digit <= '9'):
return False
return True

def main():
with open("bignumber.in", "r") as f:
N, X = map(int, f.readline().split())
digits = f.readline().strip()

if not is_valid_input(N, X, digits):
with open("bignumber.out", "w") as f_out:
f_out.write("Date invalide.")

else:
max_number = maximum_number(N, X, digits)
with open("bignumber.out", "w") as f_out:
f_out.write(max_number)

if __name__ == "__main__":
main()
</syntaxhighlight>

1161 - Big Number - Revision history