Advertisement
YEZAELP

o64_feb_c2_kon

Jan 30th, 2022
720
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 1e9;
  5. const int N = 1e6;
  6. int dp[N + 10], par[N + 10], cnt[N + 10];
  7. string ans[N + 10];
  8.  
  9. int main(){
  10.  
  11.     dp[1] = 0;
  12.     for(int i = 2; i <= N; i ++)
  13.         dp[i] = INF;
  14.     for(int i = 1; i <= N; i ++){
  15.         for(int j = i + i, c = 1; j <= N; j += i, c ++){
  16.             int cur = dp[i] + 3 + c;
  17.             if(cur < dp[j]){
  18.                 dp[j] = cur;
  19.                 par[j] = i;
  20.                 cnt[j] = c;
  21.             }
  22.         }
  23.     }
  24.  
  25.     FILE *read, *write;
  26.     read = fopen("kon_input.txt", "r");
  27.     write = fopen("kon_output.txt", "w");
  28.  
  29.     int Q;
  30.     fscanf(read, "%d", &Q);
  31.     fprintf(write, "10\n");
  32.     for(int q = 1; q <= Q; q ++){
  33.         int x;
  34.         fscanf(read, "%d", &x);
  35.         fprintf(write, "%d\n", q);
  36.         int cur = x;
  37.         vector <char> ans;
  38.         while(cur != 1){
  39.             for(int i = 1; i <= cnt[cur]; i ++)
  40.                 ans.push_back('V');
  41.             ans.push_back('V');
  42.             ans.push_back('C');
  43.             ans.push_back('A');
  44.             cur = par[cur];
  45.         }
  46.         for(int i = dp[x] - 1; i >= 0; i --)
  47.             fprintf(write, "%c", ans[i]);
  48.         fprintf(write, "\n");
  49.     }
  50.  
  51.     fclose(read);
  52.     fclose(write);
  53.  
  54.     return 0;
  55. }
Advertisement
RAW Paste Data Copied
Advertisement