272 Bridge

[•Adriana_S]

Pe pod Fat-Frumos se poate deplasa [...] stationand (va ramane pe aceeasi scandura)

Genial, absolut genial. Vreau si eu sa ma pot deplasa stationand.
Apoi, nu poti sari pe o scandura subreda, dar poti sari de pe ea. Deci scandura nu suporta forta cu care se sare pe ea, dar suporta forta cu care se sare de pe ea. Acu' serios, enuntu' sucks. Tre' sa ne chinuim sa intelegem problema sau sa gasim rezolvarea?

[•pauldb]

Genial, absolut genial. Vreau si eu sa ma pot deplasa stationand.

Si eu as vrea sa ma pot teleporta, dar nu pot. Si ce legatura are asta cu problema? 

[•devilkind]

Nu cred ca e primul enunt de pe infoarena cu notiuni fictive.  E adevarat ca enuntul e putin cam ciudat, insa aceste lucruri se datoreaza ,  cum am mai spus, schimbarilor pe care acesta le-a suferit din dorinta de a fi cat mai clar si a se intelege cat mai bine ce se vrea. Am vrut ca din enunt sa rezulte modalitatea exacta de deplasare (respectiv stationare) pe acel pod, adik modalitatea de calcularea a rezultatului.

Tre' sa ne chinuim sa intelegem problema sau sa gasim rezolvarea?

rezolvarea nu mi se pare asa greu de gasit.

[•Adriana_S]

Pai asta spun si eu, rezolvarea e simpla, problema e ca enuntu' e dubios, si eu una pana nu mi-a explicat cineva care facuse problema ca stationarea se considera pas nici nu intelegeam exemplu. Ma rog, whatever.

[•wefgef]

mie personal mi s-a parut usor de inteles enuntul, asta probabil si pentru ca problema e inspirata din ceva dat acum cativa ani pe la OJI

[•devilkind]

iata ca s-a prins cineva. Oricum problema a fost modificata serios. acolo nu se exista stationare, teleportare si de asemenea se cerea altceva.

[•bogdan2412]

Eu de exemplu luam 70 de puncte in concurs tocmai pentru ca stiam problema de la acel ONI... O facusem cu cateva zile inainte... acolo de pe o scandura subreda NU puteai sa sari... Dar oricum nu conteaza acum...

[•cristy]

am ajuns la cota 80... am 2 wa...dar am o nelamurire...
stationarea se considera pas?...
[later edit]
ms...am 100

[•devilkind]

DA.

[•sakka]

             Am 2 intrebari:
  1.O scandura de tip 3 il poate teleporta pe FF pe o alta scandura de tip 3?
  2.Daca ajungem pe o scandura teleportatoare, numai la urmatorul pas are loc teleportare pe pozitia respectiva?

[•cristy]

1. DA
2. Teleportarea are loc automat, fara sa mai faca el vreun pas, cu toate acestea, se considera pas

[marcelcodrea06]

Eu am folosit memorie statica la implementare(o matrice de 4001*4001 ), programare dinamica inainte (ca si in solutia oficiala) si am inlocuit "%" cu o intructiune de decizie si o operatie de scadere cand este cazul ! Recurenta am facut-o pe matrice in mod clasic , folosind cateva if-uri si cu toate acestea  iau TLE pe ultimele 6 teste ! Unde gresesc ? Ce imi scapa ?

P.S.

                                                                                                                         
                                                                                                             Multumesc anticipat !

[•devilkind]

ultimele 6 teste sunt testele mari, eu le-am facut teoretic ptr a pica solutia cu dinamica inapoi in n^3, insa dak faci dinamica inainte esti pe solutia cea buna, incearca sa mai obtimizezi cate ceva.

[•cos_min]

Ce complexitate ai ? Trebuie O(n*maxim), unde maxim este numarul maxim de pasi. 

[marcelcodrea06]

Ce complexitate ai ? Trebuie O(n*maxim), unde maxim este numarul maxim de pasi. 

Complexitatea este O (n*3999) , adica programul meu executa cel mult 16 000 000 operatii + cele de inceput(0(n)) care pot fi considerate insignifiante !

Voi cate if-uri folositi la parcurgerea matricii pentru fiecare (i,j) ? 

Pe pod Fat-Frumos se poate deplasa [...] stationand (va ramane pe aceeasi scandura)

Apoi, nu poti sari pe o scandura subreda, dar poti sari de pe ea. Deci scandura nu suporta forta cu care se sare pe ea, dar suporta forta cu care se sare de pe ea. Acu' serios, enuntu' sucks. Tre' sa ne chinuim sa intelegem problema sau sa gasim rezolvarea?

