Welcome Guest ( Log In | Register )

Help | Search | Members | Calendar

Pages: (4) [1] 2 3 ... Last »  ( Go to first unread post )
Задачка из олимпиады
« Next Oldest | Next Newest » Track this topic | Email this topic | Print this topic
nop
Posted: Oct 20 2008, 19:29

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

Интересная задачка из олимпиады, кому интересно, попробуйте решить.

Consider an integer sequence consisting of N elements where –
X1 = 1
X2 = 2
X3 = 3
Xi = (Xi-1 + Xi-2 + Xi-3) % M + 1 for i = 4 to N

Find 2 values a and b so that the sequence (Xa Xa+1 Xa+2 ... Xb-1 Xb) contains all the integers
from [1,K]. If there are multiple solutions then make sure (b-a) is as low as possible.
In other words, find the smallest subsequence from the given sequence that contains all the integers
from 1 to K.

Consider an example where N = 20, M = 12 and K = 4.

The sequence is {1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}.

The smallest subsequence that contains all the integers {1 2 3 4} has length 13 and is highlighted in
the following sequence:

{1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}.

Input
First line of input is an integer T(T<100) that represents the number of test cases. Each case consists of
a line containing 3 integers N(2 < N < 1000001), M(0 < M < 1001) and K(1< K < 101). The meaning of
these variables is mentioned above.

Output
For each case, output the case number followed by the minimum length of the subsequence. If there is
no valid subsequence, output “sequence nai” instead. Look at the sample for exact format.

Sample Input
2
20 12 4
20 12 8

Output for Sample Input
Case 1: 13
Case 2: sequence nai

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
arnix
Posted: Oct 20 2008, 20:59

Challenger

Group: Moderator
Member No.: 869

Joined: July 31, 2004

"The smallest subsequence that contains all the integers {1 2 3 4} has length 13 and is highlighted in
the following sequence:

{1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}."

Well, it is not highlighted wink.gif
 
    Top
arnix
Posted: Oct 20 2008, 22:46

Challenger

Group: Moderator
Member No.: 869

Joined: July 31, 2004

Вроде решил (а может и нет), на паскале, как и водится )
Для компиляции пользуйтесь FreePascal v2.2.2 или Lazarus 0.9.26

CODE

{
 Problem: See http://forum.vision.am/index.php?act=ST&f=75&t=16237&st=0
 Solution Author: arnix [arnix.at [@] gmail.com]
}

program nop;

{$mode objfpc}{$H+}

uses
 {$IFDEF UNIX}{$IFDEF UseCThreads}
 cthreads,
 {$ENDIF}{$ENDIF}
 Classes
 { you can add units after this };


var
 a: array of array of integer;
 rng: array of array[1..2] of integer;
 a1, a2, a3, x1, x2: integer;
 i, j, r: integer;
 t, n, m, k: integer;
 temp: integer;
 res: integer;
 f, fw: text;
 solved: boolean;

procedure process_index(indx, pass: integer);
begin
 if pass = 0 then begin
   x1 := -1;
   x2 := -1;
 end else begin
   x1 := rng[pass - 1][1];
   x2 := rng[pass - 1][2];
 end;

 if (x1 < 0) or (indx < x1) then begin
   if x2 < 0 then begin
     x2 := x1;
   end;
   x1 := indx;
 end else if (x2 < 0) or (indx > x2) then begin
   x2 := indx;
 end;

 rng[pass][1] := x1;
 rng[pass][2] := x2;
end;

procedure solve(x, y: integer);
begin
 //writeln(x, ', ', y);
 process_index(a[x][y], x);
 if x < length(a) - 1 then begin
   solve(x + 1, 0);
 end else begin
   temp := x2 - x1 + 1;
   //writeln(' ', x1, ', ', x2, ' = ', temp);
   if (res < 0) or (temp < res) then begin
     res := temp;
     x1 := -1;
     x2 := -1;
   end;
 end;
 if y < length(a[x]) - 1 then begin
   solve(x, y + 1);
 end;
end;

