Вт, 24.10.2017, 01:17
Форум інформатиків України
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Вітання на форумі
Незнайомець
Вітаємо на форумі,
Незнайомцю!

   
зареєструйтесь
Перед реєстрацією обов’язково прочитайте:
Оновлення Учасники Пошук
Особисті повідомлення
Видавництво ’’Аспект’’ Видавництво

Сторінка 3 з 3«123
Модератор форуму: Ktara, Bandalak, НІКОЛЯ, volevikt 
Форум інформатиків » РОЗДІЛ I: ІНФОРМАТИКА, ПРОБЛЕМИ, ОБГОВОРЕННЯ, ВИРІШЕННЯ » 1.11 Змагання, конкурси, олімпіади » олімпіада 2009
олімпіада 2009
silva Дата: Вт, 15.12.2009, 13:54 | Повідомлення № 1
Новий користувач
Повідомлень: 8
Нагороди: 0
Рейтинг: 0
У кого є завдання олімпіади обласної 2009 року? А також пропоную залишати в даній темі розв'язки з олімпіад з минулих років! Це буде корисно для всіх!

[admin]Шановні форумчани!!!!!
Повідомлення, які не відповідають темі або несуть некорисний зміст будуть видалятись без попередження!!!
Bandalak Дата: Чт, 24.12.2009, 22:02 | Повідомлення № 31
Лідер форуму
Повідомлень: 5437
Нагороди: 37
Рейтинг: 247
Quote (vitert)
А по-друге все ж залишаюсь при своїй думці у вас через одиничку на межі розрядів рано буде переходить до наступного розряду, тобто для 62 буде 6 а для 63 уже 7 хоча 7 починається з 64.

vitert, чого тут гадати. Запустіть мою програму в середовищі і протестуйте. Ви здивуєтеся, але вона працює без помилок! Я не сперечаюся, що можна і ншим способом написати, можливо навіть простішим. Але в моєму варіанті логічних помилок немає. Все відлагоджено, все працює!
vitert Дата: Чт, 24.12.2009, 23:06 | Повідомлення № 32
Тут живе...
Повідомлень: 174
Нагороди: 1
Рейтинг: 22
Quote (Bandalak)
vitert, чого тут гадати. Запустіть мою програму в середовищі і протестуйте. Ви здивуєтеся, але вона працює без помилок! Я не сперечаюся, що можна і ншим способом написати, можливо навіть простішим. Але в моєму варіанті логічних помилок немає. Все відлагоджено, все працює!

Не довіряйте на 100% машинам. Якщо ваша програма працює 100% використовуєте TP, якщо протестуєте свою прогу в Free Pascal то побачите помилку про яку я писав.
Причина зрозуміла. Якщо знайти значення виразу trunc(ln(n+1)/ln(2)) для n=63 в цих двох середовищах то стане зрозуміло, що в TP логарифм 64 за основою 2 менше 6.
Bandalak Дата: Чт, 24.12.2009, 23:13 | Повідомлення № 33
Лідер форуму
Повідомлень: 5437
Нагороди: 37
Рейтинг: 247
Quote (vitert)
Якщо ваша програма працює 100% використовуєте TP

Дійсно так. Мабуть ці середовища використовують зовсім різні алгоритми знаходження логарифма. Різниця не велика, але вона стає критичною при відкиданні цілої частини числа. ТР дає результат при наближенні до чисел 4, 8, 16, ... трошки менший від цілого, а Фрее Паскаль - трошки більший! Тому то і така петрушка!
Newbie Дата: Пт, 25.12.2009, 09:22 | Повідомлення № 34
Хелпер
Повідомлень: 1412
Нагороди: 9
Рейтинг: 91
Quote (Bandalak)
ці середовища використовують зовсім різні алгоритми

на районній олімпіаді цього року цілком випадково виявили, що програми в Паскалі і Алго дають різний результат проходження тестів:
написана на Алго програма з використанням integer працює для великих чисел (до 2147483647), тоді як в Паскалі - обмеження у 32768.
написана на Паскаль програма просто не запускалась в Алго без попереднього обнулення змінних-лічильників, тоді як в Паскалі працювала ідеально.
dpi Дата: Пт, 25.12.2009, 10:36 | Повідомлення № 35
Досвідчений вчитель
Повідомлень: 1438
Нагороди: 1
Рейтинг: 39
Quote (Newbie)
для великих чисел (до 2147483647)

Это и даже long long (до 20 цифр) не есть большими (длинными) числами
Newbie Дата: Пт, 25.12.2009, 12:09 | Повідомлення № 36
Хелпер
Повідомлень: 1412
Нагороди: 9
Рейтинг: 91
Quote (dpi)
Это и даже long long (до 20 цифр) не есть большими (длинными) числами

