beecrowd preguntado on feb 8 2013

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

• 

  +3

  lincoln7 respondido 7 years ago

  Por favor, alguém poderia dizer onde estou errando? O indexChildren começa mesmo no 0? A contagem no sentido anti-horário incrementa ou decrementa? Já tentei inúmeras combinações e nada deu certo. Desde já grato pela atenção.

  #include<string>
  #include<iostream>
  #include<map>
  #include<queue>
  #include<algorithm>
  #include<list>
  #include<map>
  #include<stdio.h>
  #include<string.h>
  #include<math.h>
  #include<limits.h>
  #include<unordered_map>
  #include<unordered_set>
  #include<complex>
  #include<array>
  #include<vector>
  #include<stdlib.h>
  #include <set>
  
  using namespace std;
  
  class Child
  {
  public:
     char name[40];
     int value;
  };
  
  int main()
  {     
     int n;
     scanf("%d",&n);
     while(n)
     {      
        deque<Child> children(n);
        for(register int i =0;i<n;i++)                     
           scanf("%s %d",children[i].name,&(children[i].value));               
        int indexChildren= 0;
        int step = children[0].value;                               
        while(children.size()>1)
        {
           if(step%2)                             
              indexChildren = (indexChildren+step) % children.size();                  
           else                                             
              indexChildren = (indexChildren-step) % children.size();                              
           step = children[indexChildren].value;
           children.erase(children.begin()+indexChildren);                           
        }
        printf("Vencedor(a): %s\n",children.back().name);
        scanf("%d",&n);
     }    
     return 0;
  }

• 

  +3

  pfelipe1 respondido 8 years ago

  Tenta não ficar iterando usando list, usa o vector com a função erase, porque ai você pode só calcular a posição e deletá-la sem fazer iterações:

  vetor.erase(vetor.begin()+pos);

  Usar list é bom pq para apagar um elemento é O(1), já no vector é (+ ou -) O(pos), porém para apagar no list você tem que iterar até chegar no carinha que deseja, portanto ficando com a mesma complexidade do vector. Espero ter ajudado. E para achar a posição tentar usar aritmética modular que já vai direto.

  Abraços!

• 

  +2

  SamuelEduardo respondido 8 years ago

  TLE. Sugestões ? Valeu.

  #include<bits/stdc++.h>
  
  using namespace std;
  
  int main()
  {
      int N;
      string Nome;
      map<string,int>PC;
      int Cartao;
      bool ja;
      int inicio;
      list<string>Circulo;
      list<string>::iterator it,aux;
      while(scanf("%d",&N),N)
      {
          ja=false;
          bool prima=false;
          for(int i=0;i<N;i++)
          {
              cin>>Nome>>Cartao;
              if(!ja)
              {
                  inicio=Cartao;
                  ja=true;
              }
  
              PC[Nome]=Cartao;
  
              Circulo.push_back(Nome);
          }
          bool chego=false;
          it=Circulo.begin();
          bool antihorario=false;
          bool horario=false;
          if(inicio%2!=0)
              antihorario=true;
          else
          {
              prima=true;
              horario=true;
              chego=true;
          }
  
         while(Circulo.size()>1)
          {
  
              if(antihorario)
              {
                  for(int i=0;i<inicio;i++)
                  {
                  it++;
                  if(it==Circulo.end())
                      it=Circulo.begin();
                  }
  
              }
            else
              {
  
                  for(int i=0;i<inicio-1;i++)
                  {
  
                      if(!chego)
                          it--;
                      else
                      {
                          it=Circulo.end();
                          it--;
                          chego=false;
                          if(prima)
                          {
                              i--;
                              prima=false;
                          }
  
                      }
  
                      if(it==Circulo.begin())
                      {
                          chego=true;
  
                      }
  
                        cout<<*it<<endl;
                  }
              }
  
              inicio=PC[*it];
  
              if(it==Circulo.begin())
              {
                  it=Circulo.end();
                  it--;
                  aux=it;
                  it=Circulo.begin();
              }
              else
              {
                  aux=--it;
                  it++;
              }
  
              Circulo.remove(*it);
  
               it=aux;
  
              if(inicio%2!=0)
              {
                   antihorario=true;
                   horario=false;
              }
  
              else
              {
                  horario=true;
                  antihorario=false;
              }
  
              chego=false;
          }
  
              cout<<"Vencedor(a): "<<Circulo.front()<<endl;
  
          Circulo.clear();
  
      }
  
  }

• 

  0

  ccunha respondido 8 years ago

  Ola, O toolkit deste problema não esta de acordo com o enunciado do problema:

  Obs: O Nome de cada criança não deverá ultrapassar 30 caracteres e contém apenas letras maiúsculas e minúsculas, sem acentos, e o caractere “_”. O final da entrada é indicado pelo número zero.

  porem esta aceitando letras com acentos.