fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector> 
  4.  
  5. using namespace std;
  6.  
  7. #define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
  8. #define forn(i, n) forsn(i, 0, n)
  9. #define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
  10. #define dforn(i, n) dforsn(i, 0, n)
  11.  
  12. #define sz(x) int(x.size())
  13. #define all(x) begin(x), end(x)
  14.  
  15. typedef pair<int, int> ii;
  16. typedef vector<int> vi;
  17. typedef long double ld;
  18.  
  19. const int ALPHA = 26;
  20. const int INF = 1e9;
  21.  
  22. struct Edge {
  23.     int u, v, w;
  24.     Edge(int a, int b, int c) : u(a), v(b), w(c) {}
  25. };
  26.  
  27. int id(char x, char y) { return (x - 'a') * ALPHA + (y - 'a'); }
  28.  
  29. const int NODES = ALPHA * ALPHA;
  30.  
  31. template<typename T>
  32. void chmax(T &x, T v) {
  33.     if (x < v) x = v;
  34. }
  35.  
  36. template<typename T>
  37. void chmin(T &x, T v) {
  38.     if (x > v) x = v;
  39. }
  40.  
  41. int main() {
  42.     ios::sync_with_stdio(0);                
  43.     cin.tie(0); cout.tie(0);
  44.  
  45.     int n;
  46.     while (cin >> n) {
  47.         if (n == 0) break;
  48.         vector<Edge> graph;
  49.         graph.reserve(n);
  50.         forn(i, n) {
  51.             string s;
  52.             cin >> s;
  53.             int w = sz(s);
  54.             if (w < 2) continue;
  55.             int u = id(s[0], s[1]);
  56.             int v = id(s[w - 2], s[w - 1]);
  57.             graph.push_back(Edge(u, v, w));
  58.         }
  59.         n = sz(graph);
  60.         vector<vi> dp(NODES + 1, vi(NODES, -INF));
  61.         dp[0] = vi(NODES, 0);
  62.         forn(i, NODES) {
  63.             forn(j, n) {
  64.                 Edge &e = graph[j];
  65.                 if (dp[i][e.u] < 0) continue;
  66.                 chmax(dp[i + 1][e.v], dp[i][e.u] + e.w);
  67.             }
  68.         }
  69.         ld x = 0;
  70.         forn(u, NODES) {
  71.             if (dp[NODES][u] < 0) continue;
  72.             ld y = INF;
  73.             forn(i, NODES) {
  74.                 if (dp[i][u] < 0) continue;
  75.                 chmin(y, (dp[NODES][u] - dp[i][u]) / ld(NODES - i));
  76.             }
  77.             chmax(x, y);
  78.         }
  79.         if (x < 1) {
  80.             cout << "No solution.\n";
  81.         } else {
  82.             cout << fixed << setprecision(2) << x << "\n";
  83.         }
  84.     }
  85.  
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xwYInL
problem WORDRING, based on SPOJ submission 35503795 (CPP14), 2026-02-02 15:27:52
language:
C++14 (gcc 8.3)
created:
3 hours ago
visibility:
public

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!