як би їх не називали :) , тести, розраховані для Паскалівської програми, на числа наприклад до 1000000, в Алго проходять без жодних додаткових маніпуляцій чи записів, тоді як в середовищі Паскаля такий тест не пройде. тобто один і той же код - при перевірці в Паскаль дає умовно 5 балів, при перевірці в Алго - 50
Nevirkovets Дата: Пт, 25.12.2009, 12:54 | Повідомлення № 37
Написав MifTests
Повідомлень: 266
Нагороди: 0
Рейтинг: 12
Допоможіть знайти алгоритм розв'язку (ідею!!!) задачі
Перестановки рядів (50 балів)

Задана квадратна таблиця A розміром N*N (1<=N<=100), яка містить цілі додатні числа. Перевірити, чи можна із рядків таблиці A шляхом їх перестановки побудувати нову таблицю B, діагональні елементи якої будуть впорядкованими по зростанню значень:
b[1, 1] < b[2, 2] < … < b[N-1, N-1] < b[N, N].
Якщо така перестановка можлива, то вказати номери тих рядків таблиці A, які в таблиці B можуть бути першими. Якщо ж такої перестановки рядків для заданої таблиці A не існує, то вивести відповідне повідомлення.

Вимоги до програми. Програма повинна зчитувати вхідні дані із файлу TASK3.DAT. В першому рядку цього файлу вказується ціле число – кількість контрольних тестів. На початку кожного тесту записане ціле число N – розмірність таблиці A. В наступних N рядках міститься по N цілих чисел, розділених пропусками, – елементи таблиці A. Дані кожного окремого тесту починаються з нового рядка.
Результат виконання програми повинен записуватися у вихідний файл TASK3.REZ. Якщо для чергового тесту перестановки рядків можливі, то у відповіді записується слово ТАК, після якого через пропуски перелічуються номери рядків таблиці A, які можуть бути першими у результуючій таблиці B. Якщо ж не існує жодної такої перестановки рядків, то у відповіді записується одне слово НІ. Результати окремих тестів повинні відділятися одним пустим рядком.

Приклад

TASK3.DAT TASK3.REZ

2 НІ
3
9 6 3 ТАК 3
8 5 2
7 4 1
3
4 5 6
7 8 9
1 2 3

alex Дата: Пт, 25.12.2009, 15:25 | Повідомлення № 38
Активний учасник
Повідомлень: 586
Нагороди: 1
Рейтинг: 17
Quote (Nevirkovets)
Допоможіть знайти алгоритм розв'язку (ідею!!!) задачі

Переборний варіант

Знаходим всі перестановки з n чисел
Для кожної перестановки пеевіряємо чи впорядковані діагональні елементи.
Оптимальність алгоритму n!

На даний момент більш оптимального розвязку не придумав.

dpi Дата: Пт, 25.12.2009, 15:44 | Повідомлення № 39
Досвідчений вчитель
Повідомлень: 1438
Нагороди: 1
Рейтинг: 39
Создаем функцию сортировки заданного столбца и массив m[N]
сортируем первый столбец, m[1]=min, обнуляем строку с мином, запоминаем номер строки, например k=m[1];
сортируем последующие, находим первое большее m[i-1]-го, заносим в m[i], если такового нет конец и NO иначе обнуляем стороку , откуда он родом и повторяем
YES k;


Відредаговано: dpi - Пт, 25.12.2009, 15:46
Nevirkovets Дата: Пт, 25.12.2009, 15:56 | Повідомлення № 40
Написав MifTests
Повідомлень: 266
Нагороди: 0
Рейтинг: 12
Quote (alex)
Оптимальність алгоритму n!

Ой щось мені кажеться дуууже не ефективно буде!!!!
Quote (Nevirkovets)
(1<=N<=100

На скільки то часу програма затримається ...
Причому як зробити перестановку із невідомою кількістю циклів? Щось невиходить ... можна фрагментик програми, як це було б зробити...
Quote (dpi)
сортируем первый столбец, m[1]=min, обнуляем строку с мином, запоминаем номер строки, например k=m[1]

Незавжди так буде є контр приклади
1 7 9
0 5 7
9 8 7
По вашій методиці... має бути 2 рядок стояти першим... а тут і так все правильно!!!
NataliyG Дата: Пт, 25.12.2009, 17:03 | Повідомлення № 41
Активний учасник
Повідомлень: 680
Нагороди: 2
Рейтинг: 37
Quote (Bandalak)
Та виставте тут, я думаю усім буде цікаво!

Згідна треба ділитися всім.
То є завдання районної олімпіади 2009 року з Львівської області.
Прикріплення: oL2009.doc(32Kb)
Форум інформатиків » РОЗДІЛ I: ІНФОРМАТИКА, ПРОБЛЕМИ, ОБГОВОРЕННЯ, ВИРІШЕННЯ » 1.11 Змагання, конкурси, олімпіади » олімпіада 2009
Сторінка 3 з 3«123
Пошук:


© Форум інформатиків України, 2007-2017.