Omówienie zadania “Dwukrotność sumy cyfr”

Omówienie zadania “Dwukrotność sumy cyfr”

Szczegółowe omówienie zadania Dwukrotność sumy cyfr:

Link do powyższego omówienia zadania Dwukrotność sumy cyfr:
https://youtu.be/x8-GgzTgCH8

Link do zadania:
https://szkopul.edu.pl/problemset/problem/Cgw52wK7lgkABFnX_GbP-kiD/site


Zadanie Dwukrotność sumy cyfr wymaga jedynie pomysłu, zauważenia, że komputer bez sensu powtarza cały czas te same operacje.
Wówczas możemy napisać program, który zamiast liczyć kolejne wartości setki lat (wykonywać 10^18 operacji), upora się z problemem w ułamek sekundy licząc kilkadziesiąt wartości ciągu.


Zadanie Dwukrotność sumy cyfr pochodzi z I etapu, tury otwartej XIV Olimpiady Informatycznej Juniorów.
Pięknie pokazuje. że każdy z nas może startować w Olimpiadzie Informatycznej!
Link do wszystkich zadań z Olimpiady Informatycznej Juniorów:
https://szkopul.edu.pl/task_archive/oig/


Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625


Kod C++ programu Dwukrotność sumy cyfr, który jest omówiony w powyższym filmie i który otrzymuje 100%

#include <bits/stdc++.h>
using namespace std;

int pozycje[400];

int DwukrotnoscSumyCyfr (long long liczba) {
 int suma_cyfr, cyfra;

 suma_cyfr = 0;
 while (liczba > 0) {
    cyfra = liczba % 10;
	suma_cyfr = suma_cyfr + cyfra;
    liczba = liczba / 10;
 }

 return 2*suma_cyfr;
}

int main(){
 long long liczba, n;
 long long dlugosc_cyklu, pozostale_elementy_ciagu, pozostala_liczba_ruchow;
 int i, j;

 cin >> n >> liczba;

 if ( n == 1 ) {
    cout << liczba;
    return 0;
 }
 
 for (i=2; i<=n; ++i) {
 	liczba = DwukrotnoscSumyCyfr(liczba);
 	if ( pozycje[liczba] == 0 ) {
       pozycje[liczba] = i;
       continue;
    }
    dlugosc_cyklu = i - pozycje[liczba];
    pozostale_elementy_ciagu = n - i;
    pozostala_liczba_ruchow = pozostale_elementy_ciagu % dlugosc_cyklu;
    j = 0;
    while (true) {
       if ( j == pozostala_liczba_ruchow ) {
          cout << liczba << "\n";
          return 0;
	   }
 	   liczba = DwukrotnoscSumyCyfr(liczba);
	   ++j;	
	}
 } 
 cout << liczba << "\n";

 return 0;
}
Kod C++ programu Dwukrotność sumy cyfr, który jest omówiony w powyższym filmie i który otrzymuje 100%

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz