/home/toolbox/public_html/solutions/101/10170/b.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9 #include <ctype.h>
10
11 #define TRUE (1 == 1)
12 #define FALSE (1 != 1)
13
14 #define DEBUG if (FALSE)
15
16 /*
17 * Author: Isaac Traxler
18 * Date: 2023-10-17
19 * Purpose: fun
20 * Problem: 10170
21 */
22
23 /*
24 * This template reads data until a terminating value is reached.
25 *
26 * for the sequence:
27 * 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 ...
28 *
29 * (n * (n + 1)) / 2 calculates the where the nth digit last appears
30 * so if n is 5:
31 * (5 * 6) / 2 = 30 -- so 5s end at 15
32 *
33 * 4s end at 10, so 5s start at 11
34 * so the start is:
35 * (n * (n -1)) / 2 + 1
36 *
37 * So if the you start with 4, you are omitting 1-3 (the first 6 days of full sequence)
38 * basically, you are adding 6 to number of days
39 *
40 *
41 * To find the pth item, you must solve the first equation for n
42 *
43 * p = (n * (n + 1)) / 2
44 * p = (n^2 + n) / 2
45 * 2p = n^2 + n
46 * 0 = n^2 + n - 2p
47 * in the form aX^2 + bX + c,
48 * a = 1
49 * b = 1
50 * c = p * -2
51 *
52 * quadrtic formula:
53 * x = (-b + sqrt(b * b - 4ac)) / 2a
54 * since a nd b are 1
55 * x = -1 + sqrt(1 - 4c) / 2
56 * and c = - p * 2
57 * x = (-1 + sqrt(1 + 8p) ) / 2
58 *
59 */
60
61
62 int start;
63 int days;
64
65 void init()
66 {
67 /* FUNCTION init */
68 } /* FUNCTION init */
69
70 void dump()
71 {
72 /* FUNCTION dump */
73 } /* FUNCTION dump */
74
75 int getInput()
76 {
77 /* FUNCTION getInput */
78 int dataReadFlag;
79
80 dataReadFlag = ! feof(stdin);
81 if (dataReadFlag)
82 {
83 /* something to read */
84 scanf(" %d %d ", &start, &days);
85 } /* something to read */
86 return (dataReadFlag);
87 } /* FUNCTION getInput */
88
89 int findP(int d)
90 {
91 /* function findP */
92 /* x = (-1 + sqrt(1 + 8p) ) / 2 */
93 double t;
94 int ret;
95
96 t = 1 + 8 * d;
97 t = sqrt(t);
98 ret = (-1 + (0.5 + t) ) / 2;
99 return ret;
100 } /* function findP */
101
102 int omit(int n)
103 {
104 /* function omit */
105 int ret;
106
107 ret = (n * (n + 1)) / 2;
108 return ret;
109 } /* function omit */
110
111 void process()
112 {
113 /* FUNCTION process */
114 int skip;
115 int lst;
116 int ans;
117
118 skip = omit(start - 1);
119 lst = findP(days);
120 ans = findP(skip + days);
121 printf("(start %d) (skip %d) (days %d) (lst %d) (ans %d)\n", start, skip, days, lst, ans);
122 } /* FUNCTION process */
123
124 int main()
125 {
126 /* main */
127 int moreToDo;
128
129 init();
130 moreToDo = getInput();
131 while (moreToDo)
132 {
133 /* while */
134 process();
135 moreToDo = getInput();
136 } /* while */
137
138 return EXIT_SUCCESS;
139 } /* main */
140