Cod:

672 580

Ce complexitate ai?

Care este solutia oficiala la aceasta problema?

Punctele sunt sortate?

LE: Pot exista 2 pct cu aceleasi coordonate?

[i]

[offtopic]
@speedzeal Decat sa pui la indoiala relevanta rezultatelor de la competitii si sa critici modul altora de a scrie, iti sugerez sa arunci o privire rapida asupra mesajului tau:

• Dupa "In primul rand" se pune virgula.
• "Sa nui pui punct la sfarsit de propozitie" - i-ul acela nu are ce cauta acolo.
• "In special cand aceea persoana ii se cuvine mai mult respect decat altora" - In ceea ce priveste aceasta fraza, nu am comentarii... Sa faci acordul nu este unul din punctele tale forte.
• "Intelectualii a avut mult de suferit" - Citeste ce am scris la punctul anterior.

Lasand gramatica si alte chestiuni neesentiale la o parte, nu inteleg in ce calitate evaluezi tu psihicul diversilor membrii ai forumului(pe care ii imparti cu mana ta divina in INTELECTUALI, categorie din care bineinteles ca faci parte, si RESTUL, persoane care incearca sa ii coboare pe intelectualii asemeni tie printre muritorii de rand).
[/offtopic]

Mi se pare ca rezolvarea problemelor de OJI si ONI din anii precedenti reprezinta un punct de plecare destul de bun pentru calificarea la ONI.
Lista de probleme ar merge intregita cu problemele selectate de diversi utilizatori in topicul asta. In general sunt probleme din care se invata cate ceva nou.

Miercuri, 20 februarie, de la ora 17:30 are loc Codeforces Round #168(Div 1 & Div 2) pe Codeforces

Eu am luat 100 cu citire cu stream-uri, fara parsare.

Ce complexitate ai?

Cred ca ar trebui marita limita de timp la aceasta problema.

Iau TLE pe un test folosind algoritmul lui Miller-Rabin cu 3 baze, ridicare la putere in timp logaritmic si parsarea citirii.

In general cand vrei sa iti spuna lumea ce gresesti ar fi util sa descri ce faci in sursa ta pentru ca este mult mai incomod de interpretat o sursa decat o idee.

Dinamica de care vei avea nevoie va fi de genul acesta dp[ i][j][k] = numarul de moduri in care poti alege i carti din primele j astfel incat suma acestora sa aiba restul k la impartirea cu 100.
Recurentele sunt destul de usor de gasit.

Probabil se poate gasi ceva mai eficient, dar din cauza faptului ca nu ai pus restrictiile problemei, nu stiu daca este necesar.

Pe testul pe care tu ai zis ca da NU RIMEAZA, desi corect ar fi RIMEAZA, sursa mea da RIMEAZA. In codul postat de tine ai uitat sa pui i = 0 dupa strcpy.

PS foloseste tag-ul code cand postezi cod

In primul rand, banuiesc ca voiai sa spui sa execute cautarea binara.
In al doilea rand, ar fi indicat sa precizezi ce ai incercat si ce nu ti-a iesit ca sa te putem ajuta.

@Simoiu Robert: Daca faci declararea cu e cum ai zis tu, in PInfinit vei avea valoarea 2 * 10^(-10) ceea ce tinde la 0, nu la infinit. Corect e fara acel -.

Cred ca ar trebui putin marita limita de timp la problema asta.

Am o rezolvare in O(N log N + L) si iau 60 de puncte cu TLE.

Atunci trebuie doar scos +1 de la strcpy si va functiona.

Am editat raspunsul ca sa functioneze

@Simoiu Robert: E gresit algoritmul tau.

Da testul:
arc
darcfearc

si o sa te convingi(al tau da "NU RIMEAZA").

Cod:

#include <stdio.h>
#include <stdlib.h>
#include <cstring>

int vocala(char voc)
{
    switch(voc)
    {
    case 'a' :
    case 'e' :
    case 'i' :
    case 'o' :
    case 'u' :
        return 1;
    default :
        return 0;
    }
}

int strlen(char sir[])
{
    int i=0;
    while(sir[i])
        i++;
    return i;
}

char* sufix(char sir[])
{
    int i;
    for(i=0; i<strlen(sir); i++)
        if(vocala(sir[i]) == 1)
        strcpy(sir, sir+i), i = 0;
    return sir;
}

int main()
{
    char sir_1[100], sir_2[100];
    int i, m, n, ok;
    printf("\n Introduceti primul cuvant : ");
    gets(sir_1);
    printf("\n Introduceti al doilea cuvant : ");
    gets(sir_2);
    if(strcmp(sufix(sir_1), sufix(sir_2)) == 0)
        printf("\n RIMEAZA\n");
    else
        printf("\n NU RIMEAZA\n");
}

Asta ar trebui sa mearga

@Dragu Mircea
Cele 2 siruri date de tine rimeaza. Ambele au sufixele fgfgfg.

Desi merge sa pui LL dupa un numar care depaseste valoare LL, acesta nu va putea fi stocat intr-o variabila de tip long long din motive evidente.
Nici daca declari un int si ii dai valoare 10000000000000 nu vei lua eroare de compilare, dar nici nu vei avea valoarea dorita in variabila.

Declararea ca 1e20 inseamna 10^20.
Daca vrei sa ti se afiseze in mod uzual si nu in format stiintific, este ok sa scrii cout<<fixed<<INF;

Pentru a folosi fixed trebuie sa incluzi header-ul iomanip.

Din cate mi se pare, gresesti in functia init.

Tu acolo iei vecinii fiecarei fortarete si le bagi distanta fata de cea mai apropiata fortareata, alaturi de indicele acestei fortarete.
Problema este ca tu vei face overwrite pe vectorul fort.

Sa presupunem ca ai fort = {1, 3, 4} cu indexare de la 1 si muchie de la 1 la 2 de cost 3 sa zicem.
Vei seta fort[2] = 1, iar astfel fort = {1, 1, 4}. Tu nu vei mai extinde fortareata 3.

Bafta! 

Nu ai cum sa scoti o solutie in O(N log N) din moment ce ai complexitate O(N^2) doar pentru citirea matricii.

Greseam eu ceva la distanta intre 2 puncte. Merge 

Intr-adevar exista un caz cand niciun om nu e nehotarat 

Pentru ca se rezolva/se poate rezolva folosind algoritmul pentru determinarea celor mai apropiate puncte in plan.

SPOILER ALERT!

Daca determini cele mai apropiate puncte in plan, poti considera aceea diagonala unui dreptunghi de latura x si 3x. Aplici teorema lui Pitagora si obtii ca D = 2x, unde D este distanta dintre cele mai apropiate 2 puncte in plan. De aici obtii ca x = D / 2, unde x e inaltimea ceruta.

LE Din cate vad e ceva mai smecher de atat... Nevertheless, probabil exista si o solutie cu cele mai apropiate pct in plan, pe langa cea cu cautare binara

Daca a rezolvat cineva problema asta cu algoritmul lui Manacher, as avea nevoie de putin ajutor. Iau doar 25 de puncte cu TLE, desi teoretic ar trebui sa intru lejer in limita de timp.

LE Uitam sa updatez centrul celui mai extins palindrom 

Problem solved thanks to Tudor Tiplea 

adaccaia
fdcac

Imi dadea ca sunt 6 posibilitati si am facut de mana si am ajuns la concluzia ca sunt mult mai multe

LE Scuze. Imi dadea bine. 6 dadea cu alta submisie care nu am lasat-o pana la final

Mie imi da ca sunt 22 de posibilitati ...

si mie

Cod:

#include <fstream>

using namespace std;

int main()
{
int N, invers = 0;
ifstream in("intrare.txt"); in>>N; in.close();
while(N)
{
invers = invers * 10 + N % 10;
N = N / 10;
}
ofstream out("iesire.txt"); out<<invers; out.close();
}