Имя: Пароль:
IT
 
Russian Code Cup, вторая квалификация
,
0 izekia
 
01.06.12
16:06
Завтра кто-то участвует?
Я сижу и думаю про питон, в заданиях помимо всего прочего есть ограничения на время выполнения, где интерпретируемый язык очевидно проиграет по скорости и быть может не впишется в условия, живые примеры есть на сфере.
И еще, есть ли какой-то тестовый сервер, как был у кодеджема?
1 izekia
 
01.06.12
16:08
на хабре больше информации, чем на родном сайте, могли бы хотя бы задачи первого тура оставить для попыток решения
2 d3N4eGG
 
01.06.12
16:20
Можно посмотреть какие задания были на конкурсе?
3 izekia
 
01.06.12
16:21
4 izekia
 
01.06.12
16:22
разбор соответственно здесь:
http://habrahabr.ru/company/mailru/blog/144793/
5 OneUser
 
01.06.12
16:56
Чет не понятно. Им надо exe-шник или исходник отправлять?
6 OneUser
 
01.06.12
16:57
Про этикетку вообще жесть какая то. Чуть башка не взорвалась))
7 NS
 
01.06.12
17:02
Я участвую.
(6) на самом деле с этикеткой всё оказывается просто. Писанины правда много, но некторые успели написать за 10 минут. Нужен хеш (словарик),, счетчик неправильных слов в каждой строке, и после каждого сдвига проверять стыки.
8 NS
 
01.06.12
17:03
(5) исходник
9 OneUser
 
01.06.12
17:04
(8) .е. там по каждой задаче получают исходник, потом его компилируют вручную, а потом уже его автоматом проверяют?
10 OneUser
 
01.06.12
17:05
(7) Скока задач правильно решил? Какое место занял?
11 NS
 
01.06.12
17:10
(10) было в прошлой ветке.
371 место. Все же есть на сайте.
12 NS
 
01.06.12
17:11
(9) он естественно компилируется автоматом.
13 izekia
 
01.06.12
17:17
(7) да, я для себя открыл много нового ...
писанины не так много, если есть готовая канва
14 izekia
 
01.06.12
17:18
как я понимаю система такая же как и на spoj.pl ?
15 OneUser
 
01.06.12
17:20
(12) Например я написал программу в MS Visual Studio, я должен потом скопировать текст в блокнот и отправить и + написать на каком языке делал? Или надо файл .cpp отправлять, а там сами поймут какой компилятор использовать?
16 NS
 
01.06.12
17:24
(15) ты выбираешь при отправке какой компилятор использовать. Список возможных есть на сайте в правилах. Решение должно быть одним файлом.
17 NS
 
01.06.12
17:25
(14) такая же как в гугл ai
18 NS
 
01.06.12
17:26
(13) вообще да, правда очень много этим не сэкономишь.
19 NS
 
01.06.12
17:27
(15) отправляешь исходник. То есть cpp, если хочешь можешь и в блокнот скопировать :)
20 NS
 
01.06.12
17:28
21 izekia
 
01.06.12
17:37
(20) да там открытого примера нет и честно говоря тупо непонятно откуда данные забирать, кроме уже разбора
22 izekia
 
01.06.12
17:39
я вот вник про этикетку, и на питоне 2 секунды не получится, открытая дискриминация?
23 NS
 
01.06.12
17:39
(21) не понял.
Данные берешь с консоли, отправляешь туда же.
Они при запуске просто перенаправят ввод/вывод в файл.
24 NS
 
01.06.12
17:41
(22) задача решается со сложностью логарифм от колиечтва слов в словаре умноженное на количество символов суммарно в этикетках.
Если ты именно так решишь то уложится на любом языке, а если не так то не уложится в любом языке.
25 izekia
 
01.06.12
17:42
(23) ну да, как везде, но обычно просто пишут про это и рядом складывают рабочий пример
26 izekia
 
01.06.12
17:56
(24) там условия не смотрел?
Первая строка содержит одно целое число m (1 ? m ? 2000) — количество слов в словаре. Следующие m строк содержат слова из словаря. Все слова различны, состоят только из строчных букв латинского алфавита, длина каждого слова не превышает 2000 символов.
Следующая строка содержит одно целое число n (1 ? n ? 2000) — количество строк, написанных на этикетке. Следующие n строк содержат слова строки, написанные на этикетке. Все эти строки состоят только из строчных букв латинского алфавита и символов «.». Длина всех строк одинакова и не превышает 2000 символов.

на питоне 2.6 это нереально обработать за 2 секунды
27 NS
 
01.06.12
17:58
(25) ну я как раз на проблеме ввода и влетел в первом туре.
Правда еще и долгое отсутствие практики сказалось. Но одного тура достаточно чтоб провести работу над ошибками и нормально выступить в другом.
28 NS
 
01.06.12
18:01
(26) реально. У тебя словарь из 2000 хеш значений. Логарифм равен 11. Тебе нужно посчить хеши, и при каждом сдвиге срванить слово на сдвиге с хешем. Это не больше 4 миллионов симолов. Уложишься спокойно в 2 секунды.
29 NS
 
01.06.12
18:02
Тем более в питоне встроенная работа со словарями.
30 NS
 
01.06.12
18:19
Вообще народ пишет что использование одного языка для всех задач не очень хорошо, но если и используется только один язык - желательно использовать относительно быстрый.
То есть с/с++ либо жава.
31 NS
 
02.06.12
10:31
полчаса до старта.
32 izekia
 
02.06.12
10:58
поехали
33 Balabass
 
02.06.12
11:01
На 1С можно писать?
34 izekia
 
02.06.12
11:01
я такой тупой или первая задача настолько тупая?
35 izekia
 
02.06.12
11:02
(33) нет
36 izekia
 
02.06.12
11:16
в первой ключ к успеху - отсутствие преобразования
37 izekia
 
02.06.12
11:48
на первую уже два неправильных ушло
хоть бы понять в чем проблема
38 izekia
 
02.06.12
12:01
видимо в формате данных что-то не так
39 izekia
 
02.06.12
12:02
накуй такие конкурсы, если даже тупо тестов нет
40 izekia
 
02.06.12
12:44
блин, бесит уже, что я не так сделал?
sys.stdout.write("\n".join(map(lambda x : ((x[0] == "1" and (x[1] == "0" or x[1] == "1" or x[1] == "2")) or (x[0] == "2" and (x[1] == "1" or x[1] == "0")) or (x[0] == "0" and (x[1] == "0" or x[1] == "1" or x[1] == "2"))) and "Yes" or "No", map(lambda x: x.split(" "), sys.stdin.read().split('\n')[1:]))))
41 izekia
 
02.06.12
12:50
во второй задаче кто-то может объяснить что такое развернутая строка?
42 NS
 
02.06.12
13:00
теперь завис на третьей задаче.
Сделал проверку на возможность существования треугольников, нужно написать последнюю проверку - что вершина может существовать, и не находится в плоскости основания, и усё. Опять завис.
43 0_Serg_0
 
02.06.12
13:09
ну  и...?)
какие места?
44 izekia
 
02.06.12
13:10
(43) я даже простую задачу запостить не смог
45 NS
 
02.06.12
13:10
Это уже старость - лень стало выписывать формулу герона.
Сумма площадей трех боковых граней должна быть больше площади основания.
И нахрена без последней проверки отправлял?!
Решение без последней проверки
import java.io.*;
import java.util.*;
public class k2C {
   public static boolean ist(int a,int b,int c){
       return (a<b+c)&&(b<c+a)&&(c<b+a);
   }
   
