fork(3) download 
  1. #include <iostream>
  2. #include <math.h>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. void wypisz_rozwiazanie(int* tab_wy, int j)
  8. {
  9.     int licznik_G = 0, licznik_D = 0;
  10.     for (int i = 0; i <= j; i++)             //znajdź ilość wystąpień pozycji przełącznika
  11.     {
  12.         if (tab_wy[i] == 1)
  13.             licznik_G++;
  14.         if (tab_wy[i] == -1)
  15.             licznik_D++;
  16.     }
  17.     cout << licznik_G << " ";
  18.     for (int i = 0; i <= j; i++)             //wypisz pozycje G
  19.     {
  20.         if (tab_wy[i] == 1)
  21.             cout << i << " ";
  22.     }
  23.     cout << endl;
  24.     cout << licznik_D << " ";
  25.     for (int i = 0; i <= j; i++)             //wypisz pozycje G
  26.     {
  27.         if (tab_wy[i] == -1)
  28.             cout << i << " ";
  29.     }
  30.     cout << endl;
  31.  
  32. }
  33.  
  34. //zwraca tab_wy[]: 1 na pozycji to G, 0 brak, -1 D; gdzie G=potęga+, D=potęga-  
  35. //przykłady: 5=-1-3+9 => [-1,-1,1]; 10=+1+0+9 => [1,0,1]  
  36. void szukaj_klucza(int x, int* tab_wy, int* tab_p, int j)
  37. {
  38.     int pom1, pom2, pom3, znak, min, l_startowa;
  39.     l_startowa = tab_p[j];
  40.     tab_wy[j] = 1;
  41.     j--;
  42.     for (int i = j; i >= 0; i--)
  43.     {
  44.         //trzy przypadki co robimy z kolejną wartością potęgi -> szukamy różnicy najbliższej x
  45.         //i dla minimum ustawiamy znak -1 lub 0 lub 1 
  46.         pom1 = l_startowa - tab_p[i]; pom2 = l_startowa + 0; pom3 = l_startowa + tab_p[i];
  47.         if (abs(pom1 - x) > abs(pom2 - x))
  48.         {
  49.             znak = 0, min = abs(pom2 - x), l_startowa = pom2;
  50.         }
  51.         else 
  52.         { 
  53.             znak = -1, min = abs(pom1 - x), l_startowa = pom1;
  54.         }
  55.         if (min > abs(pom3 - x))
  56.             znak = +1, l_startowa = pom3;
  57.         tab_wy[i] = znak;
  58.     }
  59. }
  60.  
  61.  
  62. int main()
  63. {
  64.     int suma_poteg;
  65.     int l_zamkow = 20;
  66.     int *tab_p;                         //tablica kolejnych poteg liczby 3 o rozmiamrze ilosci zamkow 
  67.     int *tab_s;                         //i sum ich poteg
  68.     int *tab_wy;                        //tablica ustawien przełacznków
  69.     //int t=1;                          //liczba haseł czyli testów
  70.     int t; 
  71.     cin >> t;
  72.     int x=0;                            //liczba kodowana 
  73.     int j;                              //liczba potęg potrzebnych z tablicy 
  74.     tab_p = new int[l_zamkow];
  75.     tab_s = new int[l_zamkow];
  76.     tab_wy = new int[l_zamkow];
  77.     tab_s[0] = 0;
  78.     for (int i = 0; i < 20; i++)        //klucze do 20-stu pozycji 
  79.     {
  80.         tab_wy[i] = -100;
  81.         tab_s[i] = 0;
  82.         tab_p[i] = pow(3,(double)i);
  83.         if (i==0)
  84.             tab_s[i] += tab_p[i];
  85.         else
  86.             tab_s[i] = tab_s[i-1]+ tab_p[i];
  87.     }
  88.     for (int i = 0; i < t; i++)         //ustala ile j sum potęg potrzeba do reprezenatacji danej liczby
  89.     {
  90.         j = 0; suma_poteg = 0;
  91.         cin >> x;
  92.         while (x > suma_poteg)
  93.         {
  94.             suma_poteg = tab_s[j];
  95.             j++;
  96.         }
  97.         --j;
  98.         szukaj_klucza(x, tab_wy, tab_p, j);
  99.         wypisz_rozwiazanie(tab_wy, j);
  100.         //cout << endl << j << endl;
  101.     }
  102.     delete [] tab_p;
  103.     delete [] tab_s;
  104.     delete [] tab_wy;
  105.     //system ("pause");
  106.     return 0; 
  107. }
Success #stdin #stdout 0.01s 5380KB
comments (?)
stdin 
2
5
10
stdout 
1 2 
2 0 1 
2 0 2 
0
https://ideone.com/BQqA9J
problem OIG1_DIA, based on SPOJ submission 29635644 (C++ 4.3.2), 2022-06-01 18:24:55
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!