begin
 assign(fw, 'output.txt');
 rewrite(fw);

 assign(f, 'input.txt');
 reset(f);
 readln(f, t);
 for i := 1 to t do begin
   solved := false;

   read(f, n);
   read(f, m);
   read(f, k);

   if k > m then begin
     writeln(fw, 'Case ' , i, ': sequence nai');
     solved := true;
     break;
   end;

   setlength(a, k);
   a1 := 1;
   a2 := 2;
   a3 := 3;
   for j := 0 to n - 1 do begin
     if j <= 2 then begin
       r := j + 1;
     end else begin
       r := ((a3 + a2 + a1) mod m) + 1;
       a1 := a2;
       a2 := a3;
       a3 := r;
     end;
     if (r >= 1) and (r <= k) then begin
       setlength(a[r - 1], length(a[r - 1]) + 1);
       a[r - 1][length(a[r - 1]) - 1] := j;
     end;
   end;

   for j := 0 to k - 1 do begin
     if length(a[j]) < 1 then begin
       writeln(fw, 'Case ' , i, ': sequence nai');
       solved := true;
       break;
     end;
   end;

   if not solved then begin
     res := -1;
     setlength(rng, k);
     for j := 0 to k - 1 do begin
       rng[j][1] := -1;
       rng[j][2] := -1;
     end;
     solve(0, 0);
     writeln(fw, 'Case ' , i, ': ', res);
     solved := true;
   end;
 end;
 close(fw);
 close(f);
end.


User Attached Image Download attachment
nop.zip ( Number of downloads: 330 )


 
    Top
arnix
Posted: Oct 20 2008, 22:48

Challenger

Group: Moderator
Member No.: 869

Joined: July 31, 2004

В архиве из предыдущего поста отсутствует файл input.txt
вот он

User Attached Image Download attachment
input.txt ( Number of downloads: 387 )


 
    Top
nop
Posted: Oct 21 2008, 11:25

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

QUOTE
Well, it is not highlighted wink.gif

Да, забыл smile.gif, вот:
{1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}
QUOTE
Вроде решил (а может и нет)...

Дело в том, что для решения дается 8 сек...
При входных данных "100000 1000 100" соответственно N M K, прога работает намного дольше wink.gif, значит алгоритм кривой smile.gif

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
nop
Posted: Oct 21 2008, 11:52

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

Вот еще кривой алг:
QUOTE

#include <iostream>

using namespace std;

int X[1000001];

bool exist(int a,int b,int c){
for(int i=a;i<b;i++)
  if(X[i]==c)return true;
return false;
}

bool ka(int N,int n, int K){
int i,j;
for(i=0;i+n<N;i++){
  for(j=1;j<=K;j++)
  if(!exist(i,i+n,j))break;
  else if(j==K && exist(i,i+n,j))return true;}
return false;
}

main(){
int T,N,M,i,K,k;
cin>>T;
for(k=1;k<=T;k++){
  cin>>N>>M>>K;
  for(i=0;i<3;i++)X[i]=i+1;
  for(;i<N;i++)X[i]=(X[i-1]+X[i-2]+X[i-3])%M+1;
  for(i=K;i<N;i+=i-1)
  if(ka(N,i,K)){
    cout<<"Case "<<k<<": "<<i<<endl;
    break;
  }
  if(!ka(N,i,K))cout<<"Case "<<k<<": "<<"sequence nai"<<endl;
}
return 0;
}


--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
Dream_InspectoR
Posted: Oct 21 2008, 15:28

Eye of the Vision

Group: Moderator
Member No.: 614

Joined: February 10, 2004

Функция exist глупость smile.gif Извини если обидел, но bitset сделает то же самое в константное время.

--------------------
Kill'em!!! Kill'em ALL!!!
 
        Top
Dream_InspectoR
Posted: Oct 21 2008, 15:33

Eye of the Vision

Group: Moderator
Member No.: 614

Joined: February 10, 2004

Хочешь еще подсказку? smile.gif) Или ты знаешь решение (nop в смысле)?

--------------------
Kill'em!!! Kill'em ALL!!!
 
        Top
nop
Posted: Oct 21 2008, 16:17

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

Дело не в том, что ф-я exist глупость smile.gif, там и алгоритм глупость, хоть exist, хоть bitset, все равно при относительно больших данных работать будет ооочень долго...
QUOTE
Хочешь еще подсказку?

Если это касается алгоритму - да, если же проге - спасибо, но оптимизация тут не при чем. smile.gif
QUOTE
Или ты знаешь решение (nop в смысле)?

Не понял... wacko.gif

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
Agent47
Posted: Oct 21 2008, 16:32

Wise Dreamer

Group: Elite Member
Member No.: 3118

Joined: May 16, 2008

QUOTE (In the immortal words of nop, since Oct 21 2008, 17:17)
Не понял... wacko.gif

Думаю, Dream хотел узнать, знаешь ли ты верное решение этой задачи?(в смысле, чтоб прога работала быстро и правильно) smile.gif
 
     Top
Dream_InspectoR
Posted: Oct 21 2008, 16:33

Eye of the Vision

Group: Moderator
Member No.: 614

Joined: February 10, 2004

Да я хотел узнать ты знаешь решение или как?

--------------------
Kill'em!!! Kill'em ALL!!!
 
        Top
nop
Posted: Oct 21 2008, 16:34

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

Неа, не знаю.

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
Dream_InspectoR
Posted: Oct 21 2008, 18:47

Eye of the Vision

Group: Moderator
Member No.: 614

Joined: February 10, 2004

Похоже я недочитал условие.. Подумаю дальше smile.gif Я могу найти первую последовательность довольно быстро, но кратчайшую пока нет. Хотя идея как найти также кратчайшую есть, но надо написать проверить. Примерно за N*M времени..

--------------------
Kill'em!!! Kill'em ALL!!!
 
        Top
arnix
Posted: Oct 21 2008, 20:16

Challenger

Group: Moderator
Member No.: 869

Joined: July 31, 2004

QUOTE (In the immortal words of nop, since Oct 21 2008, 11:25)
Да, забыл smile.gif, вот:
{1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}

Дело в том, что для решения дается 8 сек...
При входных данных "100000 1000 100" соответственно N M K, прога работает намного дольше wink.gif, значит алгоритм кривой smile.gif

Ты шутишь да?? При входных данных "100000 1000 100" соответственно N M K _моя_ программа работает меньше 0.1 секунд и выдает что решения нет, откуда ты взял "прога работает намного дольше wink.gif" ??
 
    Top
nop
Posted: Oct 25 2008, 13:19

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

QUOTE (In the immortal words of arnix, since Oct 21 2008, 21:16)
QUOTE (In the immortal words of nop, since Oct 21 2008, 11:25...)
Да, забыл smile.gif, вот:
{1 2 3 7 1 12 9 11 9 6 3 7 5 4 5 3 1 10 3 3}

Дело в том, что для решения дается 8 сек...
При входных данных "100000 1000 100" соответственно N M K, прога работает намного дольше wink.gif, значит алгоритм кривой smile.gif

Ты шутишь да?? При входных данных "100000 1000 100" соответственно N M K _моя_ программа работает меньше 0.1 секунд и выдает что решения нет, откуда ты взял "прога работает намного дольше wink.gif" ??

Не знаю как у тебя, но у меня вот с этими данными
2
100000 1000 100
20 12 8
вообще зависает sad.gif

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
knightmare
Posted: Oct 26 2008, 21:58

Wise Dreamer

Group: Elite Member
Member No.: 1572

Joined: October 31, 2005

на скорую руку
вариант, если правильно понял задачу

----------------
//пусть N[i] - i-ое число последовательности

int min=0;
int vstretili=0;
int i;

int[] k=new int[K];
for(i=0; i<K; ++i){k[i]=-1;}

for(i=0; i<N; ++i){
if(N[i]>K){continue;}
vstretili += k[N[i]-1]==-1;
k[N[i]-1]=i;
if(vstretili==K){
int kmin=0;
for(int j=0; j<K; j++){
if(kmin>k[j]){kmin=k[j];}
}
if (i-kmin+1<min){min = i-kmin+1;} //i-kmin - самое дальнее (индекс начала), из встречавшихся чисел "от 1 до K" (все уже встречались хотя бы раз)
}
}
----------------

в min - ответ, либо 0 если ответа нет


минусы:
1. никак не используется способ построения последовательности
2. оптимизируется
3. не проверял
4. N+K<сложность<N*K

--------------------
армия - эта крута, армейский спецназ - эта ваще крута


Хочу трахнуть Nissan Skyline R34, и ездить на Alessandra Ambrosio
 
    Top
firewall
Posted: Oct 27 2008, 10:01

Challenger

Group: Elite Member
Member No.: 2010

Joined: August 16, 2006

QUOTE (In the immortal words of knightmare, since Oct 26 2008, 21:58)
на скорую руку
вариант, если правильно понял задачу

----------------
//пусть N[i] - i-ое число последовательности

int min=0;
int vstretili=0;
int i;

int[] k=new int[K];
for(i=0; i<K; ++i){k[i]=-1;}

for(i=0; i<N; ++i){
if(N[i]>K){continue;}
vstretili += k[N[i]-1]==-1;
k[N[i]-1]=i;
if(vstretili==K){
int kmin=0;
for(int j=0; j<K; j++){
if(kmin>k[j]){kmin=k[j];}
}
if (i-kmin+1<min){min = i-kmin+1;} //i-kmin - самое дальнее (индекс начала), из встречавшихся чисел "от 1 до K" (все уже встречались хотя бы раз)
}
}
----------------

в min - ответ, либо 0 если ответа нет


минусы:
1. никак не используется способ построения последовательности
2. оптимизируется
3. не проверял
4. N+K<сложность<N*K

идея супер... cool.gif

--------------------
Newbie(g)
 
     Top
nop
Posted: Dec 20 2008, 13:15

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

След. задача:

D. Хоббит или Туда и обратно 2

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ

Старый Бильбо собирает песни и сказания всех народов Средиземья. Раз в двадцать лет он на год уезжает из Ривенделля, чтобы обойти за это время N городов Средиземья, пронумерованных числами от 1 до N (Ривенделль имеет номер 1), и в конце путешествия вернуться назад. Со времени последнего путешествия Бильбо прошло уже девятнадцать лет, и он понемногу начал собираться в дорогу. Из прошлого путешествия Бильбо помнит, что на входе в каждый город стоит стражник. Стражник спрашивает у путников, из какого города они пришли, и, в зависимости от этого, требует некоторую плату за вход в город. Времена меняются, и плата за проезд также меняется. Проконсультировашись с королём эльфов Эльрондом, Бильбо выяснил, что нынче за вход в город с номером A у тех, кто пришёл из города с номером B, стражники требуют ровно PA·[1000/PB] золотых, где Pi — население города с номером i, а [X] обозначает целую часть числа X. По мнению властей, такая плата стимулирует отток населения из крупных городов Средиземья в более мелкие. Бильбо знает население всех городов Средиземья и предполагает, что за год его путешествия население ни одного города не изменится. Как обычно, до начала путешествия ему хотелось бы найти такой порядок посещения городов, при котором потраченная сумма будет минимальна.
Исходные данные
В первой строке целое число N. 2 ≤ N ≤ 1000. Во второй строке через пробел N целых чисел P1, …, PN — население городов Средиземья. Все Pi лежат в пределах от 1 до 1000.
Результат
Выведите N целых чисел — порядок посещения N городов, минимизирующий плату за вход. Не забывайте, что Бильбо должен выйти из города с номером 1, побывать в каждом городе ровно по одному разу и только в конце путешествия вернуться в город с номером 1. Если у задачи существует множество решений, выведите любое из них.

Пример

исходные данные

4
10 3 5 4

результат
1 4 2 3

Автор задачи: Александр Ипатов
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, January 2008

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
Master of Puppets
Posted: Dec 20 2008, 13:48

Eye of the Vision

Group: Moderator
Member No.: 2067

Joined: August 29, 2006

В заданном полном неориентированном графе найти Гамильтонов цикл с минимальным весом. Книжка Скиены Programming Challenges тебе поможет.

--------------------
Master of Puppets, I'm pulling your strings, twisting your mind and smashing your dreams!
⠠⠵
 
       Top
nop
Posted: Dec 20 2008, 14:22

Wise Dreamer

Group: Elite Member
Member No.: 3143

Joined: July 2, 2008

А почему Гамильтонов цикл?
Не может быть такая комбинация, что вершины повторяются, а суммарный вес минимальный?

--------------------
- Но это же противоречит здравому смыслу
- А что такое здравый смысл? - спросил
Путешественник во Времени.
 
     Top
66 replies since Oct 20 2008, 19:29 Track this topic | Email this topic | Print this topic
Pages: (4) [1] 2 3 ... Last »
<< Back to Programming languages

 




Arminco Global Telecommunications