Btw mi se pare logic sa poti sari de pe o scandura subreda si sa nu poti sa ajungi pe ea prin saritura sau teleportare, deoarece lui FF nu-i pasa ce s-a intamplat cu scandura subreda din spate dupa ce s-a desprins de pe ea . Daca ea cedeaza atunci cand FF sare sau se teleporteaza pe ea , atunci eroul ar putea sa fie relativ "incomodat"(Teoria chibritului generalizata) ....

[•cos_min]

si in ce timp raspunzi la cele m intrebari ? O(m) nu?

nu prea cred ca [virgula] conteaza nr de if-uri folosite. si la modulo -> poti face modulo dar numai daca ii cazu, adica daca valoarea la un moment depaseste sau ii egala cu 666013 . Cam atat ii tot. spor.

[ditzone]

Poti sa nu faci deloc modulo: daca rezultatul unei adunari e mai mare decat 666013, scazi 666013 la rezultat.

[marcelcodrea06]

Am implementat cu scadere de la inceput ....
Nu inteleg de ce sursa consuma atat timp ... pentru fiecare scandura a[j] verific daca poate avea ca destinatie a[j+1] sau a[j+2] , si daca sc. j nu este teleportoare atunci adun la b[i+1][j] pe b[ i ][ j ] .... in cazul in care se poate ajunge pe a[j+1] sau pe a[j+2] folosesc un for care merge pe numarul de pasi (1...3999) si aduna la b[i+1][j+1] sau/si la b[i+1][j+2] , dupa caz , pe b[ i ][ j ] ! Daca se poate ajunge pe scandura destinatie corespunzatoare unei scanduri teleportoare adun la b[i+1][destinatie[j]] pe b[ i ][ j ] !
E asa de simplu rationamentul incat nu-mi pot da seama ce se intampla....Voi nu faceti asa ?   

Ms oricum pt sfaturi !

[marcelcodrea06]

Daca trimit :

Cod:

#include<stdio.h>
long n,i,l,b[4001][4001],xx,yy,ll,j,aux,q;
int main()
{
 freopen("bridge.in","r",stdin);
 freopen("bridge.out","w",stdout);
 scanf("%ld %ld",&n,&ll);
 for(j=1;j<=n;j++)
 for(i=1;i<=3999;i++)
  b[i][j]=1;
  printf("0 \n");
  fclose(stdout);
  return 0;
}

Programul imi depaseste timpul de executie pe ultimele 6 teste !      Care este logica ?

Cod:

TEST 1	...[0.05s]...	Incorect sau fisier iesire lipsa
TEST 2	...[0.05s]...	Incorect sau fisier iesire lipsa
TEST 3	...[0.06s]...	Incorect sau fisier iesire lipsa
TEST 4	...[0.07s]...	Incorect sau fisier iesire lipsa
TEST 5	...[1.13s]...	Time limit exceeded
TEST 6	...[1.12s]...	Time limit exceeded
TEST 7	...[1.03s]...	Time limit exceeded
TEST 8	...[1.12s]...	Time limit exceeded
TEST 9	...[1.06s]...	Time limit exceeded
TEST 10	...[1.03s]...	Time limit exceeded

[•cos_min]

fa intreaga citire...si zi daca iti intra in timp. si inca ceva fara fclose(stdout) si poti folosi int si la citire %d nu %ld .

[u-92]

Problema este ca tu accesezi indicii rasturnati.
http://info.devnet.ro/articole.php?page=art&art=2

[marcelcodrea06]

Da....mersi mult ! Asta era problema ! Eu incercam sa optimizez degeaba , din moment ce spargeam linia de cache des ! Iata ca ai de invatat si acolo unde credeai ca nu se poate invata nimic , la accesarea unor elemente din memorie ! Mersi inca o data !

[•vladtarniceru]

imi explica si mie cineva va rog ce trebuie sa fac cand ma opresc pe o scandura teleportatoare?

pe exemplu pentru al treilea query se afiseaza 0 cu toate ca nr de pos de a ajunge sunt 2
apoi, pentru testul asta

6 5
3 0 3 3 1 2
2
5
6
1 1
2 1
2 4000
5 4000
6 4000

trebuie sa afisez 1 pentru query-ul 1 1, cu toate ca ma opresc pe scandura de tip 3..
ma poate lamuri si pe mine cineva va rog?
multumesc

[•darren]

Numarul de moduri de a ajunge pe o scandura lipsa sau pe o scandura teleportoare care are ca destinatie o scandura lipsa sau subreda este 0

Din cauza asta se afiseaza 0 la query (scandura teleportoare din exemplu duce pe scandura 4, care este subreda).

Altfel, singura restrictie pentru scandurile teleportoare este:

In momentul in care Fat-Frumos ajunge pe o scandura teleportoare el va fi teleportat pe scandura destinatie indiferent daca el vrea sau nu (nu poate stationa, sari sau pasi de pe ea)

Se intampla acelasi lucru si pentru exemplul dat de tine...

[•vladtarniceru]

multumesc am rezolvat pana la urma