|
OFF: Если ты по-настоящему крутой программист, прими участие в Russian Code Cup! | ☑ | ||
---|---|---|---|---|
0
Зеленый Кот
25.05.12
✎
07:51
|
Russian Code Cup — крупнейшая в России ежегодная открытая олимпиада для самых сильных программистов. Общий призовой фонд составляет 18 тыс. долларов. Предварительные этапы олимпиады проходят онлайн, а финал — в Москве. В 2012 г. соревнование пройдет уже во второй раз. В первом Russian Code Cup приняли участие более 3 000 человек.
Russian Code Cup — это вызов для тех, кто считает себя настоящим профи в программировании. Первый тур весеннего Russian Code Cup состоится 27 мая. Чтобы принять участие, нужно зарегистрироваться. http://russiancodecup.ru/ на сайте примеры задач... сдается мне абсолютное большинство одинэсников их не сделает ;) |
|||
1
0xFFFFFF
25.05.12
✎
07:53
|
(0) а на 1С можно решать? :)
|
|||
2
Wobland
25.05.12
✎
07:54
|
(1) там жестокие ограничения по времени и памяти, какая нафих 1С
|
|||
3
chelentano
25.05.12
✎
07:55
|
(0) зашёл, увидел слово "ахроматическое", испугался, вышел
|
|||
4
zak555
25.05.12
✎
07:58
|
Антипалиндром
Ограничение по времени 2 секунды Ограничение по памяти 256 мегабайт Палиндромом называют строку, читающуюся одинаково с обеих сторон. Задана строка s. Найдите ее наибольшую по длине подстроку, не являющуюся палиндромом. Формат входных данных Входные данные содержат строку s. Она состоит только из строчных букв латинского алфавита, не пуста, а ее длина не превышает 100000 символов. Формат выходных данных В выходной файл выведите ответ на задачу. Если все подстроки s являются палиндромами, выведите в выходной файл NO SOLUTION. Примеры Входные данные Выходные данные abba abb это за 2 секунды надо код написать ? |
|||
5
Зеленый Кот
25.05.12
✎
07:59
|
такая же фигня!
ну про антипалиндром я может и сделаю... а про ахроматическое да ни в жисть... |
|||
6
zak555
25.05.12
✎
08:01
|
(5) это фигня со вторых семестр вузов : дискретная математика
|
|||
7
Зеленый Кот
25.05.12
✎
08:02
|
(6) я физик и дискретной математики у меня не было ;)
|
|||
8
PuhUfa
25.05.12
✎
08:17
|
(4) 2сек на выполнение кода.
Вот то что задание неккоректное это да... Из условия не понятно, входящая строка S изначально является палиндромом целиком или этот палиндром в ней еще найти надо? Если строка S изначально вся полидром то зачем писать вообще код? Ответ будет: подстрока = Лев(S,СтрДлина(S)-1); или подстрока = Прав(S,СтрДлина(S)-1); |
|||
9
IamAlexy
25.05.12
✎
08:25
|
(8) садись два
непрошел все там корректно - страка может быть произвольная, вообще без палиндрома.. или вся быть палиндромом, или содержать гденить в серединке комбинацию aabbbbbaa |
|||
10
golden-pack
25.05.12
✎
08:39
|
(0) да да ... настоящий прог
да настоящий 1сник 10 000$ за день зарабатывает и на логане ездит. |
|||
11
golden-pack
25.05.12
✎
08:39
|
(0) + малый призовой фонд. от 100$ тыс.
|
|||
12
zak555
25.05.12
✎
08:40
|
(7) из какого вуза ?
|
|||
13
IamAlexy
25.05.12
✎
08:41
|
(12) 9 классов средней школы г. Усть Заж.пинска
|
|||
14
zak555
25.05.12
✎
08:45
|
(13) не знаю
|
|||
15
PuhUfa
25.05.12
✎
08:46
|
(9) В условии из (4) ни где не сказано что строка S "может быть произвольная, вообще без палиндрома", а в примере, там же, она является вся палиндромом. Поэтому я сразу оговорился в (8), что задание некорректно -)
Для твоего примера: zxcxcaabbbbaazerty (палидром - aabbbbaa) решение будет тоже самое что и выше: подстрока = Лев(S,СтрДлина(S)-1); или подстрока = Прав(S,СтрДлина(S)-1); так как в условии надо найти максимальную подстроку исходной строки S а не палидрома ps отдай дневник -) |
|||
16
butterbean
25.05.12
✎
08:50
|
(15) там нигде не написано, что строка S - обязательно палиндром
|
|||
17
1Сергей
25.05.12
✎
08:50
|
(15) русские буквы позабыл? :)
найти надо "Антипалиндром" |
|||
18
Xapac_2
25.05.12
✎
08:51
|
В задаче антипалиндром есть непонятки.
выходные данные: В выходной файл выведите ответ на задачу. Если все подстроки s являются палиндромами, выведите в выходной файл NO SOLUTION. Входные данные abba Выходные данные abb че такое abb? если это непалиндром подстроки, то почему он один, вить их больше ab ba abb bba или я что-то не так понял? п.с. У меня всегда так с этими олимпиадными задачами, и их условиями. |
|||
19
IamAlexy
25.05.12
✎
08:55
|
(18)ыыыы
1. ab и ba непоходят ибо они наименьшие по длинне 2. задача поставлена так "Найдите ее наибольшую по длине подстроку, не являющуюся палиндромом" то есть пример abba не имеет решения ибо там нет наибольшей по длинне строки, так как abb и bba по длинне равны - то есть ни одна из них не является "наибольшей" правильный ответ: надо вернуть исключение ибо по условию задачи не предусмотрен вариант ответа в ситуациях когда возвращать нечего :) |
|||
20
PuhUfa
25.05.12
✎
08:57
|
(17) Антипалиндром - строка не являющаяся палиндромом. неа? -)
Надо найти максимальную такую подстраку. Пример: zxclcaabbbbaazerty (палибром внутри этой строки - "aabbbbaa") максимальная подстрака не являющеяся палидромом подстрока = Лев(S,СтрДлина(S)-1); или подстрока = Прав(S,СтрДлина(S)-1); что не так? -)) |
|||
21
Xapac_2
25.05.12
✎
08:58
|
(19)Все теперь понятно. Спасибо
|
|||
22
butterbean
25.05.12
✎
08:58
|
(20) не так то, что вся этма строка не палиндром
|
|||
23
picom
25.05.12
✎
08:59
|
какие мелочи
клиент для андройда стоит 5 миллионов |
|||
24
Cube
25.05.12
✎
09:00
|
(15) Если входная строка "aaaaaaaaaaaaaaaaaaaaaaaaaaaa", то твой кон не работает...
|
|||
25
Cube
25.05.12
✎
09:00
|
+(24) кон = код
|
|||
26
zak555
25.05.12
✎
09:01
|
где функция определения палиндром или нет ?
|
|||
27
Xapac_2
25.05.12
✎
09:03
|
а вообще нужно отщипывать по одному символу слева и справа
если встретили антипалиндром то он "наибольший" и задача решене если ниче не встретили выводим нусубжект (24)можно проверить, сперва если строка вся из первого символа тогда носубжект задача решена в теории. реализовывать надо? |
|||
28
Cube
25.05.12
✎
09:04
|
(27) "а вообще нужно отщипывать по одному символу слева и справа
если встретили антипалиндром то он "наибольший" и задача решене если ниче не встретили выводим нусубжект" Это шляпа, а не решение. |
|||
29
Xapac_2
25.05.12
✎
09:06
|
(28)Почему этот алгоритм не решит задаче?
тогда какие будут ваши варианты? перебрать все возможные подстроки, но тогда за 2 сек не успееете когда строка у вас 100000 символов |
|||
30
PuhUfa
25.05.12
✎
09:06
|
Как ба я написал условие:
Есть искодная трока S длинной от 2 до 100000 символов которая может содержать палидромы. Найдите максималную подстраку палидрома которая не будет сама являться палидромом. |
|||
31
Cube
25.05.12
✎
09:08
|
(29) Хотя... Я тут подумал... Наверное я поторопился с выводами :)
|
|||
32
zak555
25.05.12
✎
09:09
|
Функция палиндром (стр)
длинаСтроки = стрДлина (стр); количество = Цел ( длинаСтроки ) / 2; Для н = 1 по количество Цикл Если Сред(Стр, н, 1) <> Сред (Стр, длинаСтроки - н + 1) Тогда Возврат Ложь; КонецЕсли; КонецЦикла; Возврат Истина; КонецФункции |
|||
33
K-5
25.05.12
✎
09:11
|
(19) abb или bba
|
|||
34
IamAlexy
25.05.12
✎
09:15
|
(33) давай упростим задачу
есть две строки: abb и bba верни пожалуйста максимальную из них по длинне |
|||
35
Креатив
25.05.12
✎
09:16
|
(34)Максимальные обе. А наибольшей, действительно нет.
Про графы задачка интересная, только она больше математическая, как мне кажется. |
|||
36
Asmody
25.05.12
✎
09:19
|
ветка показывает, что одинесники в массе своей даже задачу внимательно прочитать не могут, не говоря о том, чтобы её решить
|
|||
37
Ненавижу 1С
гуру
25.05.12
✎
09:19
|
обходим всю строку посимвольно сначала и с конца одновременно - проверяем ее на палиндром и одновременно проверяем, что не все символы одинаковые. Время О(длина строки)
случай 1. строка не палиндром - это ответ случай 2. все символы одинаковые - ответа нет случай 3. строка палиндром тогда подстрока от 2 символа до n - гарантировано не палиндром - эта подстрока ответ |
|||
38
Asmody
25.05.12
✎
09:21
|
(37) от символа 2 до n гарантировано антипалиндром, но не факт, что максимальный
|
|||
39
Ненавижу 1С
гуру
25.05.12
✎
09:22
|
(38) ну как же не факт, больше только вся строка, но она палиндром
|
|||
40
Ненавижу 1С
гуру
25.05.12
✎
09:22
|
+(37) n это последний символ строки
|
|||
41
Asmody
25.05.12
✎
09:23
|
(40) а, тогда да
|
|||
42
Ursus maritimus
25.05.12
✎
09:27
|
С полиндром хрень
?(ЭтоПолиндром(Строка),Сред(Строка,2),Строка); Куда за бабаками подходить? |
|||
43
IamAlexy
25.05.12
✎
09:28
|
(37) твой алгоритм перестает работать если палиндром в строке есть и расположен нессиметрично..
например строка вида uuuabbap |
|||
44
Ненавижу 1С
гуру
25.05.12
✎
09:28
|
(42) забыл случай, когда все символы одинаковые
и вообще ты опоздал после (37) |
|||
45
Ненавижу 1С
гуру
25.05.12
✎
09:29
|
(43) не перестанет, он выдаст
uuabbap |
|||
46
Ненавижу 1С
гуру
25.05.12
✎
09:29
|
+(45) вру uuuabbap
|
|||
47
IamAlexy
25.05.12
✎
09:30
|
(45) а да...
еще раз внимательно перечитал условие.. да все верно тупым перебором можно просто решить задачу |
|||
48
Ненавижу 1С
гуру
25.05.12
✎
09:34
|
(47) только время будет O(n^2)
|
|||
49
trad
25.05.12
✎
09:38
|
(37) А интересно в решении подобных задач допускается применение многопоточности?
Ведь исходную строку можно побить на несколько, скажем так, "орбит" и сканировать одновременно несколько пар фрагментов одновременно. "Орбита" - пара подстрок одинаковой длины равноудаленных от центра |
|||
50
Xapac_2
25.05.12
✎
10:17
|
итак
вот вам http://clck.ru/d/KH8gRJ8P184rz только в случае с abba мой алгоритм возвращает bba НО вить тоже верно? |
|||
51
Ненавижу 1С
гуру
25.05.12
✎
10:17
|
(50) нах нам ехе, ты алгоритм покажи
|
|||
52
0_Serg_0
25.05.12
✎
10:19
|
(50) локдир туда впихнул??))
|
|||
53
Xapac_2
25.05.12
✎
10:22
|
bool Palindrom(char *str)
{ char str2[10000]; int l = strlen(str); for(int i = 0;i<l;i++) str2[i] = str[l-i-1]; str2[l] = '\0'; if(strcmp(str,str2) == 0)return true; return false; } char* FindNoPalindrom(char* str) { if(strlen(str) <=1) return "NO"; if(Palindrom(str)) return FindNoPalindrom((char*)&str[1]); else return str; } int _tmain(int argc, _TCHAR* argv[]) { while(1) { cout<<endl; cout<<"Input String"<<endl; char str[10000]; cin>>str; if(strcmp(str, "-1") == 0)break; cout<<FindNoPalindrom(str); } cout<<"exit"; return 0; } |
|||
54
Xapac_2
25.05.12
✎
10:22
|
(53)Отщипывал тока первый символ. потом подумал. а надо ли последний?
|
|||
55
Ненавижу 1С
гуру
25.05.12
✎
10:26
|
(53) квадратичная зависимость времени от длины строки
|
|||
56
Xapac_2
25.05.12
✎
10:28
|
(55)что?
|
|||
57
Ненавижу 1С
гуру
25.05.12
✎
10:33
|
(56) говорю, у тебя время выполнения алгоритма O(n^2) где n - длина строки
у меня O(n) |
|||
58
Xapac_2
25.05.12
✎
10:35
|
(57)аналогичный алгоритм. почему у меня времени больше?
или где ваше решение? |
|||
59
Ненавижу 1С
гуру
25.05.12
✎
10:39
|
(58) моё в (37)
хотя нет, у вас алгоритм почти всегда быстро найдет за O(n) - кроме одинаковых строк просто это на первый взгляд из него не видно, почти зачет в общем |
|||
60
Xapac_2
25.05.12
✎
10:45
|
(59)Меня больше интересует проблема того, что
в случае с abba мой алгоритм возвращает bba. не как в примере. я вить больше чем уверен, что проверяют не люди, а они как-то программкой программки проверяют. |
|||
61
Ненавижу 1С
гуру
25.05.12
✎
10:50
|
(60) по идеи алгоритм вообще должен выдавать число
хотя тут сложности нет на проверку, думаю учли, всего три варианта: 1. либо вся строка 2. либо решения нет 3. либо одна из подстрок: откусили первый символ или откусили последний |
|||
62
Xapac_2
25.05.12
✎
10:54
|
итак переходим ко 2-й задаче.
и опять трудности в понимании условия: дано число n Найдите ахроматическое число цикла длиной n. А где взять граф? |
|||
63
Ненавижу 1С
гуру
25.05.12
✎
11:00
|
(62) Вам дано число n. Найдите ахроматическое число ЦИКЛА длиной n
то есть граф это цикл из n вершин |
|||
64
NS
25.05.12
✎
11:25
|
А чего голосовалки нет?
Задачи какие-то слишком простые, участвовать не буду - в июне в отпуске. |
|||
65
NS
25.05.12
✎
11:48
|
Длин=стрдлина(стр);
Если Длин<2 тогда возврат ложь; конецесли; перв=лев(стр,1) полиндром=1; одинсимвол=1; Для а=1 по цел(длин/2) цикл тек=сред(стр,а,1); Если тек<>сред(стр,Длин+1-а,1)) тогда полиндром=0; прервать; Иначеесли тек<>перв тогда одинсимвол=0; Конецесли; КонецЦикла; Если полиндром=0 тогда возврат стр; Иначеесли (одинсимвол=1)и(перв=сред(стр,цел(длин/2)+1,1)) тогда возврат ложь; Иначе возврат лев(стр,длин-1); КонецЕсли; // Задача явно не для олимпиад. Либо хотят устроить массовость за счет легких задач на первом туре |
|||
66
NS
25.05.12
✎
11:59
|
Вторая еще лучше - если нечетно, то выводим 3, иначе 2,
потом (a div 2) раз выводим "12", и если а нечетно, еще выводим один раз "3" |
|||
67
NS
25.05.12
✎
12:04
|
Посмотрел финальные задачи - тоже ничего сверхъественного, например задача о черепашке - просто классика динамического программирования.
|
|||
68
Ненавижу 1С
гуру
25.05.12
✎
12:36
|
(67) давай сложную
|
|||
69
NS
25.05.12
✎
12:40
|
(68) Ну в финале там уже более менее задачи.
Но непонятно зачем на первых этапах они организуют такую массовость? Надо сразу отсеивать тех у кого шансов в финале нет. А задачи в финале надо давать нестандартные, я не мастер выдумывать задачи - но задача о торте, и о черепашке - явно не первой свежести, условие остальных пока не читал. |
|||
70
Скользящий
25.05.12
✎
12:41
|
(69) Зачем отсеивать? Для многих важна не победа, а участие.
|
|||
71
Xapac_2
25.05.12
✎
12:42
|
(70)Да не будем показывать пальцем!
|
|||
72
NS
25.05.12
✎
12:43
|
(70) Потому что они позиционируются как крутое соревнование среди профи, а задачи первого тура на уровне школьной контрольной по программированию.
|
|||
73
Xapac_2
25.05.12
✎
12:45
|
(72)Ну видать задача первого тура выяснить, человек умеет вообще код писать или нет
|
|||
74
NS
25.05.12
✎
13:15
|
Выйти можно из любого отборочного. Так что буду участвовать.
|
|||
75
NS
25.05.12
✎
13:46
|
http://habrahabr.ru/company/mailru/blog/119187/
Вот тут есть примеры решений задач. |
|||
76
NS
25.05.12
✎
14:13
|
(1) http://russiancodecup.ru/rules/#rounds
3.Решением задачи является программа, написанная на одном из допустимых языков программирования: Java, Python, C/C++, C#, Perl. Проверяющая система будет использовать следующие компиляторы: •Java 6.0 •Python 3.1 •Python 2.6 •Microsoft Visual C# 2010 Express Edition •Microsoft Visual C/C++ 2010 Express Edition •GNU C/C++ MinGW 4.5 •Perl 5.10 •PHP 5.3.6 |
|||
77
NS
26.05.12
✎
01:09
|
Попробовал - что-то очень медленно у меня на JAVA пишется :(
|
|||
78
NS
26.05.12
✎
13:34
|
Что-то ветка затухла, неужели никто кроме меня не хочет попробовать свои силы?
Результаты вчерашней попытки написания на JAVA у меня - первый этап предыдущего отборочного тура - все задачи по 10 минут, последняя за час. В последней долго разбирался с работой с длинными числами в JAVA. |
|||
79
Партизан
26.05.12
✎
14:11
|
а че, ассемблер уже не котируется?
|
|||
80
NS
26.05.12
✎
14:12
|
(79) А что, бывают олимпиады на ассемблере?
|
|||
81
proger2011
26.05.12
✎
14:17
|
(0) Да ладно про полидром то че не решить, вот с графами надо разбираться.
В полидроме надо перебрать все комбинации возможных строк и проверить является ли полидромом, если не является запомнить длину и само подстроку и т.д. В результе будет самый длинный не полидром. |
|||
82
proger2011
26.05.12
✎
14:19
|
(78) Ты молодец конечно. Нам на тебя надо равняться, ты исключение из всех конфигурастов. Займись просветительской работой над конфигурастами. Расскажи с чего начать, какие книги почитать. Только не надо кнута советовать :)
|
|||
83
NS
26.05.12
✎
14:41
|
По сути это ближе к математической олимпиаде, математика которую нужно воплотить в коде.
|
|||
84
Gobseck
26.05.12
✎
15:05
|
(81)Твое решение про палиндром не зачтут, т.к. оно не уложится в ограничение по времени. Правильный подход см в (37)
|
|||
85
Зеленый Кот
26.05.12
✎
15:06
|
Кнут хороший... мне очень первый том нравится...
даже больше чем руководство по ассемблеру system 360/370 |
|||
86
NS
27.05.12
✎
10:31
|
Через полчаса старт первой квалификации.
|
|||
87
Xapac_2
27.05.12
✎
10:55
|
(86)дашь списать?
|
|||
88
NS
27.05.12
✎
10:57
|
Дам, через три часа после старта. :)
|
|||
89
NS
27.05.12
✎
13:02
|
Полностью пролетел на неумении работать со строками в JAVA.
Постоянный вылет с непонятной ошибкой, если строка только одна, причем если больше - то всё почему-то работает. В итоге первую задачу написал, а на четвертой завис. |
|||
90
NS
27.05.12
✎
13:08
|
import java.io.*;
import java.util.Scanner; public class z4 { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader( new InputStreamReader(System.in)); Scanner in1 = new Scanner(System.in); int m=in1.nextInt(); String[] s; s=new String[m+1]; for (int i=1;i<=m;i++) { s[i] = in.readLine(); }; int n=in1.nextInt(); String[] e; e=new String[n+1]; for (int i=1;i<=n;i++) { e[i] = in.readLine(); }; String ss,ss1,ss2=""; char c; int d=e[1].length(); int t=0; for (int i=0;i<d;i++) { ss1=""; for (int j=1;j<=n;j++) { ss1=ss1+e[j].substring(i,d); if (i>0) {ss1=ss1+e[j].substring(0,i);}; }; ss1=".."+ss1+".."; ss=""; for (int j=0;j<ss1.length();j++) {c=ss1.charAt(j);if (c!='.'){ss=ss+c;}else{ss=ss+"QQ";}}; //System.out.println(ss); for (int j=1;j<=m;j++) ss=ss.replaceAll("Q"+s[j]+"Q","Q"); //System.out.println(ss); ss=ss.replaceAll("Q"," ").trim(); if (ss.length()<2) {t=t+1;ss2=ss2+Integer.toString(i)+" ";}; } System.out.println(t); System.out.print(ss2); } } Почему-то вылетает, если входная строка всего одна. |
|||
91
NS
27.05.12
✎
13:10
|
При этом для квалификации было достаточно решить всего две задачи...
|
|||
92
NS
27.05.12
✎
13:15
|
Блин, не знал что replaceAll, не просто заменяет, а применяет регулярные выражения,
Иначе бы написал замену простым проходом. |
|||
93
NS
27.05.12
✎
13:22
|
Прикол, но уже на куче тестов проверил - у меня всё работает, а у них выдавала рунтайм еррор.
ЧТо-то странное... |
|||
94
NS
27.05.12
✎
14:42
|
Чемпион предыдущего года решил всего две задачи.
В четвертой задачи сами организаторы предлагают решение основанное на словаре и хеш-функции. У меня с одной задачи 371-ое место из нескольких тысяч участников. Придется сделать вторую попытку второго июля. |
|||
95
NS
27.05.12
✎
18:48
|
Бред какой-то - как я написал не читает из файла, работает только при ручном построчном вводе, а если поменять in.readLine(); в двух местах на in1.next() - то всё работает. И их тест проходит. :(
|
|||
96
mehfk
27.05.12
✎
19:45
|
(0) пора уже Mista Code Cup организовывать с присвоением победителю "Почетные 22 см"
|
|||
97
Agent00x
27.05.12
✎
19:53
|
Всю ветку не читал, Рома Печенкин будет участвовать? Как единственный профи на форуме.
|
|||
98
_Atilla
28.05.12
✎
07:29
|
(4)
Если Палиндром(s) Тогда Результат = Лев(s, n-1) или (или Сред(s, 2, )) Иначе Результат = s КонецЕсли; |
|||
99
izekia
28.05.12
✎
07:44
|
автор темы тролль
было же уже много аналогичных кодеджемов и сфера если совсем скучно |
|||
100
Gobseck
28.05.12
✎
07:52
|
(100)
|
|||
101
Зеленый Кот
28.05.12
✎
07:53
|
(96) первый приз похоже заслуженно получит NS
|
|||
102
Зеленый Кот
28.05.12
✎
07:54
|
(99) да тролль и не скрываю этого ;)
|
|||
103
izekia
28.05.12
✎
08:08
|
да я сто лет не заходил на форум, регнулся во втором этапе приму участие, если не напьюсь опять)
|
|||
104
izekia
28.05.12
✎
08:08
|
втором квалификационном раунде*
|
|||
105
Xapac_2
28.05.12
✎
08:37
|
Вопреки известной поговорке «спички детям не игрушка», один мальчик очень любит играть со спичками. Но он не балуется ими, не разжигает огонь, а решает различные головоломки. Например, он умеет приравнивать число девять к числу одиннадцать, переложив только одну спичку.
Недавно родители этого мальчика подарили ему несколько наборов, каждый из которых состоит из двенадцати спичек. Мальчик начал собирать из них различные геометрические фигуры. Он уже собрал много различных фигур, но теперь ему стало интересно: из каких наборов возможно склеить каркас параллелепипеда при помощи двенадцати спичек из набора и клея? Ломать спички нельзя и ни одна из спичек не должна выступать за каркас. Ваша задача состоит в том, чтобы по известным длинам спичек для каждого набора проверить, можно ли из них склеить каркас параллелепипеда. итак мой вариант решения: 1) помещаем числа в массивчик 2) сортируем числа 1 1 1 1 2 2 2 2 3 3 3 3 (дада эти самые) 3) берем по 4-ре числа. если в каждой четверке числа равны, то тогда УЕС иначе нет. в каком случае мой алгоритм будет не рабочим? |
|||
106
Xapac_2
28.05.12
✎
08:38
|
а блин там ответы есть....
|
|||
107
izekia
28.05.12
✎
08:56
|
на кодеджеме на той же квалификации вроде веселее все было
|
|||
108
NS
28.05.12
✎
12:16
|
(101) Первый не получу.
Я разговаривал с человеком - олимпиадные программисты - это специализация, они постоянно занимаются решением олимпиадных задач, у них куча готовых тестов, и знают они весьма специфичные олимпиадные вещи, типа полиномиальных хешей и т.д. У меня цель одна - пройти в финал, ну и сначала конечно-же пройти в отборочный тур. За 20+ лет прошедших с последней олимпиады я напрочь потерял навык. Зачем-то перед началом решения вникал во все задачи. Вместо того чтоб спокойно решить третью, не оторвался от четвертой. Причем налетел на проблемы не сколько раз, сначала с replaceAll, котоый не просто заменяет, а применяет регулярное выражение, а я вообще не знаю что это такое, потом еще и с сочетанием двух разных методов в вводе, которые вызвали ошибку. После того как система дала рунтайм еррор - у меня было еще навалом времени. И третью задачу всяко успевал сделать. Но на меня просто нашел ступор. (105) Это правильный алгоритм. |
|||
109
NS
28.05.12
✎
12:17
|
Короче совет - если система не приняла решение - лучше сразу приступать к другой задаче, тем более что на этой уже получаешь 20 штрафных минут, а если выложишь другую - то штрафного времени не будет.
|
|||
110
izekia
28.05.12
✎
12:20
|
(108) сортировать? это же больше операций
|
|||
111
NS
28.05.12
✎
12:33
|
(110) Там есть описание решения на сайте на последней закладке.
И на олимпиадах никто не считает количество операций, считают О() В данном случае число значений в массиве фиксировано, и поэтому любое решение это О(1), и в любом случае уложится в 2 секунды. Причем те, кто решили за три минуты - явно имели заготовку - ввод числа элементов в массиве, ввод массива, сортировка. Им оставалось написать проверку на нули, и сравнение трех четверок. И больше операций чем в каком методе решения? |
|||
112
izekia
28.05.12
✎
12:41
|
(111) мне кажется собрать словарь дешевле
хотя конечно на 12 элементах не скажется зато сразу размер словаря отсеивает часть вариантов, плюс просто проверяем на 4 |
|||
113
NS
28.05.12
✎
12:42
|
(112) Собрать словарь - сложность алгоритма такая-же как и сортировка - n ln n
Тебе в словарь нужно добавить n слов, бинарный поиск на уже наличие - логарифм. |
|||
114
izekia
28.05.12
✎
12:44
|
(113) ты не учитываешь, что мы ищем не среди 12 элементов, а среди трех
иначе отбрасываем сразу |
|||
115
NS
28.05.12
✎
12:48
|
(114) Если среди трех - то любой метод О(1), и разница только в скорости написания. С сортировкой, особенно если она у тебя готовая - намного быстрее.
Хотя какой-нибудь пузырек пишется за две минуты. Я им и сделал. |
|||
116
izekia
28.05.12
✎
12:50
|
блин, извини, какой пузырек?
просто три сравнения, не совпало ни одного - выкидываем, иначе увеличиваем соответствующий счетчик, я не про словарь готовый, я про принцип |
|||
117
NS
28.05.12
✎
13:08
|
(116) А я про сотрировку, которая пишется моментально.
Для а=1 по т-1 цикл Для б=а+1 то т цикл Если м[а]>м[б] Тогда темп=м[а]; м[а]=м[б]; м[б]=темп; Конецесли; КонецЦикла; КонецЦикла; И повторюсь - у большинства участников сортировкка готовая, они её просто копируют в проет. А ты свой принцип вместо минуты будешь писать 10, и решив все задачи отстанешь на 45 очков. |
|||
118
GomerSimpson
28.05.12
✎
14:02
|
Про Палидром придумал вот так:
Если ЭтоПалиндром(S) Тогда Если СтрЧислоВхождений(S, Лев(S,1)) = СтрДлина(S) Тогда Возврат "NO SOLUTION"; Иначе Возврат Сред(S,2); КонецЕсли; Иначе Возврат S; КонецЕсли; |
|||
119
izekia
28.05.12
✎
17:12
|
(117) отсортированный массив еще надо обработать
сейчас условия перечитаю и попробую сделать на питоне |
|||
120
izekia
28.05.12
✎
17:14
|
кстати в условии первой задачи возможны спички нулевой длины?
|
|||
121
izekia
28.05.12
✎
17:21
|
блин, залез на сферу, посмотрел на свои примеры, точно не сегодня)
|
|||
122
NS
28.05.12
✎
17:42
|
(120) Я проверку не делал, мне решение засчитали.
Посмотри условие, вроде там в условии длины целые положительные. |
|||
123
NS
28.05.12
✎
17:44
|
(119) его не надо обрабатывать.
Если (м[1]=м[2])и(м[2]=м[3])и(м[3]=м[4])и(м[5]=м[6])и(м[6]=м[7])и(м[7]=м[8])и(м[8]=м[9])и(м[9]=м[10])и(м[10]=м[11]) Тогда можно иначе нельзя |
|||
124
NS
28.05.12
✎
17:45
|
Если (м[1]=м[2])и(м[2]=м[3])и(м[3]=м[4])и(м[5]=м[6])и(м[6]=м[7])и(м[7]=м[8])и(м[9]=м[10])и(м[10]=м[11])и(м[11]=м[12]) Тогда
блин! |
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |