Paginacja

[RediioS]

Pomoże ktoś w rozwiązaniu tego zadania:

 

Paginacja to nic innego, tylko opatrzenie stron książki kolejnymi numerami. Załóżmy, że pierwsza strona książki ma numer 1, numeracja jest jednolita i że używamy tylko liczb arabskich.

 

Zadanie

 

Napisz program, który: czyta ilości stron książek i znajduje ilość cyfr użytych do ich paginacji.

 

Wejście

 

Pierwszy wiersz danych zawiera liczbę całkowitą Z (1 ≤ Z ≤ 1000) oznaczającą ilość książek. W kolejnych Z wierszach znajdują się ilości stron w każdej książce – po jednej w każdym wierszu (są to liczby naturalne z zakresu od 2 do 5000).

 

Wyjście

 

Program powinien dla każdej książki wypisać wiersz tekstu zawierający liczbę cyfr użytych do jej paginacji.

 

 

Przykład

Dla danych wejściowych:
2
10
100

poprawnym wynikiem jest:
11
192

[encoreeFTW]

Od czego zacząć (wariant prosty mniej wydajny):

 

1. Każdą ksiażkę przeskakujesz co 10x- więc złożoność masz logarytmiczną o podstawie 10 .

1-9 masz po 1, 10-99 masz po 2, 100-999 masz po 3 (czyli po prostu

dodajesz). Zakładajć że strony w książkach nie mają więcej niż 10^9

długości więc masz jedynie 9 stopni na każdą książkę do policzenia. A

tych masz 1000 więc nie jest nawet dużo Wystarczy dobrze dodać i pomnożyć co nieco

 

 

[metin1998]

ciekawy problem

 

#include <iostream>

using namespace;

int main() {
int nbooks;
int npg;

cin >> nbooks;

for(int i=0; i < nbooks; i++) {
cin >>npg;
if(npg<10) cout << npg;
else if(npg<100) cout << 9 + (npg-9) *2;
else if(npg<1000) cout << 9 + 90*2 +(npg-(9+90)) * 3;
else if(npg<10000) cout << 9 + 90*2 + 900*3 +(npg - ( 9 + 90 + 900))*4;
}
return 0;
}
 

 

 

 

Można by to zrobić jeszcze szybciej, deklarujac stałą tablice ze poprawną ilością cyfr dla każdej ilości stron.

 

kod wyglądał by wtedy m/w tak

 

cin >> nbooks;

 

for(int i=0;i < nbooks; i++) {

cin >> npg;

cout << tablica[npg];

}

 

 

jeżeli zamienisz cin i cout na szybsze odpowiedniki to bedziesz mial najszybsze rozwiazanie (jezeli zalezy Ci na byciu pierwszym w rankingu Czas wykonania)

[Sopelek997]

#include <iostream>

int main()

{

int strony, cyfry = 0;

cin >> strony;

for(int x = 1000, a = 4; x != 0; x /= 10)if(x <= strony)(cyfry += strony - x + 1) * a--;

std::cout << cyfry;

}

 

 

 

[Sopelek997]

Jak wróciłem do tego tematu i przejrzałem ko,dk tóry napisałem to zauważyłem, że chyba byłem nieprzytomny jak go pisałem ;d

#include <iostream>
int main()
{
    int strony, cyfry = 0;
    std::cin >> strony;
    for(int x = 1000; x != 0; x /= 10)if(x <= strony) cyfry += strony - x + 1;
    std::cout << cyfry;
}

ten działa również poprawnie, a nie ma w nim niepotrzebnych rzeczy