- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
// Задача "Сложный XOR", олимпиада ACM контестер Украина.
// Есть множество натуральных чисел от 0 до N. Играют двое игроков. Сначала один убирает из множества число,
// потом второй. Если в множестве есть (осталось) число, равное побитовому XOR двух выбранных чисел, убирают
// и его (в условии задачи битность числа не указана, но сказано, что 1 <= N <= 32). Играют пока в множестве
// есть числа. Проигрывает тот, который не может совершить ход (на ком кончились числа).
// Ввод - число N, вывод - игрок, который выиграл (оба игрока придерживаются выгодной стратегии).
#include <iostream>
#include <time.h>
using namespace std;
int main() {
int n;
cin >> n;
// Это очевидно
if (n==1) {
cout << "First";
return 0;
}
if (n==2) {
cout << "Second";
return 0;
}
// Это было в примере
if (n==3) {
cout << "First";
return 0;
}
int s = clock() % 2; // rand() не работал чето :)
if (s==0) {
cout << "First";
} else {
cout << "Second";
}
return 0;
}
Follow us!
Но нас не остановить!
<cstdlib> же!
в такую игру не интересно играть, следовательно - и программировать это г.
1. невзлюбил такие олимпиады потому что залог успеха в них - не творческое мышление, а заучивание книжек с алгоритмами (которые были придуманны еще в эпоху перфокарточек (чтобы меньше оных надо было) или вообще счета в столбец). Школьники и некоторые студенты, в меру непонимания, что такое тру-программирование, с удовольствием выстукивают эти задачи на паскале (да-да, паскаль обязателен, не факт что задачи, скомпиленные на си, выдадут результат, сопоставим с эталонным в тестах) с чувством особо
2.
отвечу всем и много. накипело, извините.
Я как раз и невзлюбил такие олимпиады, потому что залог успеха в них - не творческое мышление, а заучивание книжек с алгоритмами (которые, к слову, были придуманны еще в эпоху перфокарточек (чтобы меньше оных надо было) или вообще счета в столбец). Школьники и некоторые студенты, в меру непонимания, что такое тру-программирование, с удовольствием выстукивают эти задачи на паскале (да-да, турбо(!)паскаль обязателен, не факт что задачи, скомпиленные на си, выдадут результат, сопоставим с эталонным в тестах) да еще с чувством особой элитарности.
Я больше скажу. Большинство этих задач подразумевает написание двух-трех строчек vip-кода (анти-говнокода :) с какой-то бешенной рекурсией и на одной формуле, с которых ничего не очевидно, но зато оно укладывается и в лимит времени, и памяти. К слову, эти синтетические лимиты на то и придуманны, чтобы задача решалась единственным шаблонным способом. Все делается на скорость, так что обычно все пишется в main, верх крутизны - в отдельную функцию в глобальном нэймспейсе. Я сам на этих олимпиадах в школе сидел и должен был год после них лечиться нормальными языками (вообще не признавал ООП).
Насчет <cstdlib> и <ctime>... не знал, не сишник я, но писать на турбопаскале это убого :)
А дело здесь, да, либо в невероятном везении, либо в том, что авторы сами не знали решения и сделали тесты только на первые три значения. Мы ничего не выиграли (да и пришли просто постебаться, что удалось); если бы жюри посмотрело решения, им было бы о чем задуматься.
после них лечиться нормальными экскрементами (вообще не признавал копрофагию)
пардон, как алгоритм зависит от ЯП? если прога на Си выдает не тот результат, что прога на Паскале - очевидно, что вы реализовали разные алгоритмы.
а требование к ЯП на олимпиадах, это всего-то затем, что бы:
1. экзаменаторы, знающие только этот ЯП, поняли программу
2. все конкурсанты были бы поставлены в равные условия (например, вдруг вы воспользуетесь стандартной библой другого языка и поэтому, естественно, покажете лучшие результаты)
а об стандартных библиотеках, считается, участник вообще не должен догадываться. если в задаче написано - дано n целых чисел (1 <= n <= 100000, n разный от задачи до задачи), то участник должен сделать массив из 100000 интов (вместо списков, векторов...) Нет, оно не запрещено парсером, просто предполагается, что предел уровня участника - это ввод и вывод в std, написание метода и рекурсия. Зато зубрежка > мастерство. Изящное (книжное) решение приветствуется.
Короче говоря, олимпиады с алгоритмического программирования имеют очень мало общего с настоящим программированием. Очень жаль, что школьники, будучи уверенными и накормленными обещаниями, мол, это престижно и вы станете венцом программерской элиты, верят и тратят время на изучение всего того, что давно скрыто в движках и стандартных библиотеках (поиск пути, сортировка...), в то же время стараясь сделать программу побыстрее а не читабельнее, порождая тонны вип-кода. а еще хуже, что этим занимаются взрослые люди (которые, наверное, не смогли освоить современные подходы к программированию, или не могут смириться со стремительным повышением уровня абстракции программ). Надеюсь, у Вас там олимпиады лучше.
Вот так приходится делать компромисс между хорошим кодом (попутно регулируя степень тщательности проектирования) и собственной репутацией.
Извините, тоже накипело.
управленец при принятии решения руководствуется в основном затратами на разработку - их нужно минимизировать ("быстрее, быстрее"), т.к. от этого зависит его доход. будущее проекта - ну это ж будет когда-нибудь - типа там и посмотрим - может и так нормально будет, и вообще это проблема программистов - пусть они и думают.
как вообще можно сравнить участников, имея в распоряжении всего-лишь 6-8 часов?
отсюда и получаем задания, рассчитанные на 1-2 часа работы.
В производстве ПО цель совсем иная - не понять кто круче, а использовать все ресурсы (в смысле весь штат программистов) оптимальным образом.
Соответственно, опыт олимпиад мало годится для производства ПО.
согласитесь же, знание исторических алгоритмов не поможет, если нужно реализовать класс для обмена сообщениями через xmpp, ну или даже регистрацию пользователей на сайте.
а что верить - не верить - это известный факт.
poweroff; sleep 5; poweron &
???
тёлки и всё такое
программирование в длину
программирование в ширину
с шайбой, с мячом, тысячи их!
Мышление - оно есть первые несколько раз. Дальше задачи повторяются. Когда в школе, или на первых курсах, особо нечего делать было, конечно, для развития было интересно походить. причем не готовясь - что смог, то решил. и занимал в общем-то хорошие места.
Алгоритмы... думал, где же они применяются в явном виде. Максимум - навигационное ПО. А так, оно давно реализованно все. ХХЫ-век, энкапсуляция :)
Немного не в тему, но... Перед собственно олимпиадой идет выступление организаторов. Выходит на трибуну чел, который тоже занял золото в ЧМ этого АСМ-а (работает организатором олимпиад в регионе), так вот, выходит он и пишет на доске: Google Code Jam - $15000; Russian _какой-то_ Cup - $10000; _еще_какая_то_олимпа_ - $15000. на что его спрашивают, а АСМ сколько дает?
Ответ был шедевральным: "АСМ ничего не дает. АСМ это престиж."
Или задача - дано число n, вычислить, во сколько бит оно поместится. пишу ceil(ln(n)/ln(2)) - валится. из-за точности флоата, как потом сказали. эталонное решение - перебор!
for(r = 0; n > 0; r ++) n = n >> 1;
какой тут перебор?
когда я спросил координатора, тоже одного из тех продвинутых организаторов, почему с логарифмами падает, он сам посоветовал делать перебором. сработало даже.
а со сдвигом отличное решение. не допер.
Да.
> Вот это и есть засветка одного тестового варианта.
И что? В реале тоже тестер будет говорить "программа валится, а где - светить не буду".
> А про остальные вы что хотите узнать?
Если вариант ничем не выделяется, то так и написать - "неверный ответ на типичном тесте". Чтобы ответ был похож на реакцию тестера в реальной жизни.
Про rand() нам тоже говорили, правда, сказали, может проканать раза с десятого. Мы не верили... )
Вот как раз учёт граничных и вырожденных случаев — то, что близко к реальным задачам. Потому, что программа может работать на определённом тестовом наборе и сломаться на других реальных данных. Нужно не надеяться на авось, а иметь некоторые гарантии насчёт худшего случая (а худшие случаи не так редки, как кажется).
А тут - есть тесты, можно проверять на них наличие ошибок. А для отладки - уж будьте любезны свой тест написать. Может вам тестер ещё и патч должен прислать с исправлением ошибки?
так вот наша реализация не прошла ни одного теста, но по результатам апелляции нам дали полный балл за эту задачу - мы лишь перепутали вывод 0 и 1. а в задаче не было конкретизировано. Автор задачи решил, что она решена полностью.
Очень многое зависит от организаторов олимпиад.
А вообще, пора наверное прекращать нашу здесь специальную олимпиаду в комментариях =) Разные и, главное, личные взгляды - это хорошо.
int s = clock() % 2;
делала то, что s всегда было равное 0. Ваш код оказался верным. Он говорит всегда что выиграл второй кроме случая n==1 и n==3. Совпадение.
Помоему контест был неплохой, и там был мнoго разноплновых задач, интересних задач, видемо благодаря тому, что готовила контест топовая команда с Симферополя AKAI. Это была одна из самых простых задач на заметить закономерность, догадатся.
Вопрос к автору: и сколько задач вы решили с 15 что там были за 5 часов?
Это задача была дана чтобы с 158 команд(у моем регионе) 28 не поехали домой с 0 из 15 решенных задач. Но даже с такой задачей это случилось. вот пруфлинк http://olymp.sumdu.edu.ua/standings.php.
П.С. это была задача N. ее решили 7 команд. задумайтесь лучше о уровне преподавания программирования в наших университетах.
ступидент детектед
Как я уже говорил, я не ставил себе цель подготовиться к олимпиаде. Я пришел и увидел, что в алгоритмическом я ноль, в чем охотно признаюсь. Тем не менее, сейчас соображаю над неплохим, на мой взгляд, проектом, и незнание олимпиадных мне как-то не мешает.
Насчет перебора. Вы перебрали все 32 варианта? И сколько времени это заняло? Или вы наперед знали, какие подходы к подобным задачам? Я руками проверил вариант 4 и решил, что зависит от четности (как в Простом ХОR'e). Для того, чтобы проследить такую закономерность, нужно перебрать хотя бы половину значений.
Встречный вопрос (не из злости, просто не ожидал здесь напороться на участника :). А сколько решили вы? И на каком языке писали?
Насчет уровня. Нам, если на то пошло, не обязаны объяснять алгоритмы олимпиадных задачек. У нас на первом курсе было какое-никакое, а все же ООП, а в начале второго мы индивидуально писали веб-порталы (тоже, какие-никакие, но писали, и это лично мне принесло больше пользы). (Нет, конечно, смешно, что после этого на третьем курсе нам будут читать школоbundle - "вёрд", эксель и фотошоп)
P.S. Ну так если у нас получился define clock() 0, то теперь листинг 6381 становится тру-говнокодом :)
уже здесь появлялся, говноусловия допускали решение брутом, что вобщем-то и не удивительно, т.к.:
"Генеральный спонсор — ВКонтакте"