   public static void main(String[] args) throws IOException  {
       Scanner in = new Scanner(System.in);
       int[] g;
       g = new int[6];
       int i=in.nextInt();
       for (int ch=1;ch<=i;ch++)
       {
         for (int k=0;k<6;k++)
         {
             g[k]=in.nextInt();
             
         };
         //sort_shell(g);
         boolean m=false;
       
                             for (int t1=0;t1<4;t1++)
                             {
                                 for (int t2=t1+1;t2<5;t2++)
                                 {
                                     for (int t3=t2+1;t3<6;t3++)
                                     {
                                       
                                         if (ist(g[t1],g[t2],g[t3]))
                                         {
                                             for (int t4=0;t4<4;t4++)
                                             {    
                                                 if (t4==t1){continue;};
                                                 if (t4==t2){continue;};
                                                 if (t4==t3){continue;};
                                                 for (int t5=t4+1;t5<5;t5++)
                                                 {
                                                     if (t5==t1){continue;};
                                                     if (t5==t2){continue;};
                                                     if (t5==t3){continue;};
                                                     for (int t6=t5+1;t6<6;t6++)
                                                     {
                                                         if (t6==t1){continue;};
                                                         if (t6==t2){continue;};
                                                         if (t6==t3){continue;};
   if ((ist(g[t1],g[t4],g[t5]))&&(ist(g[t2],g[t5],g[t6]))&&(ist(g[t3],g[t4],g[t6]))) {m=true;};
   if ((ist(g[t1],g[t4],g[t6]))&&(ist(g[t2],g[t5],g[t6]))&&(ist(g[t3],g[t4],g[t5]))) {m=true;};
   if ((ist(g[t1],g[t5],g[t6]))&&(ist(g[t2],g[t4],g[t6]))&&(ist(g[t3],g[t4],g[t5]))) {m=true;};
   if ((ist(g[t1],g[t4],g[t5]))&&(ist(g[t2],g[t4],g[t6]))&&(ist(g[t3],g[t5],g[t6]))) {m=true;};
   if ((ist(g[t1],g[t4],g[t6]))&&(ist(g[t2],g[t4],g[t5]))&&(ist(g[t3],g[t5],g[t6]))) {m=true;};
   if ((ist(g[t1],g[t5],g[t6]))&&(ist(g[t2],g[t4],g[t5]))&&(ist(g[t3],g[t4],g[t6]))) {m=true;};
   // тут в каждом условии не хватает формулы герона.
   // площадь основания (Герон(g[t1],g[t2],g[t3])) должна быть больше суммы площадей проверяемых на треугольник трех боковых граней.                                              }
                                                     
                                                 }
                                             }
                                             
                                         }
                                     }
                                 }
                             };
                           
         if (m)
         {System.out.println("Yes");} else {System.out.println("No");}
         //if (c>2) {System.out.println("Yes");} else {System.out.println("No");}
       };
   }

}
46 NS
 
02.06.12
13:11
(43) Не знаю. Но похоже в этот раз нужно было решать три задачи.
Не прошел с одной решеной точно, но в этот раз хоть меньше тормозил в начале, и быстрее запостил первое решение.
47 0_Serg_0
 
02.06.12
13:14
(46),(44)
та он  больше математика, чем программирование)
48 NS
 
02.06.12
13:17
(47) Олимпиадное программирование всегда такое.
Что-то скорость написания олимпиадных задач у меня упала уже нижеплинтуса.
в третьем туре не смогу участвовать, попробую подготовиться к следующему году.
49 NS
 
02.06.12
13:19
Кстати, опять решал второй задачу (третью) на которой завалилось большинство.
Почему не вторую - сам не понимаю.
50 0_Serg_0
 
02.06.12
13:28
(48)
зачем ждать??)
может  сюда успеешь- http://ipsc.ksp.sk/ ??
51 NS
 
02.06.12
13:37
(49) Кстати, опять облажался - площадь любой из граней должна быть меньше суммы площадей остальных трех, то есть к каждому условию добавляется еще четыре.
(50) Я в отпуске, в Риме, мне не до этого. 10 только вечером вернусь.
52 NS
 
02.06.12
13:42
(50) Она командная, еще и условия на английском языке.
53 0_Serg_0
 
02.06.12
13:58
(52)там ДО  3 человек = можно одному
54 NS
 
02.06.12
14:09
(53) С моей текущей формой, и десяти таких как я не хватит чтоб поучаствовать.
Я не могу понять, почему я не стал решать вторую задачу, а начал третью, в которой писанины больше? И еще вдобавок бросил за 10 с копейками минут до конца, хотя проверку на площади можно было еще успеть написать...
Хотя с двумя задачами все-равно не проходил.
http://russiancodecup.ru/round/7/analysis
Выложили решение. Делал я всё правильно.

"При отсутствие проверки на трёхгранный угол, а например, при проверке, что площадь каждой грани должна быть меньше, чем площадь остальных граней, мы получим что данный тетраэдр существует, но это не так"
Независимо от того, куда вы едете — это в гору и против ветра!