Вопросы по олимпиаде

[FsGaCh]

Ешё несколько задачек (Эти я выполнил заранее, вот почему тут не использовал ваш метод):
1)Дано натуральное число N и массив из N целых чисел. Найти номер последнего максимального элемента этого массива.
Формат входных данных
В первой строке задано одно число N (1 <= N <= 10000). В следующей строке задано N целых чисел, разделенных одним пробелом, – элементы массива.
Формат выходных данных
Выведите номер последнего максимального элемента массива

Мой вариант:

n = int(input())
numbers = input()
nums = numbers.split()
for i in range(len(nums)):
    nums[i] = int(nums[i])
max = sorted(nums)[::-1][0]
nums = nums[::-1]
for i in range(len(nums)):
    if nums[i] == max:
        print(len(nums)-i-1)
        break

2)Дано натуральное число N и массив из N целых чисел. Поменять местами первый минимальный элемент среди положительных с последним максимальным элементом среди отрицательных.
Формат входных данных
В первой строке задано одно число N (1 <= N <= 10000). В следующей строке задано N целых чисел, разделенных одним пробелом, – элементы массива.
Формат выходных данных
В первой строке выведите число N. Во второй строке выведите N чисел, разделенных одним пробелом, – измененный массив.

Мой вариант:

n = int(input())
numbers = input()
nums = numbers.split()
for i in range(len(nums)):
    nums[i] = int(nums[i])
min = 1111111111111111111111111111111111111111111111111
for i in nums:
    if i < min and i > 0:
        min = i
print(min)
max = -11111111111111111111111111111111111111111111111111111111111
for i in nums:
    if i > max and i < 0:
        max = i
print(max)
imin = 0
imax = 0
for i in range(len(nums)):
    if nums[i] == min:
        imin = i
        break
for i in range(len(nums)):
    if nums[i] == max:
        imax = i
nums[imax] = min
nums[imin] = max
for i in nums:
    print(i, end=' ')

3)Дано натуральное число N и массив из N целых чисел. Поменять местами первый минимальный элемент с последним максимальным элементом.
Формат входных данных
В первой строке задано одно число N (1 <= N <= 10000). В следующей строке задано N целых чисел, разделенных одним пробелом, – элементы массива.
Формат выходных данных
В первой строке выведите число N. Во второй строке выведите N чисел, разделенных одним пробелом, – измененный массив.

Мой вариант:

n = int(input())
numbers = input()
nums = numbers.split()
for i in range(len(nums)):
    nums[i] = int(nums[i])
min = 1111111111111111111111111111111111111111111111111
for i in nums:
    if i < min:
        min = i
max = -11111111111111111111111111111111111111111111111111111111111
for i in nums:
    if i > max:
        max = i
imin = 0
imax = 0
for i in range(len(nums)):
    if nums[i] == min:
        imin = i
        break
for i in range(len(nums)):
    if nums[i] == max:
        imax = i
nums[imax] = min
nums[imin] = max
print(max, min)
for i in nums:
    print(i, end=' ')

(Да, последние 2 задачи получились очень грамосткими)

[BDA]

1)

n = int(input())
nums = list(map(int, input().split()))[::-1]
print(len(nums) - nums.index(max(nums)) - 1)

2) Сработает, если подходящие для обмена числа есть в массиве.

n = int(input())
nums = list(map(int, input().split()))
min_positive = min(i for i in nums if i > 0)
max_negative = max(i for i in nums if i < 0)
min_index = nums.index(min_positive)
max_index = len(nums) - nums[::-1].index(max_negative) - 1
nums[min_index] = max_negative
nums[max_index] = min_positive
for i in nums:
    print(i, end = ' ')

3)

n = int(input())
nums = list(map(int, input().split()))
min_index = nums.index(min(nums))
max_index = len(nums) - nums[::-1].index(max(nums)) - 1
nums[min_index], nums[max_index] = nums[max_index], nums[min_index]
for i in nums:
    print(i, end = ' ')

[ViktorR]

min = 1111111111111111111111111111111111111111111111111

Такие операции - источник ошибок.
Часто ещё используют константы для min/max, зашитые в языке. Это тоже неправильно.
В подобных случаях следует выбрать, например, первый элемент массива и положить, что он и есть минимальный/максимальный.
Далее, сравнивая с другими элементами ищем настоящий min/max.

[FsGaCh]

2 задания одно смог выполнить, но сомневаюсь в ответе, другое не смог выполнить:
1)У нас имеется N камней с весами w1, w2, w3,…, wn. Написать программу, которая распределит эти камни на две кучи так, чтобы разность весов этих двух куч была бы минимальной.
Формат входных данных
В первой строке задано одно число N (1 <= N <= 20). В следующей строке задано N целых чисел w1, w2, w3,…, wn, разделенных одним пробелом, – веса камней.
Формат выходных данных
В одной строке искомая минимальная разность весов двух куч.

Для этого у меня нету своего варианта.

2)Дано целое число N. Требуется найти минимальное целое положительное число M, произведение цифр которого равно N.
Формат входных данных
В первой строке задано одно число N (0 ≤ N ≤ 109).
Формат выходных данных
Вывести число M. Если такого числа не существует – вывести -1.

Мой вариант:

n = int(input())
num = 0
while True:
    ints = []
    x = 1
    for i in str(num):
        ints.append(int(i))
    for i in ints:
        x = x * i
    if x == n:
        print(num)
        break
    num += 1

