4797. Skracanie identyfikatorów [WI_IDEN]

[Yash_sof]

Zadanie: pl.spoj.pl/problems/WI_IDEN/
--
Czy na wejściu mogą pojawić się znaki które nie są literami, cyframi ani _ ani $?

[kokosek_sof1]

Nie wiem czy mogą, bo nie próbowałem zakładać, że nie mogą.
Tak więc mój kod, który zakłada, że mogą ma 100pkt.
Radzę dodać ten warunek, bo to mało roboty, a będzie się wiedziało, że to nie w tym tkwi błąd (albo że w tym tkwił).
Jak chcesz, to wklej kod, to będzie łatwiej pomóc.
Mój błąd tkwił w tym, że wypisywało mi 2 razy odpowiedź kiedy długość stringa była krótsza od maksymalnej długości stringa (czyli, że nie trzeba było nic usuwać).

Powodzenia.

[jurkowski]

Cześć.
Rozwiązałem zadanie "Skracanie identyfikatorów" (http://pl.spoj.pl/problems/WI_IDEN/) i mój rezultat to 60, a maximum to 100. Co to tak właściwie oznacza?

[kokosek_sof1]

To znaczy, że nie masz maksymalnej ilości testów wykonanych poprawnie.
Czyli masz np. 10 testów po 10pkt każdy. No i Twój program odpowiada dobrze np. na: 1, 2, 3, 4, 7, 9 i masz 6*60=60pkt, na 10*10pkt.
W testach, których nie masz zaliczonych możesz mieć TLE (Time Limit Exceeded) albo WA (Wrong Answer), co nie ma znaczenia, bo i tak nie masz tego zaliczonego.
Więc, żeby mieć 100pkt a nie 60 musisz albo przyspieszyć algorytm, albo znaleźć błąd w Twoim programie dla jakichś danych.

Powodzenia.

[Joachim_Wulff]

Witam.
Ma ktos jakies testy do tego zadania? Nie moge przeskoczyc 60pkt., moze ktos mi powiedziec jakie beda odpowiedzi dla :
1
AS

Czy to ma byc A czy S bo nie wiem czy dobrze rozumie w wyniku ma byc przynajmniej jedna samogloska.

1
SSSASS -> A

2
SSSAS -> AS

2
SSASS -> AS

3
WQAS -> WAS

Z gory dzieki.
Pozdr.

[Joachim_Wulff]

Witam.
Ma ktos jakies testy zeby przekroczyc 60pkt. albo jakas wskazowke.

Z gory dzieki.

[kokosek_sof1]

Trudno tak wymyślić trudne testy. Daj może kod, to poszukam WA testów.
No ale jeden test (może wtrafiłem w twój błąd):

14
RSHU_RSRWWHST$IOOIO$E_OTYO_TYOU$HWO$

AC odp:

RSHURSRWWHST$$

Powodzenia.

[Joachim_Wulff]

to moj kod moze ktos sprawdzic co jest nie tak, za ten kod dostaje 60pkt.

z gory dzieki

[Joachim_Wulff]

sorry nie ten kod

[zjarek_sof]

Kto powiedział, że wszystkie litery w identyfikatorze są duże?

[Pete_sof]

W zadaniu nie ma napisane jakie to litery.

Szczerze mówiąc to nie mam już siły, mój program przechodzi każdy wymyślony test, może Wy na coś wpadniecie, bo ja już nie mam pojęcia:

#include <iostream>
using namespace std;
int main()
{
  char tab[65536];
  bool tab1[65536];
  int b(0);
  unsigned long int l, licz(0), zos;
  cin>>l;
  char a;
  a=getchar(); if(a==10) a=getchar();
  while((a!=10) && (a!=EOF))
  {
    tab[licz]=a;
    tab1[licz]=true;
    licz++;
    a=getchar();
  }
  zos=licz+1;
  if(zos<=l)
    goto aaa;
  for(int i(licz); i>=0 ; i--)
  {
    if(((tab[i]>=48) && (tab[i]<=57)) || ((tab[i]>=65) && (tab[i]<=90)) || ((tab[i]>=97) && (tab[i]<=122)) || (tab[i]==36)) ;
    else
      {
        tab1[i]=false;
        zos--;
      }
    if(zos<=l)
      goto aaa;
  }
  for(int i(licz) ; i>=0 ; i--)
  {
    if(tab1[i])
      if((tab[i]>=48) && (tab[i]<=57))
      {
        tab1[i]=false;
        zos--;
      }
    if(zos<=l)
      goto aaa;
  }
  for(int i(0) ; i<=licz ; i++)
  {
    if(tab1[i])
      if((tab[i]==65) || (tab[i]==97) || (tab[i]==69) || (tab[i]==101) || (tab[i]==73) || (tab[i]==105) || (tab[i]==79) || (tab[i]==111) || (tab[i]==85) || (tab[i]==117) || (tab[i]==89) || (tab[i]==121))
      {
        if(b)
        {
          tab1[i]=false;
          zos--;
        }
        b++;
      }
    if(zos<=l)
      goto aaa;
  }
  b=0;
  for(int i(licz) ; i>=0; i--)
  {
    if(tab1[i])
    {
      if(b)
      {
        tab1[i]=false;
        zos--;
      }
      b++;     
    }
    if(zos<=l)
      goto aaa;
  }
  aaa:
  for(int i(0); i<licz ; i++)
    if(tab1[i])
      cout<<tab[i];
  system("pause");
  return 0;
}

[kokosek_sof1]

Próbowałem znaleźć błąd, ale nie znalazłem.
Może powodem nie jest WA, ale TLE, jak pisałem kilka postów wyżej, w dwóch ostatnich testach (bo jak wrzucałem, to wolno szło to).
Spróbuj może zoptymalizować swój algorytm.
Mi się udało zrobić liniówkę i mam 0.00, więc się da. No i jak będziesz miał mały czas, to będziesz wiedział, że to WA, a nie TLE.

Ale poszukam jeszcze, bo w sumie jest 10 sekund na to, więc może jednak WA.

/Edit: Sorry, nie przeczytałem postu Twojego. Zawsze najpierw sprawdzam kod. Tak więc nadal szukam błędu.

[davidbnpl]

A masz moze pomysl na jakis test, ktory pochlaniac moze duzo czasu?
U siebie testowalem dla losowego napisu o dlugosci 65000 i program sie wyrabial w niecale 2s za kazdym razem.
Jeszcze mam pytanie - co znaczy limit czasu "1s-10s"? 1s dla jednego testu, a 10s dla wszystkich 10 testow? I wynik w sekundach jak mam interpretowac? Jesli mam np 1.98s wynik to znaczy, ze wszystkie 8 testow (bo 2 niezaliczone) wykonalo w sumie w 1.98s czy moze to jest srednia na test? Czy byc moze jeszcze inaczej? I dlaczego ktos ma powyzej 15s i zaliczone zadanie (na 80pkt)?
Co do algorytmu to podziwiam, nie mam pojecia jak to mozna zrobic w 0.00... Jesli nie chcesz na forum zdradzac tajemnicy to moze napiszesz do mnie na gg 2192616? Taki przykladowy wydajny kod moglby mi pomoc w przyszlosci i zmienic podejscie do tworzenia algorytmow

[Joachim_Wulff]

Ten program co podales dla testu
3
./a.out <- wejscie
/at <-odp

a powinno byc

3
./a.out
aut

[davidbnpl]

Nazwa zmiennej składa się z liter, cyfr, znaku '_' i '$', kropki nie mogą wchodzić w skład napisu. Po za tym to już sprawdzałem i testowałem też wraz z przepuszczeniem całego testu przez funkcję usuwającą wszelkie inne znaki, po za dozwolonymi, jedyny efekt to dodatkowe pół sekundy czasu.

EDIT: zriobione czas 0.07 i 100pkt

teraz odpowiedź w czym tkwił błąd:
CZAS, a dokładniej wszelkie miejsca użycia

strlen(ch)

gdy dodałem te 2 linijki:

int length = strlen(ch);
#define strlen(ch) length

program przeszedł

[Joachim_Wulff]

Wcale ze nie to co przytaczasz to jes pierwszy punkt

napisz nazwę zmiennej w postaci, w której życzyłbyś sobie ją widzieć (czyli) – używaj tylko liter, cyfr oraz znaków '_' (podkreślenie) i '$' (dolar); może zabrzmi to dziwnie, ale znak '$' traktować będziemy jak literę

nic nie ma na temat ze na wejsciu nie moze byc "dsvsd.vsd,v/we,/we,fwe',fg./we,fwe,f/32,f/32,rf/........................///////////[[[[[[[[[]]]]]]]]]]]"
i dalej
jeśli długość nazwy jest mniejsza równa n, możesz jej użyć i nic musisz robić nic więcej

jesli dalej przekracza to przechodzisz dalej

a po zatym po co jakas '.' nie mozesz zrobic drugiej tablicy i do niej zapisywac. co do wywolania funkcji strlen() wyciagnij ja przed for(;; nie umieszczaj jej w petli bo to strata czasu. po co ja cafy czas wywolywac przy karzdym obrocie petli?

[davidbnpl]

No właśnie to pierwszy punkt algorytmu, który mamy zapisać i zarazem wejście. Nie ma testu, w którym by potrzeba było sprawdzać czy występują inne znaki.
Druga tablica char? Można, ale po co, wydaje mi się moje rozwiązanie optymalniejsze, a na pewno wystarczająco szybkie. Co do wywołania funkcji strlen() to już post wcześniej pisałem, że na to wpadłem, więc nie ma potrzeby, abyś mi to teraz mówił (mogłeś wcześniej, jak nie wiedziałem gdzie tkwi błąd).

[Joachim_Wulff]

Na pewno nie jest optymalniejsze niz zastosowanie 2 tablic mozna osiagnac 0.00 1.7M, a co do petli for(; to wyslales szybciej posta. jak robisz na 1 tablicy to po co sprawdzasz tyle razy czy sie zmienila dlugosc skoro ona sie nie zmienia? Jak juz chcesz tak to robic to zastosuj dwie zmienne dlugosc=dlugosc1=strlen(nap); w pierwszej trzymasz dlugos ktorej nie zmieniasz, a w 2 jak wstawiasz '.' to zmniejszasz ja i sprwadzasz z max ogranicza to wywolanie strlen() bo i tak nie zmieniasz dlugosci.

[davidbnpl]

jak robisz na 1 tablicy to po co sprawdzasz tyle razy czy sie zmienila dlugosc skoro ona sie nie zmienia? Jak juz chcesz tak to robic to zastosuj dwie zmienne dlugosc=dlugosc1=strlen(nap); w pierwszej trzymasz dlugos ktorej nie zmieniasz, a w 2 jak wstawiasz '.' to zmniejszasz ja i sprwadzasz z max ogranicza to wywolanie strlen() bo i tak nie zmieniasz dlugosci.

przeciez wlasnie tak robie...

[Pete_sof]

Jeżeli macie jakiś pomysł, albo test to byłbym wdzięczny, każdy mój test przechodzi a dostaje 0 pkt.

#include <iostream>
using namespace std;
int main()
{
  char tab[65536];
  bool tab1[65536];
  int b(0);
  unsigned long long int l, licz(0), zos;
  cin>>l;
  char a;
  a=getchar(); if(a==10) a=getchar();
  while((a!=10) && (a!=EOF))
  {
    tab[licz]=a;
    tab1[licz]=true;
    licz++;
    a=getchar();
  }
  zos=licz+1;
  if(zos<=l)
    goto aaa;
  for(int i(licz); i>=0 ; i--)
  {
    if(((tab[i]>=48) && (tab[i]<=57)) || ((tab[i]>=65) && (tab[i]<=90)) || ((tab[i]>=97) && (tab[i]<=122)) || (tab[i]==36)) ;
    else
      {
        tab1[i]=false;
        zos--;
      }
    if(zos<=l)
      goto aaa;
  }
  for(int i(licz) ; i>=0 ; i--)
  {
    if(tab1[i])
      if((tab[i]>=48) && (tab[i]<=57))
      {
        tab1[i]=false;
        zos--;
      }
    if(zos<=l)
      goto aaa;
  }
  for(int i(0) ; i<=licz ; i++)
  {
    if(tab1[i])
      if((tab[i]==65) || (tab[i]==97) || (tab[i]==69) || (tab[i]==101) || (tab[i]==73) || (tab[i]==105) || (tab[i]==79) || (tab[i]==111) || (tab[i]==85) || (tab[i]==117) || (tab[i]==89) || (tab[i]==121))
      {
        if(b)
        {
          tab1[i]=false;
          zos--;
        }
        b++;
      }
    if(zos<=l)
      goto aaa;
  }
  b=0;
  for(int i(licz) ; i>=0; i--)
  {
    if(tab1[i])
    {
      if(b)
      {
        tab1[i]=false;
        zos--;
      }
      b++;     
    }
    if(zos<=l)
      goto aaa;
  }
  aaa:
  for(int i(0); i<licz ; i++)
    if(tab1[i])
      cout<<tab[i];
  return 0;
}