[BDA]

1) Ничего лучше перебора всех вариантов раскладки камней на 2 кучи не пришло в голову:

n = int(input())
w = list(map(int, input().split()))
s = sum(w)
min_diff = s
for i in range(1, 1 << (n - 1)):
    s1 = 0
    for j in range(n - 1):
        if (i >> j) & 1:
            s1 += w[j]
    tmp_diff = abs(s - 2 * s1)
    if tmp_diff < min_diff:
        min_diff = tmp_diff
print(min_diff)

2) В вашем решении нет вывода -1. Не уверен, что всегда будет минимальное число:

n = int(input())
if n == 0:
    print(-1)
    exit()
m = ''
for i in [9, 8, 7, 6, 5, 4, 3, 2]:
    count = 0
    while n % i == 0:
        count += 1
        n //= i
    m = str(i) * count + m
if n != 1:
    print(-1)
    exit()
print(m)

[challengerr]

Задача 2.Лёша сидел на лекции. Ему было невероятно скучно. Голос лектора казался таким далеким и незаметным...
Чтобы окончательно не уснуть, он взял листок и написал на нём свое любимое слово. Чуть ниже он повторил своё любимое слово, без первой буквы. Ещё ниже он снова написал своё любимое слово, но в этот раз без двух первых и последней буквы.
Тут ему пришла в голову мысль — времени до конца лекции все равно ещё очень много, почему бы не продолжить выписывать всеми возможными способами это слово без какой-то части с начала и какой-то части с конца?
После лекции Лёша рассказал Максу, как замечательно он скоротал время. Максу стало интересно посчитать, сколько букв каждого вида встречается у Лёши в листочке. Но к сожалению, сам листочек куда-то запропастился.
Макс хорошо знает любимое слово Лёши, а ещё у него не так много свободного времени, как у его друга, так что помогите ему быстро восстановить, сколько раз Лёше пришлось выписать каждую букву.
Входные данные
На вход подаётся строка, состоящая из строчных латинских букв — любимое слово Лёши.
Длина строки лежит в пределах от 5 до 100 000 символов.
Выходные данные
Для каждой буквы на листочке Лёши, выведите её, а затем через двоеточие и пробел сколько раз она встретилась в выписанных Лёшей словах (см. формат вывода в примерах). Буквы должны следовать в алфавитном порядке. Буквы, не встречающиеся на листочке, выводить не нужно.
Примеры тестов
Входные данные
hello
Выходные данные
e: 8
h: 5
l: 17
o: 5
Входные данные
abacaba
Выходные данные
a: 44
b: 24
c: 16
Примечание
Пояснение к первому примеру. Если любимое Лёшино слово — "hello", то на листочке у Лёши будут выписаны следующие слова:
•"hello"
•"hell"
•"ello"
•"hel"
•"ell"
•"llo"
•"he"
•"el"
•"ll"
•"lo"
•"h"
•"e"
•"l"
•"l"
•"o"
Среди этих слов 8 раз встречается буква "e", 5 раз — буква "h", 17 раз — буква "l" и 5 раз буква "o".

import sys
n = sys.stdin.read()
a = len(n)-1
#print ('str: ', n[0:a])
#print ('len: ', a)

l1 = list()
#print(len(l1),'\n')
l2 = list()
#print(len(l2),'\n')


i = 0
j = a
step = 1
while j > 0:
    while i < j: 
        k = i
        l = j
        while k < j:
            #print(n[k]) 
            if  len(l1) == 0:
                l1.append(n[k])
                l2.append(1)
            else:
                ip = 0
                m = 0

                while m < len(l1):
                    if l1[m] == n[k]:
                        l2[m] = l2[m] + 1
                        ip = 1 
                    m = m + 1

                if ip == 0:
                    l1.append(n[k])
                    l2.append(1)                
            
           
            k = k + 1
                       
        #print (i, '\t', j, '\t', n[i:j])
        i = i + 1
    j = j - 1
    i = 0


m = 0
while m < len(l1):
    print (l1[m], ' ', l2[m])
    m = m + 1

Нормально? Или можно лучше?

[BDA]

Сообщение от challengerr

можно лучше?

Можно:

s = input()
n = len(s)
d = {}
for i, k in enumerate(s):
    d[k] = d.get(k, 0) + (i + 1) * (n - i)
for k, c in sorted(d.items()):
    print("%s: %d" % (k, c))

[ViktorR]

Длина строки лежит в пределах от 5 до 100 000 символов.

Если на написание одного символа тратилось 0.5 с, то это около 14 часов безвылазной работы.
Ничего себе любимое словечко?
А ещё и выписать все комбинации.

[challengerr]

Сообщение от BDA

Можно:

s = input()
n = len(s)
d = {}
for i, k in enumerate(s):
    d[k] = d.get(k, 0) + (i + 1) * (n - i)
for k, c in sorted(d.items()):
    print("%s: %d" % (k, c))

Извините, ваш код совсем не понимаю...
Я только начал изучать питон....
d какого типа?


Нашел сайт, где решают эти задачи ( informatics.mccme.ru ).
Мое решение не прошло ни одного теста.

[BDA]

d типа словарь. Ваше решение не соблюдает требования к выходным данным (нет двоеточия, не в алфавитном порядке).